On the number of Hamiltonian cycles in a tournament

Ehud Friedgut, Jeffry Kahn

Research output: Contribution to journalArticle

5 Scopus citations

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) ≥ 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) Here we improve this to C(n) with ξ = 0.2507... Our approach is mainly based on entropy considerations.

Original languageEnglish (US)
Pages (from-to)769-781
Number of pages13
JournalCombinatorics Probability and Computing
Volume14
Issue number5-6
DOIs
StatePublished - Nov 1 2005

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On the number of Hamiltonian cycles in a tournament'. Together they form a unique fingerprint.

  • Cite this