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 , who showed in an early application of the probabilistic method that P(n) ≥ n!2-n+1, and conjectured that lim(P(n)/n!)1/n= 1/2. This was proved by Alon , who observed that the conjecture follows from a suitable bound on C(n), and showed C(n) Here we improve this to C(n) with ξ = 0.2507... Our approach is mainly based on entropy considerations.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics