HEXAGONbeta

Two conjectures of Wormald on Hamilton cycles in tournaments

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatoricsmath.RA — Rings and Algebras

Contributed by Deep Bhattacharjee

Version 1 / Oct 22, 2026 / CC BY 4.0

Abstract

A tournament is a complete graph in which every edge has been given a direction, and a Hamilton cycle in it is a directed cycle through all the vertices. Let h(n)h(n) be the largest number of Hamilton cycles that a tournament on nn vertices can have, and let g(n)=2−n(n−1)!g(n)=2^{-n}(n-1)! be the expected number of Hamilton cycles of a random tournament on nn vertices. Wormald obtained lower bounds for h(n)h(n) by replacing every vertex of a fixed regular tournament TT on dd vertices by a random tournament on nn vertices. The expected number of Hamilton cycles of the result is governed by a number HH, the determinant of the Hessian of a function defined implicitly by TT; the bound is d/H g(dn)\sqrt{d/H}\,g(dn), or e1/dd/H g(dn)e^{1/d}\sqrt{d/H}\,g(dn) when the blocks are regular. Wormald computed HH for a few small tournaments, found that d/Hd/H was the square of a rational number every time, and could not explain it. We prove that H=ddet⁡(d2I+S2)/det⁡(d2I−S2)H=d\det(d^2I+S^2)/\det(d^2I-S^2), where SS is the skew adjacency matrix of TT, so that H≠0H\neq0 and d/H=det⁡(dI−S)/det⁡(dI−iS)\sqrt{d/H}=\det(dI-S)/\det(dI-iS) is a ratio of two positive integers. This is his Conjecture~6. For the cyclic tournament on dd vertices the formula becomes d/H=((d+1)d+(d−1)d)/((d+i)d+(d−i)d)\sqrt{d/H}=\bigl((d+1)^d+(d-1)^d\bigr)/\bigl((d+i)^d+(d-i)^d\bigr), which tends to cosh⁡1/cos⁡1=2.8559578925…\cosh1/\cos1=2.8559578925\ldots as dd grows. This is his Conjecture~2, and it identifies the constant 2.8559582.855958 that he estimated by fitting polynomials; it also explains why the terms in 1/d1/d and 1/d31/d^3 of his fits were nearly zero. We add bounds for d/H\sqrt{d/H} over all regular tournaments on dd vertices, with equality in the lower bound exactly for doubly regular tournaments. Every statement is proved by hand.

Provenance statement

Deep Bhattacharjee chose the problem and directed the work. Claude (Anthropic), through Claude Code, carried out the searches and computations, wrote the checking programs and the Lean 4 proofs and drafted the paper. Settles Wormald's Conjectures 2 and 6. The proofs are written out in the paper; the programs and their outputs are in the release. The author approved the final version. Code and data: release v1.0.0, https://github.com/creelie/Breakthrough-problems-1/releases/tag/v1.0.0.
AI provenance filesAI-PROVENANCE-HEXAGON.md · 1 KB

Tools used

Anthropic
Claude CodeVersion Fable 5.1 Medium

References

  1. I. Adler, N. Alon and S. M. Ross, On the maximum number of Hamiltonian paths in tournaments , Random Structures Algorithms 18 (2001), no. 3, 291--296, 10.1002/rsa.1010 .DOI
  2. N. Alon, The maximum number of Hamiltonian paths in tournaments , Combinatorica 10 (1990), no. 4, 319--324, 10.1007/BF02128667 .DOI
  3. E. Friedgut and J. Kahn, On the number of Hamiltonian cycles in a tournament , Combin. Probab. Comput. 14 (2005), no. 5--6, 769--781, 10.1017/S0963548305006863 .DOI
  4. A. Grzesik, D. Král', L. M. Lovász and J. Volec, Cycles of a given length in tournaments , J. Combin. Theory Ser. B 158 (2023), 117--145, 10.1016/j.jctb.2022.07.007 .DOI
  5. L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci. 12699 , Springer, 2021, 625--635, 10.1007/978-3-030-79876-5_37 .DOI
  6. The mathlib Community, The Lean mathematical library , in: Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), ACM, 2020, 367--381, 10.1145/3372885.3373824 .DOI
  7. K. B. Reid and E. Brown, Doubly regular tournaments are equivalent to skew Hadamard matrices , J. Combin. Theory Ser. A 12 (1972), no. 3, 332--338, 10.1016/0097-3165(72)90098-2 .DOI
  8. T. Szele, Kombinatorikai vizsgálatok az irányított teljes gráffal kapcsolatban , Mat. Fiz. Lapok 50 (1943), 223--256.
  9. N. C. Wormald, Tournaments with many Hamilton cycles , preprint (2004), arXiv:2610.16245 (https://arxiv.org/abs/2610.16245).arXiv

Version history

  1. v1Submitted by Deep BhattacharjeeInitial depositSupersededOct 22, 2026
  2. v2Submitted by Deep BhattacharjeeSubmitted as a new versionCurrentOct 26, 2026