Browse › Combinatorics › 165 The Harary–Hill and Zarankiewicz crossing-number formulas
The crossing number of complete bipartite graphs
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We prove the Zarankiewicz crossing-number conjecture, resolving Turán's brickyard problem. For all positive integers m, n, the ordinary crossing number of the complete bipartite graph $K_{m,n}$ is $\displaystyle \left\lfloor\frac m2\right\rfloor \left\lfloor\frac{m-1}{2}\right\rfloor \left\lfloor\frac n2\right\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor.$
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-23) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- J. Balogh, N. Layman, B. Lidický, F. Pfender, G. Salazar, S. Spiro, J. Volec, Crossing numbers of complete bipartite graphs (arXiv:2610.25204, 18 Oct 2026). Uses flag algebras to obtain asymptotic lower bounds of 0.96936 times the Zarankiewicz value for balanced complete bipartite graphs (also treating the rectilinear version) and 0.9899 times the Hill value for complete graphs; its abstract notes that both conjectures "were claimed to be true in manuscripts by OpenAI dated Sep 23, 2026", and it cites both manuscripts while describing its results as preceding them. [family-level]
- A. Hubard, C. S. Ndiaye, O. Solé-Pi, Crossing numbers of simplicial complexes (arXiv:2610.21017, 14 Oct 2026). A paper on higher-dimensional crossing numbers; a footnote says a solution to the Zarankiewicz and Hill conjectures was announced as the manuscript was about to be made public, without naming the source. [family-level]
Formalization
- OpenAI math release, Lean scope note for family 165 (mirrored on mathcommunity/oai-math-revised) (release, 6 Oct 2026). The release's Lean scope note states that the formalization proves cr(K_{m,n}) = ⌊m/2⌋⌊(m−1)/2⌋⌊n/2⌋⌊(n−1)/2⌋ for all positive m, n with a drawing attaining it, crossings counted as points, and links the comparator statements
BipartiteCrossing.leanandCompleteCrossing.lean. [family-level]
Possibly relevant literature (found by the agent, not checked)
- K. Clancy, M. Haythorpe, A. Newcombe, A survey of graphs with known or bounded crossing numbers (arXiv:1901.05155, dynamic survey, last updated Dec 2021). Compiles known exact crossing numbers of K_{m,n} and related families beyond the cases the introduction lists (Kleitman's min{m,n} ≤ 6 and Woodall's K_{7,7}, K_{7,9}); it is not in the bibliography.
Digests and expositions
- Open Mathematics Courses, Crossing numbers of complete and complete bipartite graphs (undated). Eight lessons develop the manuscripts' normalization, cycle pairing, interpolation, subspace inequality and matching constructions, with proofs and exercises; the site attributes writing and self-checking to Claude Opus 5.5 and states that independent review is incomplete. [AI-generated per source] [family-level]
- Gradient Damage, The Harary–Hill conjecture: why 18 dots need 1,008 crossings (12 Oct 2026). An introductory exposition of the complete-graph formula with an illustrative animation, also introducing the companion bipartite claim and distinguishing illustration from proof verification. [family-level]
News and blogs
- ぶちょう (rivas_bucho), OpenAI's 722 Math Papers Are Not a Story of 'Leaving Humans Behind'—An Introductory Guide to 8 Key Topics (note.com, 9 Oct 2026). A general-audience overview that recounts Turán's 1944 brick-factory origin and the gap in Zarankiewicz's 1954 proof, and says No. 165 claims to solve the problem together with Hill's conjecture, with a Lean proof. [family-level]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 165
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:The-crossing-number-of-complete-bipartite-graphs-September-23-2026,
author = {{OpenAI}},
title = {{The crossing number of complete bipartite graphs}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/The-crossing-number-of-complete-bipartite-graphs-September-23-2026/paper.pdf}{OAI:The-crossing-number-of-complete-bipartite-graphs-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/165.md. The Lean statements have not been checked by people against the paper's claims.
Family 165: The Harary–Hill and Zarankiewicz crossing-number formulas
Resolves the Harary–Hill conjecture and Turán's brickyard problem in the Zarankiewicz formulation, determining the crossing numbers of every complete and complete bipartite graph. The result proves the optimality of the classical drawings among all plane drawings with continuous edge arcs.
Other papers in this family:
- The crossing number of complete graphs · September 23, 2026