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.