PreprintCC BY 4.0arXiv
Long induced cycles in pseudorandom graphs
Abstract
We show that, for some absolute constants c1,c2>0, every (n,d,λ)-graph with λ≤ c1 d contains an induced cycle of length at least c2nlog(d/λ)/d. This is best possible up to the values of c1,c2. Our techniques include a multi-scale algorithmic analysis, an adapted depth-first exploration procedure, a link to percolation theory, and estimates for random row-and-column extraction in symmetric matrices.
Related
BibTeX
@misc{diskin2026long,
title = {{Long induced cycles in pseudorandom graphs}},
author = {Sahar Diskin and Lyuben Lichev and Michael Krivelevich and Itay Markbreit},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06176},
eprint = {2609.06176},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.06176},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Long induced cycles in pseudorandom graphs
AU - Sahar Diskin
AU - Lyuben Lichev
AU - Michael Krivelevich
AU - Itay Markbreit
PY - 2026
DA - 2026/09/05
PB - arXiv
DO - 10.48550/arxiv.2609.06176
UR - https://arxiv.org/abs/2609.06176
AB - We show that, for some absolute constants c_1,c_2>0, every (n,d,λ)-graph with λ≤ c_1 d contains an induced cycle of length at least c_2nlog(d/λ)/d. This is best possible up to the values of c_1,c_2. Our techniques include a multi-scale algorithmic analysis, an adapted depth-first exploration procedure, a link to percolation theory, and estimates for random row-and-column extraction in symmetric matrices.
ER -