The size of the largest hole in a random graph (Q1210559)

It is shown that almost every random graph with the expected average degree \(c\), where \(c\) is a constant larger than one, contains an induced cycle which goes through a positive fraction of the vertices of the graph. Furthermore, for large \(c\), the length of the longest induced cycle is determined up to a factor of two. A similar result was proved independently by \textit{Stephen W. C. Suen} [J. Comb. Theory, Ser. B 56, No. 2, 250-262 (1992; see the review below)].