## 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 t_{c} - ε{lunate} (that is, when the number of edges are (t_{c} - ε{lunate})n/2) are trees or unicyclic components and that the largest component is of size Ω(ε{lunate}^{-2}log n). Further, at t_{c} + ε{lunate}, all components apart from the giant component are trees or unicyclic and the size of the second-largest component is Θ(ε{lunate}^{-2}log 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 language | English (US) |
---|---|

Pages (from-to) | 221-250 |

Number of pages | 30 |

Journal | Random Structures and Algorithms |

Volume | 43 |

Issue number | 2 |

DOIs | |

State | Published - Sep 2013 |

## Keywords

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

## ASJC Scopus subject areas

- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics