The Bohman-Frieze Process

Series: 
Combinatorics Seminar
Friday, April 29, 2011 - 15:05
1 hour (actually 50 minutes)
Location: 
Skiles 006
,  
Courant Institute, NYU
,  
Organizer: 
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.