Tournament Hamiltonian cycles: GPT-5.6 settles Alon’s question
Event confirmedAwaiting review
Importance: major (4 of 5)The takeaway
Princeton’s Divoux and Wang asked GPT-5.6 for a lower bound; a second instance turned the method into the matching upper bound, closing a line of work that runs from Szele’s 1943 paper through Alon (1990) and Friedgut–Kahn.
Status
- Claim
Event confirmedAwaiting review
- Our reporting
- High confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 19 October 2026
Your AI and this story
- GPT-6 Astra169 days after its cutoff
- Claude Opus 5.5108 days after its cutoff
- Gemini 4 Argon199 days after its cutoff
- Grok 4.7138 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 108 days before it.
Key facts
- Paper: Alexander Divoux and Shouda Wang, ‘The maximum number of Hamiltonian cycles in tournaments’, arXiv 2610.23755 [math.CO], submitted 16 Oct 2026, ~48 pp.
- Main theorem: C(n) = (cosh 1 / cos 1 ± o(1))·(n−1)!/2ⁿ as n → ∞; extremal example: vertices Z/nZ, edge i→j iff j − i mod n < n/2
- History (paper): Szele (1943) gave P(n) ≥ n!/2^(n−1), often called the first use of the probabilistic method, and an upper bound P(n) = O(n!·2^(−3n/4)); Alon (1990) C(n) = O(n^(3/2)(n−1)!/2ⁿ); Friedgut–Kahn O(n^α(n−1)!/2ⁿ), α ≈ 1.249; Adler–Alon–Ross C(n) ≥ (e − o(1))(n−1)!/2ⁿ; Wormald conjectured the regular cyclic tournament is extremal
- The constant cosh 1/cos 1 was first guessed from numerics by Jay Pantone’s computer program and communicated to Alon (acknowledgments)
- AI role (acknowledgments): ‘A proof was found by GPT-5.6 following some strategies supplied by the authors (the relevant one being a suggestion to search hard for suitable permanent estimates). In a surprising turn of events, after being input this proof and a few hopeful ideas, a separate instance of GPT-5.6 was able to generalize its techniques into an argument for the matching upper bound’
- Human role: ‘Many of the arguments were eventually replaced or simplified by the authors, and others originally came from the literature. The content of the present paper was written by the authors.’ Noga Alon is thanked ‘for many helpful discussions and comments’
- Same pair (with Lowen) disproved Rota’s 1970 matroid unimodality conjecture with ChatGPT 5.6 Pro in July (Rota’s 1970 unimodality conjecture for matroid flats disproved, with ChatGPT 5.6 Pro suggesting a key construction)
- No Hacker News thread or high-reach X post found on 19 Oct morning
What happened
A tournament is a complete graph with every edge given a direction. Counting directed Hamiltonian cycles in tournaments is one of the oldest problems in probabilistic combinatorics. Szele’s 1943 bound is often called the first application of the probabilistic method, and the maximum has been pinned down only up to polynomial factors since Alon’s 1990 paper. Numerics by Jay Pantone suggested the constant cosh 1/cos 1.
Divoux and Wang first tried to prove the conjectured lower bound for the cyclic tournament, since it “seemed promising for AI models to tackle”. GPT-5.6 did this with permanent estimates. A second GPT-5.6 instance, given the proof, extended the technique to the upper bound for every tournament, which settles the asymptotics. The paper is the authors’ own exposition, and they replaced or simplified many of the model’s arguments.
Why it matters
The result closes a classic extremal question from the start of the probabilistic method, and the authors say both directions of the proof came from the model. The upper bound, the harder direction, was a generalization the authors had not expected (“in a surprising turn of events”).
What is disputed or not yet verified
| Verification | Unrefereed arXiv preprint; human-written exposition of the AI proofs |
|---|
Sources
1 source from 1 site. Numbers match the chips in the text.
1 source: 1 primary
Primary
Changes
- Filed (PDF read)