2 - Erdös–Rényi Random Graphs

Summary

In this chapter we will introduce and study the random graph model introduced by Erdös and Rényi in the late 1950s. This example has been extensively studied and a very nice account of many of the results can be found in the classic book of Bollobás (2001), so here we will give a brief account of the main results on the emergence of a giant component, in order to prepare for the analysis of more complicated examples. In contrast to other treatments, we mainly rely on methods from probability and stochastic processes rather than combinatorics.

To define the model, we begin with the set of vertices V = {1, 2, … n}. For 1 ≤ x < y ≤ n let η_x,y be independent = 1 with probability p and 0 otherwise. Let η_y,x = η_x,y. If η_x,y = 1 there is an edge from x to y. Here, we will be primarily concerned with situation p = λ/n and in particular with showing that when λ < 1 all of the components are small, with the largest O(log n), while for λ > 1 there is a giant component with ~ g(λ)n vertices. The intuition behind this result is that a site has a Binomial(n – 1, λ/n) number of neighbors, which has mean ≈ λ.