The largest hole in sparse random graphs

Abstract

We show that for any $d=d(n)$ with $d_0(\epsilon )\le d=o(n)$, with high probability, the size of a largest induced cycle in the random graph $G(n,d/n)$ is $(2\pm \epsilon )\frac{n}{d}\log d$. This settles a long-standing open problem in random graph theory.

arXiv commentto appear in RSA. arXiv admin note: substantial text overlap with arXiv:2102.09289