The Diameter of Sparse Random Graphs

Source abstract

In this paper we study the diameter of the random graph G ( n , p ), i.e. , the largest finite distance between two vertices, for a wide range of functions p = p ( n ). For p = λ/ n with λ > 1 constant we give a simple proof of an essentially best possible result, with an O p (1) additive correction term. Using similar techniques, we establish two-point concentration in the case that np → ∞. For p =(1 + ε)/ n with ε → 0, we obtain a corresponding result that applies all the way down to the scaling window of the phase transition, with an O p (1/ε) additive correction term whose (appropriately scaled) limiting distribution we describe. Combined with earlier results, our new results complete the determination of the diameter of the random graph G ( n , p ) to an accuracy of the order of its standard deviation (or better), for all functions p = p ( n ). Throughout we use branching process methods, rather than the more common approach of separate analysis of the 2-core and the trees attached to it.