| 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.