{"id":"arxiv/2609.06176","url":"https://arxiv.org/abs/2609.06176","tags":["math.CO"],"score":0,"title":"Long induced cycles in pseudorandom graphs","domain":"math.CO","source":"arxiv","authors":["Sahar Diskin","Lyuben Lichev","Michael Krivelevich","Itay Markbreit"],"reviews":0,"subject":"math.CO","summary":"We show that, for some absolute constants $c_1,c_2>0$, every $(n,d,λ)$-graph with $λ\\le c_1 d$ contains an induced cycle of length at least $c_2n\\log(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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-05","reactions":{}}