Phase Transitions for Modified Erdos-Renyi Processes

Опубликовано 17 августа 2016, 2:17

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.