The ACO Seminar (2010-2011)
, 3:30pm, Wean 8220
, 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