From Erdos-Renyi to Achlioptas: The Birth of a Giant

Abstract

In this paper, I give an exposition on the emergence of the giant component, the sudden appearance of a component of order Θ(n) beyond a critical threshold in random graph processes. Drawing from the language of statistical mechanics, mathematicians and physicists have referred to this dramatic qualitative change as a “phase transition” in the random graph process. Starting from giving an account of Bollobas’ ([9]) detailed analysis of the phase transition result in Erdos-Renyi case, I move onto Achlioptas processes, a generalization of Erdos-Renyi graphs. In contrast to the original Erdos-Renyi process which randomly adds edges to the graph, the Achlioptas process draws a number of random edges, and selects one to add to the graph based on a rule depending on the component size of their endpoints. By the accumulation of these choices, the resulting graph may display different qualitative features, an example of the “power of two choices” paradigm([20]). However, as shown by Riordan and Warnke [25], despite the potential generality of the edge-selection rule, bounded-size Achlioptas processes exhibit an “Erdos-Renyi” type phase transition: locally, they have asymptotically similar component size distributions, and globally, their largest component becomes Θ(n) and grows linearly beyond criticality. Hence, bounded-size Achlioptas processes constitute a “universality class” for the Erdos-Renyi process, with respect to its phase transition behavior. To explain their proof of this striking result, I first give an account of the techniques of branching process theory and the differential equation method. These techniques are of independent interest, as they are widely applicable in the analysis of discrete random processes. After giving the relevant background, I conclude by giving an exposition of the proof by Riordan and Warnke, highlighting the interplay between the exploration process on the random graph, the idealized branching process, and the differential equations governing the evolution of normalized random graph quantities.