Long cycles in percolated expanders

Maurício Collares¹ ; Sahar Diskin² ; Joshua Erde¹ ; Michael Krivelevich³

¹Institute of Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria
²Tel-Aviv University, Israel
³School of Mathematical Sciences, Tel Aviv University, Tel Aviv 6997801, Israel

The electronic journal of combinatorics, Tome 32 (2025) no. 1

Résumé

Given a graph $G$ and probability $p$, we form the random subgraph $G_p$ by retaining each edge of $G$ independently with probability $p$. Given $d\in\mathbb{N}$, constants $0<c<1, \varepsilon>0$0$, and $p=\frac{1+\varepsilon}{d}$, we show that if every subset $S\subseteq V(G)$ of size exactly $\frac{c|V(G)|}{d}$ satisfies $|N(S)|\ge d|S|$, then the probability that $G_p$ does not contain a cycle of length $\Omega(\varepsilon^2c^2|V(G)|)$ is exponentially small in $|V(G)|$. As an intermediate step, we also show that given $k,d\in \mathbb{N}$, a constant $\varepsilon>0$, and $p=\frac{1+\varepsilon}{d}$, if every subset $S\subseteq V(G)$ of size exactly $k$ satisfies $|N(S)|\ge kd$, then the probability that $G_p$ does not contain a path of length $\Omega(\varepsilon^2 kd)$ is exponentially small. We further discuss applications of these results to $K_{s,t}$-free graphs of maximal density.

Détail

DOI : 10.37236/13219

Classification : 05C80, 05D40, 05C38, 60C05
Mots-clés : Galton-Watson branching process, depth-first search algorithm