The Bohman-Frieze Process Near Criticality

Abstract

The Erdős-Rényi process begins with an empty graph on n vertices and edges are added randomly one at a time to a graph. A classical result of Erdős and Rényi states that the Erdős-Rényi process undergoes a phase transition, which takes place when the number of edges reaches n/2 (we say at time 1) and a giant component emerges. Since this seminal work of Erdős and Rényi, various random graph models have been introduced and studied. In this paper we study the so-called Bohman-Frieze process, a simple modification of the Erdős-Rényi process. The Bohman-Frieze process begins with an empty graph on n vertices. At each step two random edges are present and if the first edge would join two isolated vertices, it is added to a graph; otherwise the second edge is added. We present several new results on the phase transition of the Bohman-Frieze random graph process. We show that the Bohman-Frieze process has a qualitatively similar phase transition to the Erdős-Rényi process in terms of the size and structure of the components near the critical point. We prove that all components at time t_c-\eps (that is, when the number of edges are (t_c-\eps) n/2) are trees or unicyclic components and that the largest component is of size Ω(\eps^{-2} \log n). Further, at t_c + \eps, all components apart from the giant component are trees or unicyclic and the size of the second-largest component is Θ(\eps^{-2} \log n). Each of these results corresponds to an analogous well-known result for the Erdős-Rényi process. Our methods include combinatorial arguments and a combination of the differential equation method for random processes with singularity analysis of generating functions which satisfy quasi-linear partial differential equations.

References in corpus (2)

• Bohman-Frieze processes at criticality and emergence of the giant component
• Two critical periods in the evolution of random planar graphs

Cited by in corpus (7)

• The evolution of subcritical Achlioptas processes
• Bounded-size rules: The barely subcritical regime
• The augmented multiplicative coalescent and critical dynamic random graph models
• On the largest component in the subcritical regime of the Bohman-Frieze process
• 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