Many Hamiltonian Cycles

COMPUTER SCIENCE/DISCRETE MATH I
Topic:Many Hamiltonian Cycles
Speaker:Jeff Kahn
Affiliation:Rutgers University
Date:Monday, May 1
Time/Room:11:15am - 12:15pm/S-101

We'll begin with the following theorem, which proves a conjecture of S\'ark\"ozy, Selkow and Szemer\'edi, and try to use it as an excuse to talk about other things (perhaps including Br\'egman's Theorem, entropy, the ``incremental random method," statistical physics...). Theorem. Any n-vertex Dirac graph (i.e. graph of minimum degree at least $n/2$) contains at least $(2-o(1))^{-n}n!$ Hamiltonian cycles.