Many Hamiltonian Cycles

Thursday, May 4, 2006 - 11:00am
Skiles 255
Jeff Kahn
Mathematics, Rutgers University

We'll begin with the following theorem, which proves a conjecture of Sarkozy, Selkow and Szemeredi, and try to use it as an excuse to talk about other things (e.g., Bregman's Theorem, entropy, the "incremental random method," statistics 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.

Joint with Bill Cuckler.