Andrzej Dudek : Powers of Hamiltonian cycles in randomly augmented graphs

Posted by Dhruv Mubayi , part of the Mathematical Computer Science Seminar.

At

April 29, 2019, 3 p.m.

In

427 SEO

Abstract

It follows from the theorems of Dirac and of Koml\'os, Sark\"ozy, and Szemer\'edi, who confirmed the Pos\'a-Seymour conjecture, that for every $k\ge 1$ and sufficiently large $n$ already the minimum degree $\delta(G) \ge \frac{k}{k+1} n$ for an $n$-vertex graph $G$ alone suffices to ensure the existence of the $k$-th power of a Hamiltonian cycle. In this talk we will determine the number of random edges one has to add to a graph $G$ with minimum degree $\delta(G) \ge \left(\frac{k}{k+1} +\varepsilon\right)n$ (with $\varepsilon>0$) in order to create an $\ell$-th power of a Hamiltonian cycle, where $\ell\ge k+1$. This is joint work with Sylwia Antoniuk, Christian Reiher, Andrzej Ruci\'nski and Mathias Schacht.