The Crossing Number of the Complete Graph
OPG_crossing_number_complete_graph_harary_hill
Source: Open Problem Garden: the_crossing_number_of_the_complete_graph
Status ai-proved high confidence
OpenAI's manuscript proves the Harary–Hill formula $\mathrm{cr}(K_n) = \frac14\lfloor\frac n2\rfloor\lfloor\frac{n-1}2\rfloor\lfloor\frac{n-2}2\rfloor\lfloor\frac{n-3}2\rfloor$ for every $n$: the classical drawings are optimal.
Cited literature (5)
-
Proves that the 2-page crossing number of $K_n$ equals $Z(n)$, confirming Hill's conjecture for the 2-page drawing model.
-
Proves the Harary-Hill conjecture for all shellable drawings (including cylindrical, x-bounded, monotone, and 2-page drawings), settling the conjecture for these drawing classes.
-
Rules out $\mathrm{cr}(K_{13}) = 217$, narrowing the possible values to $\{219, 221, 223, 225\}$ and advancing the verification program toward $n = 13$.
-
Using flag algebras, proves that $\mathrm{cr}(K_n) > 0.985\,H(n)$ for all sufficiently large $n$, substantially improving the prior best asymptotic lower bound of $0.83\,H(n)$.
-
Provides a very general construction (including random configurations on a sphere) showing that many distinct drawing families achieve the Hill upper bound $H(n)$, without establishing it as a lower bound.
Reviewer notes. Literature status before this model-generated claim: partial. Hill's conjecture that $\mathrm{cr}(K_n) = \frac{1}{4}\lfloor n/2\rfloor\lfloor(n-1)/2\rfloor\lfloor(n-2)/2\rfloor\lfloor(n-3)/2\rfloor$ remains open in general. Since 2007, the conjecture has been proved for all 2-page, cylindrical, and shellable drawings by Ábrego et al., and Balogh, Lidický, and Salazar established via flag algebras that $\mathrm{cr}(K_n) > 0.985\,H(n)$ for all sufficiently large $n$, substantially improving the previously known $0.83\,H(n)$ lower bound. The exact value of $\mathrm{cr}(K_{13})$ remains unknown, narrowed to $\{219, 221, 223, 225\}$.
OpenAI manuscript collection ai-proved
- The crossing number of complete graphs — main result formalized in Lean by OpenAI
Family 165: The Harary–Hill and Zarankiewicz crossing-number formulas · Lean formalization scope
These manuscripts were produced by an unreleased OpenAI model and released on
2026-10-06 in github.com/openai/math.
They have not been peer reviewed. Lean formalizations are OpenAI's own and cover
only the scope stated on their scope page; this project has not run or reviewed them.
The status above records the claim; before it, the literature review rated this
entry partial. Its confidence rates
whether the manuscript's theorem settles this entry, not whether the manuscript
is correct.
Discussion
(This discussion appears as [M].) A drawing of a graph $ G $ in the plane has the vertices represented by distinct points and the edges represented by polygonal lines joining their endpoints such that: \item no edge contains a vertex other than its endpoints, \item no two adjacent edges share a point other than their common endpoint, \item two nonadjacent edges share at most one point at which they cross transversally, and \item no three edges cross at the same point. The conjectured value for the crossing number of $ K_n $ is known to be an upper bound. This is shown by exhibiting a drawing with that number of crossings. If $ n = 2m $ , place $ m $ vertices regularly spaced along two circles of radii 1 and 2, respectively. Two vertices on the inner circle are connected by a straight line; two vertices on the outer circle are connected by a polygonal line outside the circle. A vertex on the inner circle is connected to one on the outer circle with a polygonal line segment of minimum possible positive winding angle around the cylinder. A simple count shows that the number of crossings in such a drawing achieves the conjectured minimum. For $ n = 2m-1 $ we delete one vertex from the drawing described and achieve the conjectured minimum. The conjecture is known to be true for $ n $ at most 10 [G]. If the conjecture is true for $ n = 2m $ , then it is also true for $ n-1 $ . This follows from an argument counting the number of crossings in drawings of all $ K_{n-1} $ 's contained in an optimal drawing of $ K_n $ . It would also be interesting to prove that the conjectured upper bound is asymptotically correct, that is, that $ \lim \frac{cr(K_n)}{\binom{n}4} = \frac38 $ . The best known lower bound is due to Kleitman [K], who showed that this limit is at least $ 3/10 $ .
Bibliography
-
[G]R. Guy, The decline and fall of Zarankiewicz's theorem, in Proof Techniques in Graph Theory (F. Harary Ed.), Academic Press, New York (1969) 63-69. -
[K]D. Kleitman, The crossing number of $ K_{5,n} $ , J. Combin. Theory 9 (1970) 315-323. -
[M]B. Mohar, Problem of the Month Problem of the Month