### 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 language | English (US) |
---|---|

Pages (from-to) | 769-781 |

Number of pages | 13 |

Journal | Combinatorics Probability and Computing |

Volume | 14 |

Issue number | 5-6 |

DOIs | |

State | Published - 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

Friedgut, E., & Kahn, J. (2005). On the number of Hamiltonian cycles in a tournament.

*Combinatorics Probability and Computing*,*14*(5-6), 769-781. https://doi.org/10.1017/S0963548305006863