Zarankiewicz conjecture and Hill’s conjecture
For all positive integers , the crossing number of the complete bipartite graph is
References
- Crossing numbers of complete bipartite graphs — arXiv — József Balogh, Nicholas Layman, Bernard Lidický, Florian Pfender, Gelasio Salazar, Sam Spiro, Jan Volec
Source: arXiv
Progress summary
An unrefereed new paper brings two long-standing graph-drawing predictions closer to the truth, but proves neither.
The Zarankiewicz and Hill conjectures predict exact formulas for crossing numbers of complete bipartite and complete graphs. Both remain unresolved in general.
Known results
- Hill’s conjecture was verified only through ; Balogh, Lidický, and Salazar (2018) proved an asymptotic ratio exceeding .
- Zarankiewicz’s conjecture is known for , for , and several additional small cases; a 2019 survey records these results.
- Earlier flag-algebra work gave asymptotic lower bounds exceeding for complete graphs and for balanced complete bipartite graphs.
October 18, 2026 flag-algebra update
A new preprint reports lower bounds of for and for , narrowing both asymptotic gaps. These are claimed advances, not exact proofs; the preprint is unrefereed and the reported constants lack independent corroboration in the scan.
Current status (as of October 2026): Both exact conjectures remain open; the October bounds are claimed progress from an unrefereed preprint.
Solutions 0
No solutions have been posted yet.