Mathematics – Probability
Scientific paper
2008-08-29
Combinatorics, Probability and Computing 19 (2010), 835--926
Mathematics
Probability
92 pages; expanded slightly with minor corrections; to appear in Combinatorics, Probability and Computing
Scientific paper
10.1017/S0963548310000325
In this paper we study the diameter of the random graph $G(n,p)$, i.e., the the largest finite distance between two vertices, for a wide range of functions $p=p(n)$. For $p=\la/n$ with $\la>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 2-point concentration in the case that $np\to\infty$. For $p=(1+\epsilon)/n$ with $\epsilon\to 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/\epsilon)$ 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.
Riordan Oliver
Wormald Nicholas
No associations
LandOfFree
The diameter of sparse random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The diameter of sparse random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The diameter of sparse random graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-542871