a1 Department of Mathematics, Rutgers University, Piscataway, NJ08854, USA (e-mail: [email protected])
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  and providing a partial answer to a question of Friedgut and Kahn . 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)