Phase transitions for modified Erdös-Rényi processes

Abstract

A fundamental and very well studied region of the Erdös-Rényi process is the phase transition at n/2 edges in which a giant component suddenly appears. We examine the process beginning with an initial graph. We further examine the Bohman-Frieze process in which edges between isolated vertices are more likely. While the positions of the phase transitions vary, the three processes belong, roughly speaking, to the same universality class. In particular, the growth of the giant component in the barely supercritical region is linear in all cases.

22 pages

References in corpus (4)

• The phase transition in inhomogeneous random graphs
• Probability asymptotics: notes on notation
• Susceptibility in subcritical random graphs
• Duality in inhomogeneous random graphs, and the cut metric

Cited by in corpus (9)

• Achlioptas process phase transitions are continuous
• The evolution of subcritical Achlioptas processes
• The Bohman-Frieze Process Near Criticality
• Bounded-size rules: The barely subcritical regime
• Given enough choice, simple local rules percolate discontinuously
• The augmented multiplicative coalescent and critical dynamic random graph models
• Convergence of Achlioptas processes via differential equations with unique solutions
• Bohman-Frieze processes at criticality and emergence of the giant component
• Sesqui-type branching processes