The largest hole in sparse random graphs

2021/05/28 by Nemanja Draganić, Stefan Glock, Draganić, Nemanja +3 · 2 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2106.00597

Abstract

We show that for any d=d(n) with d₀(ε) ≤ 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.

Cited by

• Concentration of the maximum size of an induced subtree in moderately sparse random graphs
• A large hole in pseudo-random graphs

Related

• A large hole in pseudo-random graphs
• Cycle lengths in sparse random graphs
• Longest cycles in sparse random digraphs
• Large induced trees in dense random graphs
• Note on induced paths in sparse random graphs