Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-25T08:36:51.128Z Has data issue: false hasContentIssue false

On the Number of Hamiltonian Cycles in a Tournament

Published online by Cambridge University Press:  11 October 2005

EHUD FRIEDGUT
Affiliation:
Institute of Mathematics, Hebrew University, Jerusalem, Israel (e-mail: [email protected])
JEFF KAHN
Affiliation:
Department of Mathematics and RUTCOR, Rutgers University, New Brunswick NJ 08854, USA (e-mail: [email protected])

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
Copyright
2005 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)