Premium
The largest hole in sparse random graphs
Author(s) -
Draganić Nemanja,
Glock Stefan,
Krivelevich Michael
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21078
Subject(s) - random graph , combinatorics , mathematics , random regular graph , dense graph , discrete mathematics , graph , line graph , 1 planar graph
We show that for any d = d ( n ) withd 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.