Combinatorics, Probability and Computing



The Maximum Degree of a Random Graph


OLIVER RIORDAN a1 and ALEX SELBY a2
a1 Trinity College, Cambridge CB2 1TQ, England
a2 Department of Pure Mathematics and Mathematical Statistics, 16 Mill Lane, Cambridge CB2 1SB, England

Abstract

Let 0 < p < 1, q = 1 − p and b be fixed and let G [set membership] [script G](n, p) be a graph on n vertices where each pair of vertices is joined independently with probability p. We show that the probability that every vertex of G has degree at most pn + b [surd radical]npq is equal to (c + o(1))n, for c = c(b) the root of a certain equation. Surprisingly, c(0) = 0.6102 … is greater than [fraction one-half] and c(b) is independent of p. To obtain these results we consider the complete graph on n vertices with weights on the edges. Taking these weights as independent normal N(p, pq) random variables gives a ‘continuous’ approximation to [script G](n, p) whose degrees are much easier to analyse.

(Received April 21 1999)
(Revised March 30 2000)