The Bohman-Frieze process near criticality

Mihyun Kang, Will Perkins, Joel Spencer

Research output: Contribution to journalArticlepeer-review

Abstract

The Erdos-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 Erdos and Rényi states that the Erdos-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 Erdos 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 Erdos-Rényi process. The Bohman-Frieze process also begins with an empty graph on n 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 Erdos-Rényi process in terms of the size and structure of the components near the critical point. We prove that all components at time tc - ε{lunate} (that is, when the number of edges are (tc - ε{lunate})n/2) are trees or unicyclic components and that the largest component is of size Ω(ε{lunate}-2log n). Further, at tc + ε{lunate}, all components apart from the giant component are trees or unicyclic and the size of the second-largest component is Θ(ε{lunate}-2log n). Each of these results corresponds to an analogous well-known result for the Erdos-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.

Original languageEnglish (US)
Pages (from-to)221-250
Number of pages30
JournalRandom Structures and Algorithms
Volume43
Issue number2
DOIs
StatePublished - Sep 2013

Keywords

  • Achlioptas process
  • Differential equation method
  • Phase transition
  • Random graphs

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The Bohman-Frieze process near criticality'. Together they form a unique fingerprint.

Cite this