Long cycles in percolated expanders

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\), if every subset \(S\subseteq V(G)\) of size exactly \(k\) satisfies \(|N(S)|\ge kd\) and \(p=\frac{1+\va...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-07
Main Authors: Collares, Maurício, Diskin, Sahar, Erde, Joshua, Krivelevich, Michael
Format: Article
Language:English
Subjects:
Expanders
Graph theory
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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\), 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.
ISSN:2331-8422