Phase transitions in Achlioptas processes

Stochastic Analysis Seminar Series


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.







LUTZ WARNKE (University of Cambridge)


Monday, October 27, 2014 - 15:45
to 16:45