The phase transition in bounded-size Achlioptas processes
Abstract
In the Erdös-Rényi random graph process, starting from an empty graph, in each
step a new random edge is added to the evolving graph. One of its most
interesting features is the `percolation phase transition': as the ratio of the
number of edges to vertices increases past a certain critical density, the
global structure changes radically, from only small components to a single
giant component plus small ones.
In this talk we consider Achlioptas processes, which have become a key example
for random graph processes with dependencies between the edges. Starting from
an empty graph these proceed as follows: in each step two potential edges are
chosen uniformly at random, and using some rule one of them is selected and
added to the evolving graph. We discuss why, for a large class of rules, the
percolation phase transition is qualitatively comparable to the classical
Erdös-Rényi process.
Based on joint work with Oliver Riordan.