Almost cross-disjoint set-system conjecture

About 5 years old · traced to

Let A,B⊆2[d]\mathcal A,\mathcal B\subseteq 2^{[d]}. They are ϵ\epsilon-almost cross-disjoint if

Pr⁡A∼A, B∼B[A∩B≠∅]≤ϵ.\Pr_{A\sim\mathcal A,\,B\sim\mathcal B}[A\cap B\neq\emptyset]\leq\epsilon.

They are exactly cross-disjoint when no such intersection occurs.

Almost cross-disjointness conjecture. For every fixed ϵ>0\epsilon>0, if A\mathcal A and B\mathcal B are ϵ\epsilon-almost cross-disjoint, then there exist R⊆A\mathcal R\subseteq\mathcal A and S⊆B\mathcal S\subseteq\mathcal B that are exactly cross-disjoint and satisfy

∣R∣∣S∣≥∣A∣∣B∣⋅2−O(d).|\mathcal R||\mathcal S|\geq |\mathcal A||\mathcal B|\cdot 2^{-O(\sqrt d)}.

Equivalently, the intersection matrix with entries ∣A∩B∣|A\cap B| contains a zero-monochromatic rectangle of density at least 2−O(d)2^{-O(\sqrt d)}. The source says this conjecture would follow from the incidence-density conjecture; it is not resolved in the supplied text.

References

Primary source

Noah Singer and Madhu Sudan, “Point-hyperplane incidence geometry and the log-rank conjecture”, arXiv:2101.09592 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.