Long induced cycles in pseudorandom graphs

Sahar Diskin, Lyuben Lichev, Michael Krivelevich, Itay Markbreit

arXivarxiv/2609.06176Sep 5, 2026math.COscore 0

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.

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.06176
curl -X POST /api/v1/records/arxiv/2609.06176/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.06176/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'