Maximum Hamilton-cycle problem for tournaments
For an -vertex tournament , let denote its number of directed Hamilton cycles, and define . Let for a uniformly random -vertex tournament; equivalently, . The conjecture is that there exists a constant such that as .
References
- Tournaments with many Hamilton cycles — arXiv — N. C. Wormald
Source: arXiv
Progress summary
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 Hamilton cycles.
- For triangular tournaments with three transitive parts of order , an explicit construction gives asymptotically 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.