Giant components in random subgraphs of general graphs

Combinatorics Seminar
Friday, April 23, 2010 - 15:05
1 hour (actually 50 minutes)
Skiles 255
Emory University
Erd\H{o}s and R\'enyi observed that a curious phase transition in the size of the largest component in arandom graph G(n,p): If pn < 1, then all components have size O(\log n), while if pn > 1 there exists a uniquecomponent of size \Theta(n).  Similar transitions can be seen to exist when taking random subgraphs of socalled (n,d,\lambda) graphs (Frieze, Krivelevich and Martin), dense graphs (Bollobas et. al) and several otherspecial classes of graphs.  Here we consider the story for graphs which are sparser and irregular.  In thisregime, the answer will depend on our definition of a 'giant component'; but we will show a phase transitionfor graphs satisfying a mild spectral condition.  In particular, we present some results which supersede ourearlier results in that they have weaker hypotheses and (in some sense) prove stronger results.  Additionally,we construct some examples showing  the necessity of our new hypothesis.