Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T20:44:17.140Z 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: ehudf@math.huji.ac.il)
JEFF KAHN
Affiliation:
Department of Mathematics and RUTCOR, Rutgers University, New Brunswick NJ 08854, USA (e-mail: jkahn@math.rutgers.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Copyright
2005 Cambridge University Press