Lovett's incidence-graph conjecture for points and hyperplanes

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

nexp(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.

Sources & referencesView supporting material

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.