The largest hole in sparse random graphs. Issue 4 (25th February 2022) - Draganić, Nemanja; Glock, Stefan; Krivelevich, Michael
Abstract: We show that for any d = d ( n ) with d 0 ( ϵ ) ≤ d = o ( n ), with high probability, the size of a largest induced cycle in the random graph G ( n, d / n ) is ( 2 ± ϵ ) n d log d . This settles a long‐standing open problem in random graph theory.