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.
- Combinatorial Theory Seminar