The Phase Transition in the Configuration Model

Source abstract

Let G = G ( d ) be a random graph with a given degree sequence d , such as a random r -regular graph where r ≥ 3 is fixed and n = | G | → ∞. We study the percolation phase transition on such graphs G , i.e ., the emergence as p increases of a unique giant component in the random subgraph G [ p ] obtained by keeping edges independently with probability p . More generally, we study the emergence of a giant component in G ( d ) itself as d varies. We show that a single method can be used to prove very precise results below, inside and above the ‘scaling window’ of the phase transition, matching many of the known results for the much simpler model G ( n , p ). This method is a natural extension of that used by Bollobás and the author to study G ( n , p ), itself based on work of Aldous and of Nachmias and Peres; the calculations are significantly more involved in the present setting.