Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Powers of Hamiltonian cycles in randomly augmented graphs

Mathias Schacht, Yale

Location:  Hill 705
Date & time: Monday, 26 November 2018 at 2:00PM - 3:00PM

Abstract:  We study the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. It follows from the theorems of Dirac and of Komlós, Sarközy, and Szemerédi that for every \(k\) and sufficiently large \(n\) already the minimum degree \(geq frac{k}{k-1}n\) for an \(n\)-vertex graph \(G\) alone suffices to ensure the existence of a \(k\)-th power of a Hamiltonian cycle. We show that under essentially the same degree assumption the addition of just \(O(n)\) random edges ensures the presence of the \((k+1)\)-st power of a Hamiltonian cycle with probability close to one.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.