Crossing numbers of complete bipartite graphs
Abstract
Zarankiewicz's long standing conjecture states that the crossing number cr(Km,n) of the complete bipartite graph is Z(m,n):=⌊m/2⌋ ⌊(m−1)/2⌋ ⌊n/2⌋ ⌊(n−1)/2⌋. Using flag algebras, we show that cr(Kn,n) ≥ 0.96936 · Z(n,n) + o(n4). We also show that the rectilinear crossing number cr̅(Kn,n) of Kn,n is at least 0.987· Z(n,n) + o(n4). Additionally, we prove the following for complete bipartite graphs: if a drawing of Kn,n contains no induced subdrawing of K3,4 with exactly two crossings whose endpoints intersect in exactly one vertex, then it has at least Z(n,n)+o(n4) 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(Kn) of the complete graph Kn is H(n):= 1/4 ⌊ n/2 ⌋ ⌊ (n−1)/2 ⌋ ⌊ (n−2)/2 ⌋ ⌊ (n−3)/2 ⌋ for all n ≥ 3. By an averaging argument, the asymptotic Zarankiewicz conjecture implies the asymptotic Hill conjecture. We improve the lower bound on cr(Kn) 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.
Related
- Turán numbers for suspensions of bipartite 2-regular graphs
- Negative edge correlation in complete bipartite graphs
- Maximal Linear Arrangement is NP complete on Bipartite Graphs
- Wild number for spanning trees in complete and complete bipartite graphs
- Counting linear extensions of incidence posets of bipartite graphs is #P-complete
BibTeX
@misc{balogh2026crossing,
title = {{Crossing numbers of complete bipartite graphs}},
author = {József Balogh and Nicholas Layman and Bernard Lidický and Florian Pfender and Gelasio Salazar and Sam Spiro and Jan Volec},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25204},
eprint = {2610.25204},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25204},
}
RIS
TY - UNPB
TI - Crossing numbers of complete bipartite graphs
AU - József Balogh
AU - Nicholas Layman
AU - Bernard Lidický
AU - Florian Pfender
AU - Gelasio Salazar
AU - Sam Spiro
AU - Jan Volec
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2610.25204
UR - https://arxiv.org/abs/2610.25204
AB - Zarankiewicz's long standing conjecture states that the crossing number cr(K_m,n) of the complete bipartite graph is Z(m,n):=⌊m/2⌋ ⌊(m−1)/2⌋ ⌊n/2⌋ ⌊(n−1)/2⌋. Using flag algebras, we show that cr(K_n,n) ≥ 0.96936 · Z(n,n) + o(n^4). We also show that the rectilinear crossing number cr̅(K_n,n) of K_n,n is at least 0.987· 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):= 1/4 ⌊ n/2 ⌋ ⌊ (n−1)/2 ⌋ ⌊ (n−2)/2 ⌋ ⌊ (n−3)/2 ⌋ for all n ≥ 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.
ER -