Two conjectures of Wormald on Hamilton cycles in tournaments

Deep Bhattacharjee

Two conjectures of Wormald on Hamilton cycles in tournaments

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

Contributed by Deep Bhattacharjee

Version 2 / 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)

be the largest number of Hamilton cycles that a tournament on

n

vertices can have, and let

g(n)=2^{-n}(n-1)!

be the expected number of Hamilton cycles of a random tournament on

n

vertices. Wormald obtained lower bounds for

h(n)

by replacing every vertex of a fixed regular tournament

T

on

d

vertices by a random tournament on

n

vertices. The expected number of Hamilton cycles of the result is governed by a number

H

, the determinant of the Hessian of a function defined implicitly by

T

; the bound is

\sqrt{d/H}\,g(dn)

, or

e^{1/d}\sqrt{d/H}\,g(dn)

when the blocks are regular. Wormald computed

H

for a few small tournaments, found that

d/H

was the square of a rational number every time, and could not explain it. We prove that

H=d\det(d^2I+S^2)/\det(d^2I-S^2)

, where

S

is the skew adjacency matrix of

T

, so that

H\neq0

and

\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

d

vertices the formula becomes

\sqrt{d/H}=\bigl((d+1)^d+(d-1)^d\bigr)/\bigl((d+i)^d+(d-i)^d\bigr)

, which tends to

\cosh1/\cos1=2.8559578925\ldots

as

d

grows. This is his Conjecture~2, and it identifies the constant

2.855958

that he estimated by fitting polynomials; it also explains why the terms in

1/d

and

1/d^3

of his fits were nearly zero. We add bounds for

\sqrt{d/H}

over all regular tournaments on

d

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. This version is complete and self-contained: every statement is proved by hand, the scope of each result is stated, the only unrefereed sources it depends on are the paper of Wormald that states the conjectures and the two later works named next, and no statement rests on a computer. Two works posted after 14 October 2026 overlap with this one and are acknowledged here. Divoux and Wang (arXiv:2610.23755, 16 October 2026) prove, by a different method, that $h(n)\sim(\cosh1/\cos1)\,g(n)$, which is Wormald's Conjecture~5 and is stronger than the lower bound of Corollary~\ref{cor:hn}; their Proposition~7.1 is used in Section~\ref{sec:intro} for one comparison and nowhere else. Liu and Ye (\url{https://github.com/LStar404/wormald-tournament-conjectures}, first posted 19 October 2026) treat Wormald's Conjectures~1, 2 and~6 independently. The source of this revision is in the repository \url{https://github.com/creelie/Paper_8}, release \texttt{v1.0.0}, archived on Zenodo as \href{https://doi.org/10.5281/zenodo.23659586}{10.5281/zenodo.23659586} (concept \href{https://doi.org/10.5281/zenodo.23659585}{10.5281/zenodo.23659585}), together with programs that recompute the table and the numerical values of the paper.

Tools used

Anthropic: Claude CodeVersion Fable 5.1 Medium

References

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. doi:10.1002/rsa.1010 (https://doi.org/10.1002/rsa.1010).DOI
N. Alon, The maximum number of Hamiltonian paths in tournaments, Combinatorica 10 (1990), no. 4, 319--324. doi:10.1007/BF02128667 (https://doi.org/10.1007/BF02128667).DOI
D. Bhattacharjee, Establishing equivariant class $[O]$ for hyperbolic groups, Asian Res. J. Math. 18 (2022), no. 11, 362--369. doi:10.9734/arjom/2022/v18i11615 (https://doi.org/10.9734/arjom/2022/v18i11615).DOI
D. Bhattacharjee, Non-commutativity over canonical suspension $\eta$ for genus $g\ge1$ in hypercomplex structures for potential $\rho\phi$ , Asian Res. J. Math. 18 (2022), no. 11, 332--341. doi:10.9734/arjom/2022/v18i11607 (https://doi.org/10.9734/arjom/2022/v18i11607).DOI
D. Bhattacharjee, U. Bhattacharya, Iterated nerve complexes for $k$ -fold sensor coverage, Preprints.org (2026). doi:10.20944/preprints202606.1351.v2 (https://doi.org/10.20944/preprints202606.1351.v2).DOI
A. Divoux and S. Wang, The maximum number of Hamiltonian cycles in tournaments, preprint, arXiv:2610.23755 (https://arxiv.org/abs/2610.23755) (2026).arXiv
E. Friedgut and J. Kahn, On the number of Hamiltonian cycles in a tournament, Combin. Probab. Comput. 14 (2005), no. 5--6, 769--781. doi:10.1017/S0963548305006863 (https://doi.org/10.1017/S0963548305006863).DOI
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. doi:10.1016/j.jctb.2022.07.007 (https://doi.org/10.1016/j.jctb.2022.07.007).DOI
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. doi:10.1016/0097-3165(72)90098-2 (https://doi.org/10.1016/0097-3165(72)90098-2).DOI
T. Szele, Kombinatorikai vizsgálatok az irányított teljes gráffal kapcsolatban, Mat. Fiz. Lapok 50 (1943), 223--256.

Show all 11 referencesShow fewer references

N. C. Wormald, Tournaments with many Hamilton cycles, preprint, on the author's web page since 2013; arXiv:2610.16245 (https://arxiv.org/abs/2610.16245) (2026).arXiv

Version history

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