Abstract

Hamiltonian Cycles in Regular Tournaments

Bill Cuckler
Mon May 3 at 1:10pm in the Graduate Student Lounge

A tournament is a complete, oriented graph. Szele showed in what is considered the first application of the probabilistic method in combinatorics (1943) that there exists a tournament on n vertices with (n-1)!/2^n Hamiltonian cycles. Alon showed in 1990 that this bound is close to optimal by showing that all tournaments on n vertices have at most O(n^{3/2}(n-1)!/2^n) Hamiltonian cycles. This bound was recently improved by Friedgut and Kahn, and they posed the question of a lower bound on the number of Hamiltonian cycles in regular tournaments (a tournament is called regular if the outdegrees of all vertices are the same). I will provide a partial answer to the question by showing that any regular tournament on n vertices has at least n!/(2+o(1))^n Hamiltonian cycles. Thus, the number of Hamiltonian cycles in any regular tournament is determined to within a sub-exponential factor. A key ingredient of the proof is a martingale analysis of self-avoiding walks on a regular tournament.