Computer Science/Discrete Mathematics Seminar I

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.