Phase Transitions for Modified Erdos-Renyi Processes

  • Joel Spencer | Yale

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 the
rest!) 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.

Speaker Bios

Joel Spencer’s research centers on Probabilistic Methods in Discrete Math and Computer Science. He is coauthor of «The Probabilistic Method» and cofounder of «Random Structures and Algoritms.» His Erdos Number is one.

Regardez suivant