Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, October 3, 2006 - 4:00pm

Bill Cuckler

University of Delaware

Location

University of Pennsylvania

4N30

A graph is said to be Dirac if its minimum degree is at least n/2; this is in honor of the seminal 1952 result of Dirac proving that any such graph has a Hamiltonian cycle. We show that any Dirac graph has at least n!/(2+o(1))^n Hamiltonian cycles, which confirms a conjecture of G. Sarkozy, S. Selkow, and E. Szemeredi. We also mention that the number of Hamiltonian cycles in a Dirac graph is determined to within a subexponential factor by a simple parameter, the "entropy" of the graph. Joint with Jeff Kahn.