Cross-intersecting set-system conjecture

At least 4 years old · documented by

Let A,B⊆2[d]\mathcal A,\mathcal B\subseteq 2^{[d]}. For L⊆{0,…,d}L\subseteq\{0,\ldots,d\}, they are LL-cross-intersecting if ∣A∩B∣∈L|A\cap B|\in L for every A∈AA\in\mathcal A and B∈BB\in\mathcal B.

Cross-intersecting set-system conjecture. For every fixed k>0k>0, if ∣L∣=k|L|=k and A,B\mathcal A,\mathcal B are LL-cross-intersecting, then there exist R⊆A\mathcal R\subseteq\mathcal A, S⊆B\mathcal S\subseteq\mathcal B, and t∈Lt\in L such that R\mathcal R and S\mathcal S are {t}\{t\}-cross-intersecting and

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

Equivalently, the matrix with entries ∣A∩B∣|A\cap B| contains a monochromatic rectangle of density at least 2−polylog⁡(d)2^{-\operatorname{polylog}(d)}. The source says this conjecture would be implied by the parallel kk-partition conjecture and is therefore equivalent to the log-rank conjecture, but it remains open.

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.