Phase Transitions of Achlioptas Processes

Phase Transitions of Achlioptas Processes

-
Will Perkins, New York University
Fine Hall 224

Achlioptas processes are a class of modifications of the Erdős–Rényi random graph. At each step of an Achlioptas process we add one of two randomly selected edges 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 Erdős–Rényi process. The results include the size and structure of small components in the barely sub- and supercritical time periods. We will also discuss another type of Achlioptas process that seems to exhibit markedly different behavior at the phase transition.