Phase Transitions for Modified Erdos-Renyi Processes

A fundamental and very well studied region of the Erdos-Renyi process is the phase transition at m near n/2 edges in which a giant component suddenly appears. We review the behavior in the barely subcritical and barely supercritical regimes. We modify the process, particularly discussing a modification due to Tom Bohman and Alan Frieze in which isolated vertices are given preference. While the position of the phase transition changes and many constants change, we show to a large extent (and conjecture therest!) that the critical exponents remain the same and that the two processes belong to the same universality class. A key role is played by the susceptibility of the graph, a concept taken from theoretical physics with strong application to large finite graphs. The susceptibility, asymptotically, is shown to satisfy a differential equation from which its barely subcritical behavior may be deduced. We also discuss other natural processes which appear to have very different behavior.

©2011 Microsoft Corporation. All rights reserved.
  • SpeakerJoel Spencer
  • HostMadhu Sudan
  • AffiliationYale
  • Duration00:49:25
  • Date recorded15 June 2011
  • Share
    Share this page on Facebook
    Share this page on Twitter
    Share this page on LinkedIn
    E-mail this page
    RSS feeds