Parallel k-partition conjecture for incidence configurations

About 5 years old · traced to

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)≥mn⋅2−polylog⁡(d).\operatorname{rs}(\mathcal P,\mathcal H) \geq mn\cdot 2^{-\operatorname{polylog}(d)}.

Equivalently, every kk-listable matrix M∈Rn×mM\in\mathbb R^{n\times m} contains a 11-listable submatrix of size at least mn⋅2−polylog⁡(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.

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.