Combinatorics, Probability and Computing

Paper

Hamiltonian Cycles in Regular Tournaments

BILL CUCKLERa1

a1 Department of Mathematics, Rutgers University, Piscataway, NJ08854, USA (e-mail: cuckler@math.rutgers.edu)

Abstract

We show that every regular tournament on n vertices has at least n!/(2 + o(1))n Hamiltonian cycles, thus answering a question of Thomassen [17] and providing a partial answer to a question of Friedgut and Kahn [7]. This compares to an upper bound of about O(n0.25n!/2n) for arbitrary tournaments due to Friedgut and Kahn (somewhat improving Alon's bound of O(n0.5n!/2n)). A key ingredient of the proof is a martingale analysis of self-avoiding walks on a regular tournament.

(Received December 08 2004)

(Revised July 03 2006)