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
Abstract 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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom