Long cycle in the percolated cube
组织者
本杰明·苏达科夫
演讲者
Sahar Diskin
时间
2025年02月25日 17:05 至 18:15
地点
Online
线上
Zoom 787 662 9899
(BIMSA)
摘要
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.
演讲者介绍
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.