← All problems

Maximum Hamilton-cycle problem for tournaments

For an nn-vertex tournament TT, let H(T)H(T) denote its number of directed Hamilton cycles, and define h(n)=max⁡TH(T)h(n)=\max_T H(T). Let g(n)=E[H(T)]g(n)=\mathbb{E}[H(T)] for a uniformly random nn-vertex tournament; equivalently, g(n)=(n−1)!2ng(n)=\frac{(n-1)!}{2^n}. The conjecture is that there exists a constant c≈2.855958c\approx 2.855958 such that h(n)∼c g(n)h(n)\sim c\,g(n) as n→∞n\to\infty.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A new construction raises the known lower bound for how many full loops a tournament can contain, but the conjectured best possible value remains unknown.

The problem asks for the maximum possible number of Hamilton cycles in a tournament and for the structure of tournaments attaining the asymptotic optimum. The conjectured constant and extremal characterization remain open.

Known results

  • Szele obtained a probabilistic lower bound for Hamilton paths.
  • Wormald analyzed triangular tournaments whose three parts are random.
  • Cuckler proved that every regular tournament has at least n!(2+o(1))n\frac{n!}{(2+o(1))^n} Hamilton cycles.
  • For triangular tournaments with three transitive parts of order n/3n/3, an explicit construction gives asymptotically 11−log⁡2(n−1)!(3log⁡2)n\frac{1}{1-\log 2}\frac{(n-1)!}{(3\log 2)^n} Hamilton cycles.

October 2026 lower-bound improvement

N. C. Wormald's Tournaments with many Hamilton cycles, reported on October 12, 2026, uses expected counts in several random tournament classes to improve the lower-bound factor. This is claimed progress toward the conjectured optimum, not a solution of the maximum problem.

Current status (as of October 2026): Improved lower bounds are reported, while the conjectured asymptotic constant and extremal characterization remain open.

Sources

Solutions 0

No solutions have been posted yet.