Lovett's incidence-graph conjecture for points and hyperplanes

About 2 years old · traced to

Let ε∈(0,1/2)\varepsilon\in(0,1/2), and consider the incidence graph between nn points and nn hyperplanes in Rd\mathbb{R}^d, with an edge joining a point to a hyperplane when the point lies on that hyperplane.

Lovett's incidence-graph conjecture. If the graph has at least (1−ε)n2(1-\varepsilon)n^2 edges, then it contains a complete balanced bipartite subgraph of size at least

n⋅exp⁡(−O(εd)).n\cdot\exp(-O(\sqrt{\varepsilon d})).

This is presented as an equivalent geometric formulation of Lovett's sparse low-rank matrix conjecture. The supplied text does not state whether it has been resolved.

References

Primary source

Zach Hunter, Aleksa Milojević, Benny Sudakov and István Tomon, “Disjoint pairs in set systems and combinatorics of low rank matrices”, arXiv:2411.13510 (2024).

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.