Article contents
On the Number of Hamiltonian Cycles in a Tournament
Published online by Cambridge University Press: 11 October 2005
Abstract
Let $P(n)$ and $C(n)$ denote, respectively, the maximum possible numbers of Hamiltonian paths and Hamiltonian cycles in a tournament on n vertices. The study of $P(n)$ was suggested by Szele [14], who showed in an early application of the probabilistic method that $P(n) \geq n!2^{-n+1}$, and conjectured that $\lim ( {P(n)}/ {n!} )^{1/n}= 1/2.$ This was proved by Alon [2], who observed that the conjecture follows from a suitable bound on $C(n)$, and showed $C(n) <O(n^{3/2}(n-1)!2^{-n}).$ Here we improve this to $C(n)<O\big(n^{3/2-\xi}(n-1)!2^{-n}\big),$ with $\xi = 0.2507$… Our approach is mainly based on entropy considerations.
- Type
- Paper
- Information
- Copyright
- 2005 Cambridge University Press
- 5
- Cited by