Preprint
Sep 2026
Long induced cycles in pseudorandom graphs
We show that, for some absolute constants $c_1,c_2>0$, every $(n,d,\lambda)$-graph with $\lambda\le c_1 d$ contains an induced cycle of length at least $c_2n\log(d/\lambda)/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 explorat...
Sahar Diskin, Lyuben Lichev, Michael Krivelevich et al.
· 1 citation