Talk information

Date: Sunday, March 30, 2025
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Sahar Diskin (Tel Aviv University)
Title: Long cycle in the percolated cube

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 $\varepsilon>0$, there exists a constant $C=C(\varepsilon)>0$ such that if $p>C/d$, then $Q^d_p$ typically contains a cycle of length at least $(1-\varepsilon)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 $\varepsilon>0$, there exists a constant $C=C(\varepsilon)>0$ such that $G(n,C/n)$ typically contains a cycle of length at least $(1-\varepsilon)n$.

Joint work with Michael Anastos, Joshua Erde, Mihyun Kang, Michael Krivelevich and Lyuben Lichev.