Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 21 min ago
PreprintarXiv licencearXiv

The maximum number of Hamiltonian cycles in tournaments

  • Alexander Divoux
  • Shouda Wang
Open at sourcePDFDOICite

Abstract

Let C(n) denote the maximum number of directed Hamiltonian cycles in a tournament on n vertices. We prove that, as n→∞, C(n) = ((cosh 1)/(cos 1)± o(1))((n−1)!)/2n. The bound is asymptotically attained by the regular tournament with vertices ℤ/nℤ where (i,j) is a directed edge if j − i pmod n< n/2. This answers a question of Alon and proves a conjecture of Wormald. Among the other implications of these results is asymptotically determining the maximum number of Hamiltonian paths in a tournament on n vertices. We provide our own exposition of these proofs, which were originally found by GPT-5.6.

Related

  1. On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
    Chengli Li, Feng Liu
    The Electronic Journal of CombinatoricsPeer-reviewedCC BY 4.0Full textCombinatorics & discrete mathematicsCrossref
  2. On the Number of Hamiltonian Cycles in a Boolean Cube
    A. L. Perezhogin, V. N. Potapov
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. On the maximum number of triangles in tripartite graphs with no $4$-cycles between any two parts
    Chunqiu Fang, Rongxing Xu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Bounds on the maximum number of limit cycles of piecewise linear Lienard systems II. The discontinuous case
    Hebai Chen, Jie Jin, Shu Li +1
    arXivPreprintarXiv licenceFull textAnalysis & PDEsDynamical systemsarXiv
  5. Bounds on the maximum number of limit cycles of piecewise linear Lienard systems I. The continuous case
    Shiyu Cai, Hebai Chen, Jie Jin +1
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{divoux2026maximum,
  title = {{The maximum number of Hamiltonian cycles in tournaments}},
  author = {Alexander Divoux and Shouda Wang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.23755},
  eprint = {2610.23755},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.23755},
}
RIS
TY  - UNPB
TI  - The maximum number of Hamiltonian cycles in tournaments
AU  - Alexander Divoux
AU  - Shouda Wang
PY  - 2026
DA  - 2026/10/16
PB  - arXiv
DO  - 10.48550/arxiv.2610.23755
UR  - https://arxiv.org/abs/2610.23755
AB  - Let C(n) denote the maximum number of directed Hamiltonian cycles in a tournament on n vertices. We prove that, as n→∞, C(n) = ((cosh 1)/(cos 1)± o(1))((n−1)!)/2^n. The bound is asymptotically attained by the regular tournament with vertices ℤ/nℤ where (i,j) is a directed edge if j − i pmod n< n/2. This answers a question of Alon and proves a conjecture of Wormald. Among the other implications of these results is asymptotically determining the maximum number of Hamiltonian paths in a tournament on n vertices. We provide our own exposition of these proofs, which were originally found by GPT-5.6.
ER  -