Long induced cycles in pseudorandom graphs

Abstract

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_{2}n\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 exploration procedure, a link to percolation theory, and estimates for random row-and-column extraction in symmetric matrices.