Long cycles in percolated expanders

Maurício Collares, Sahar Diskin, Joshua Erde, Michael Krivelevich

Research output: Working paperPreprint

Abstract

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}$ and constants $00$, we show that if every subset $S\subseteq V(G)$ of size exactly $\frac{c|V(G)|}{d}$ satisfies $|N(S)|\ge d|S|$ and $p=\frac{1+\varepsilon}{d}$, 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}$ and a constant $\varepsilon>0$, if every subset $S\subseteq V(G)$ of size exactly $k$ satisfies $|N(S)|\ge kd$ and $p=\frac{1+\varepsilon}{d}$, 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.
Original languageEnglish
Publication statusPublished - 16 Jul 2024

Keywords

  • math.CO
  • math.PR

Fingerprint

Dive into the research topics of 'Long cycles in percolated expanders'. Together they form a unique fingerprint.

Cite this