Crossing numbers of complete bipartite graphs

Abstract

Zarankiewicz's long standing conjecture states that the crossing number $cr(K_{m,n})$ 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 $cr(K_{n,n}) \geq 0.96936 \cdot Z(n,n) + o(n^4)$. We also show that the rectilinear crossing number $\overline{cr}(K_{n,n})$ of $K_{n,n}$ is at least $0.987\cdot Z(n,n) + o(n^4)$. Additionally, we prove the following for complete bipartite graphs: if a drawing of $K_{n,n}$ contains no induced subdrawing of $K_{3,4}$ with exactly two crossings whose endpoints intersect in exactly one vertex, then it has at least $Z(n,n)+o(n^4)$ crossings. This is a local restriction inspired by Turán-type problems that gives an asymptotically tight result. A closely related conjecture is Hill's conjecture stating that the crossing number $cr(K_{n})$ of the complete graph $K_n$ 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 $n \geq 3$. By an averaging argument, the asymptotic Zarankiewicz conjecture implies the asymptotic Hill conjecture. We improve the lower bound on $cr(K_{n})$ from $(0.985+o(1)) H(n)$ to $(0.9899+o(1)) H(n)$. 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.