pipette
ESEspañol

Crossing numbers of complete bipartite graphs

J\'ozsef Balogh, Nicholas Layman, Bernard Lidick\'y, Florian Pfender, Gelasio Salazar, Sam Spiro, Jan Volec

Preprint

In the authors' words

Zarankiewicz's long standing conjecture states that the crossing number of the complete bipartite graph is \[ Z(m,n):=\bigg\lfloor{\frac{m}{2}}\bigg\rfloor \bigg\lfloor{\frac{m-1}{2}}\bigg\rfloor \bigg\lfloor{\frac{n}{2}}\bigg\rfloor \bigg\lfloor{\frac{n-1}{2}}\bigg\rfloor. \] Using flag algebras, we show that . We also show that the rectilinear crossing number of is at least . Additionally, we prove the following for complete bipartite graphs: if a drawing of contains no induced subdrawing of with exactly two crossings whose endpoints intersect in exactly one vertex, then it has at least crossings. This is a local restriction inspired by Tur\'an-type problems that gives an asymptotically tight result. A closely related conjecture is Hill's conjecture stating that the crossing number of the complete graph is \[ H(n):= \frac14 \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor \] for all . By an averaging argument, the asymptotic Zarankiewicz conjecture implies the asymptotic Hill conjecture. We improve the lower bound on from to . Both conjectures were claimed to be true in manuscripts by OpenAI dated Sep 23, 2026 and made public on Oct 6, 2026. This paper represents the state of knowledge before those publications and shows how far we can push the flag algebra method.

Main resultLimitation the authors admit

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 13 pages, 5 figures