The Bohman‐Frieze process near criticality. Issue 2 (28th May 2012)

• Record Type: Journal Article
• Authors: Kang, Mihyun; Perkins, Will; Spencer, Joel
• Is Part Of: Random structures & algorithms. Volume 43:Issue 2(2013)
• Page Start: 221
• Page End: 250
• Publication Date: 2012-05-28
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20437
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>The Erdős‐Rényi process begins with an empty graph on n vertices, with edges added randomly one at a time to the 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 Bohman‐Frieze process, a simple modification of the Erdős‐Rényi process.</p> <p>The Bohman‐Frieze process also begins with an empty graph on <italic>n</italic> vertices. At each step two random edges are presented, 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 process. We show that it 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 <italic>t</italic><sub><italic>c</italic></sub> − ϵ (that is, when the number of edges are (<italic>t</italic><sub><italic>c</italic></sub> − ϵ)<italic>n</italic>/2) are trees or unicyclic components and that the largest component is of size Ω(ϵ<sup>‐2</sup>log <italic>n</italic>). Further, at <italic>t</italic><sub><italic>c</italic></sub> + ϵ, all components apart from the giant component are trees or unicyclic and the size of the second‐largest component is Θ(ϵ<sup>‐2</sup>log <italic>n</italic>). Each of these results corresponds to an analogous well‐known result for the Erdős‐Rényi process. Our proof techniques include combinatorial arguments, the differential equation method for random processes, and the singularity analysis of the moment generating function for the susceptibility, which satisfies a quasi‐linear partial differential equation. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013</p> </abstract>