Name
Abstract | ||
|---|---|---|
The Erdos-Renyi process 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 Erds-Renyi process in terms of the size and structure of the components near the critical point. We prove that all components at time t(c) - E (that is, when the number of edges are (t(c) - E)n/2) are trees or unicyclic components and that the largest component is of size (E(-2)log n). Further, at t(c) + E, all components apart from the giant component are trees or unicyclic and the size of the second-largest component is (E(-2)log n). Each of these results corresponds to an analogous well-known result for the Erds-Renyi 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. (c) 2012 Wiley Periodicals, Inc. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1002/rsa.20437 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | Field | DocType |
random graphs,Achlioptas process,differential equation method,phase transition | Random regular graph,Strength of a graph,Discrete mathematics,Geometric graph theory,Combinatorics,Random graph,Cycle graph,Giant component,Multiple edges,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
43.0 | 2.0 | 1042-9832 |
Citations | PageRank | References |
4 | 0.48 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mihyun Kang | 1 | 163 | 29.18 |
| Will Perkins | 2 | 51 | 13.01 |
| Joel Spencer | 3 | 5 | 0.86 |