Short··0:40·Combinatorics
The Harary–Hill Conjecture: Why 18 Dots Need 1008 Crossings
Watch on YouTubeRead the write-up →
About this video
Join every dot to every other dot. How few times must the lines cross?
The Harary–Hill conjecture (Guy, Harary and Hill, early 1960s) says the minimum number of crossings for the complete graph Kₙ is
Z(n) = ¼ ⌊n/2⌋ ⌊(n−1)/2⌋ ⌊(n−2)/2⌋ ⌊(n−3)/2⌋.
Classical drawings reach that number, but for more than 60 years nobody could prove that nothing does better (it was known only up to n = 12).
OpenAI reports a proof (September 2026) that the classical drawings are optimal, so the formula is exact for every n, with a matching result for Zarankiewicz's bipartite problem. The paper has not been independently reviewed yet; treat it as OpenAI's claim.
What you're watching: the classical two-page drawing on a sphere, built from K5 (1 crossing) up to K18 (1008 crossings). Every gold dot is a real crossing of that drawing, and every chime you hear is one of those crossings. The animation illustrates the result; it is not the proof.
Paper: github.com/openai/math/blob/main/preprints/The-crossing-numbe…
About the problem
Combinatorics·OpenAI Math·Result 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. (Lean)
Topics
crossing numberHarary-Hill conjectureHill's conjectureGuy's conjecturecrossing number of complete graphscomplete graphK18Zarankiewicz problemgraph theorygraph drawingtwo-page drawingOpenAI mathOpenAI proofAI math proofAI solves math problemunsolved math problemscombinatoricsmath visualizationmath animationthree.jsGradient Damage
