Parallel k-partition conjecture for incidence configurations

From papers

Let (P,H)(\mathcal P,\mathcal H) be a point-hyperplane configuration in Rd\mathbb R^d. A parallel kk-partition is a partition of H\mathcal H into blocks of at most kk parallel hyperplanes such that every point is incident to a hyperplane in each block.

Parallel kk-partition conjecture. For every fixed integer k>1k>1,

rs(P,H)mn2polylog(d).\operatorname{rs}(\mathcal P,\mathcal H) \geq mn\cdot 2^{-\operatorname{polylog}(d)}.

Equivalently, every kk-listable matrix MRn×mM\in\mathbb R^{n\times m} contains a 11-listable submatrix of size at least mn2polylog(rank(M))mn\cdot 2^{-\operatorname{polylog}(\operatorname{rank}(M))}. The source proves this conjecture equivalent to the parallel 2-partition conjecture and hence to the log-rank conjecture, so it remains open.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.