ACO The ACO Seminar (2010-2011)

March 17 , 3:30pm, Wean 8220
Will Perkins, New York University
Phase Transitions of Achlioptas Processes


Achlioptas processes are a class of modifications of the Erdos-Renyi random graph. At each step of an Achlioptas process choose one of two randomly selected edges and add it to the graph according to a fixed rule. We present new results on the phase transitions of a group of Achlioptas processes called 'bounded-size rules' and show that qualitatively, these processes belong to the same class as the Erdos-Renyi process. The results include the size and structure of small components in the barely sub- and supercritical time periods. We will also mention another type of Achlioptas process that seems to exhibit markedly different behavior at the phase transition.

Back to the ACO home page