Long cycle in the percolated cube
Organizer
Benjamin Sudakov
Speaker
Sahar Diskin
Time
Tuesday, February 25, 2025 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
The (binary) $d$-dimensional hypercube is the graph whose vertex set is $\{0,1\}^d$, and an edge is drawn between every two vertices/vectors if their Hamming distance is one. Considering the percolated hypercube $Q^d_p$, where every edge of $Q^d$ is retained independently and with probability $p$, we show the following. For every $\epsilon>0$, there exists a constant $C=C(\epsilon)>0$ such that if $p>C/d$, then $Q^d_p$ typically contains a cycle of length at least $(1-\epsilon)2^d$.
This confirms a long-standing folklore conjecture, and answers in a strong form a question of Condon, Espuny Díaz, Girão, Kühn, and Osthus from 2024. This can be seen as an analogue of the classical result of Ajtai, Komlós, and Szemerédi and of Fernandez de la Vega, who showed that for every $\epsilon>0$, there exists a constant $C=C(\epsilon)>0$ such that $G(n,C/n)$ typically contains a cycle of length at least $(1-\epsilon)n$.
Joint work with Michael Anastos, Joshua Erde, Mihyun Kang, Michael Krivelevich and Lyuben Lichev.
This confirms a long-standing folklore conjecture, and answers in a strong form a question of Condon, Espuny Díaz, Girão, Kühn, and Osthus from 2024. This can be seen as an analogue of the classical result of Ajtai, Komlós, and Szemerédi and of Fernandez de la Vega, who showed that for every $\epsilon>0$, there exists a constant $C=C(\epsilon)>0$ such that $G(n,C/n)$ typically contains a cycle of length at least $(1-\epsilon)n$.
Joint work with Michael Anastos, Joshua Erde, Mihyun Kang, Michael Krivelevich and Lyuben Lichev.
Speaker Intro
Sahar Diskin is a PhD student at Tel Aviv University, under the supervision of Prof. Michael Krivelevich. His key research interests are in probabilistic combinatorics, and in particular percolation on finite graphs.