VibeMathedMath problems solved with AI
Sign in

The Harary-Hill conjecture on the crossing number of complete graphs

The crossing number cr(G)\mathrm{cr}(G) is the least number of crossing points in a drawing of GG in the plane, with vertices at distinct points and edges as simple arcs meeting in finitely many proper crossings. Hill's construction (with earlier upper bounds by Guy, 1960) draws KnK_n with Z(n)=14⌊n2⌋⌊n−12⌋⌊n−22⌋⌊n−32⌋Z(n)=\frac14\lfloor\frac n2\rfloor\lfloor\frac{n-1}2\rfloor\lfloor\frac{n-2}2\rfloor\lfloor\frac{n-3}2\rfloor crossings, and Harary and Hill (1963) conjectured that this is optimal. It was verified only for n≤12n\le12 (and reported for n≤14n\le14), for restricted drawing classes, and asymptotically up to a factor of about 0.9860.986. Is cr(Kn)=Z(n)\mathrm{cr}(K_n)=Z(n) for every nn?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Topological graph theory; crossing numbers
Posed by
Frank Harary and Anthony Hill, On the number of crossings in a complete graph (Proc. Edinburgh Math. Soc., 1963); upper bound earlier in Guy (1960)
Year posed
1963
Years open
63y
Solved
2026-09-23
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
55 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Claims cr(Kn)=14⌊n2⌋⌊n−12⌋⌊n−22⌋⌊n−32⌋\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 nn, by a lower bound from signed intersections of cycles and an even-node order detector, plus a matching two-page drawing. Crossings are counted as points, every repeated crossing of an edge pair included. It does NOT address the rectilinear crossing number, the pair crossing number or the odd crossing number, which are different parameters.

What the AI did

The release README says the manuscripts were produced by an unreleased internal OpenAI model, the vast majority by one fixed procedure using on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier results produced by the models. Its named exceptions to that procedure (the Hodge conjecture for CM abelian varieties and the zeta zero-free region work) do not concern this family. The manuscript is credited to OpenAI with no human author named.

Verification

No independent mathematician has checked this yet. Theorem 1.1 was read against the posed problem: cr(Kn)=Z(n)\mathrm{cr}(K_n)=Z(n) for all n≥3n\ge3 under the ordinary point-count convention, with unrestricted vertex positions and edge routes. formalization.yaml lists OAI.Paper170.complete_graph_crossing_number (comparator CompleteCrossing) as the main result. Its statement defines admissible drawings in R2\mathbb R^2 (injective vertices, injective continuous edge paths whose interiors avoid vertices, finitely many crossing points, each locally homeomorphic to two axes, no triple points), counts crossing points, takes the infimum over drawings, and asserts it equals the floor-product formula for n≥3n\ge3. That is the headline claim. Permitted axioms are propext, Quot.sound and Classical.choice. Not rebuilt here. Hebbar and Mangam (2018, Int. J. Eng. Technol.) published earlier claims of both formulas, which the manuscripts cite and treat as upper-bound constructions only.

Sources

Changelog1 change

Discussion