The Bohman-Frieze Process

Combinatorics Seminar
Friday, April 29, 2011 - 15:05
1 hour (actually 50 minutes)
Skiles 006
Courant Institute, NYU
The Bohman-Frieze process is a simple modification of the Erdős-Rényi random  graph that adds dependence between the edges biased in favor of joining  isolated vertices. We present new results on the phase transition of the  Bohman-Frieze process and show that qualitatively it belongs 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 mention a class of random graph processes that seems to exhibit  markedly different critical behavior.