Cross-intersecting set-system conjecture

Let A,B2[d]\mathcal A,\mathcal B\subseteq 2^{[d]}. For L{0,,d}L\subseteq\{0,\ldots,d\}, they are LL-cross-intersecting if ABL|A\cap B|\in L for every AAA\in\mathcal A and BBB\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 RA\mathcal R\subseteq\mathcal A, SB\mathcal S\subseteq\mathcal B, and tLt\in L such that R\mathcal R and S\mathcal S are {t}\{t\}-cross-intersecting and

RSAB2polylog(d).|\mathcal R||\mathcal S|\geq |\mathcal A||\mathcal B|\cdot 2^{-\operatorname{polylog}(d)}.

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

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.