The random graph is one of the simplest models of percolation. It was introduced by Erdos and Renyi in 1956, when they discovered a striking phase transition in its behavior.

Consider N points the vertices of our graph, represented for convenience on the unit circle. Suppose we declare each of the N(N-1)/2 possible edges "open" with a certain probability, p. The resulting graph is called G(N,p).

What Erdos and Renyi discovered in 1956 is the following amazing fact. Suppose p scales like c/N for some positive number c. Then the size of the largest connected component of this graph has very different qualitative behavior according to the value of c. When c<1, it is of order log N. When c=1, it is of order N^(2/3). For c>1, there is a so-called "giant component" whose size is a constant fraction of all vertices of the graph. At the same time, the other components of the graph all have much smaller smizes, of order log N.

In this simulation and all the next two pictures, we have represented the connected component that contains a distinguished vertex (1) in red, and the rest of the graph in blue. Here the value of c is 0.95, just below the critical value. The size of the cluster that contains 1 is 13 in this simulation. (A technical detail: here the graph grows in a dynamic way in a dynamic way, i.e. we have kept the same uniform random numbers for all simulations and kept each edge if the value was less than c/N. As a result, you can think of this model as throwing cN/2 edges successively uniformly at random.)

See the simulation for c=1.