Talk information

Date: Sunday, May 11, 2025
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Maksim Zhukovskii (University of Sheffield)
Title: The sharp threshold for the square of a Hamilton cycle

Abstract:

In 2020, Kahn, Narayanan and Park conjectured that the probability threshold for the binomial random graph $G(n,p)$ to contain the square of a Hamilton cycle is $(1+o(1))\sqrt{e/n}$. In the talk, I will present a proof of this conjecture. Although the proof relies on the fragmentation technique, as the original proof by Kahn, Narayanan and Park for establishing a coarse threshold, the way of selecting fragments is essentially different. One of the main ingredients of the proof is the fact that sufficiently many squares of cycles have fragments that avoid squares of paths of logarithmic (in $n$) length with high probability.