Almost cross-disjoint set-system conjecture

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

PrAA,BB[AB]ϵ.\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 RA\mathcal R\subseteq\mathcal A and SB\mathcal S\subseteq\mathcal B that are exactly cross-disjoint and satisfy

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

Equivalently, the intersection matrix with entries AB|A\cap B| contains a zero-monochromatic rectangle of density at least 2O(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.

Sources & referencesView supporting material

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.