Browse › Combinatorics › 165 The Harary–Hill and Zarankiewicz crossing-number formulas
The crossing number of complete 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 Harary–Hill conjecture: for every positive integer n, the ordinary crossing number of the complete graph Kn is $\displaystyle \frac14\left\lfloor\frac n2\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.$
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.9899 times the Hill value for complete graphs and 0.96936 times the Zarankiewicz value for balanced complete bipartite 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). Studies a higher-dimensional generalized Harary–Hill conjecture and gives a proof of Harary–Hill for antipodal drawings; 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_n) = Z(n) for n ≥ 3 with a matching two-page drawing, crossings counted as points, and links the comparator statements
CompleteCrossing.leanandBipartiteCrossing.lean. [family-level]
Possibly relevant literature (found by the agent, not checked)
- B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, D. McQuillan, B. Mohar, P. Mutzel, P. Ramos, R. B. Richter, B. Vogtenhuber, Bishellable drawings of K_n (arXiv:1510.00549, 2015, rev. 2018). Extends the shellability criterion cited in the introduction to the weaker bishellability condition, which also forces the Harary–Hill bound; 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 whose brick-factory section says No. 165 "claims to have solved both this problem and its sibling, Hill's conjecture" with a Lean proof, and recalls the gap in Zarankiewicz's 1954 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-graphs-September-23-2026,
author = {{OpenAI}},
title = {{The crossing number of complete graphs}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/The-crossing-number-of-complete-graphs-September-23-2026/paper.pdf}{OAI:The-crossing-number-of-complete-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 bipartite graphs · September 23, 2026