Convergence of Achlioptas processes via differential equations with unique solutions
arXiv:1111.6179 · doi:10.1017/S0963548315000218
Abstract
In Achlioptas processes, starting from an empty graph, in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. The evolution of the rescaled size of the largest component in such variations of the Erdős--Rényi random graph process has recently received considerable attention, in particular for for Bollobás's `product rule'. In this paper we establish the following result for rules such as the product rule: the limit of the rescaled size of the `giant' component exists and is continuous provided that a certain system of differential equations has a unique solution. In fact, our result applies to a very large class of Achlioptas-like processes. Our proof relies on a general idea which relates the evolution of stochastic processes to an associated system of differential equations. Provided that the latter has a unique solution, our approach shows that certain discrete quantities converge (after appropriate rescaling) to this solution.
arXiv comment18 pages. Revised and expanded version
References in corpus (13)
- The phase transition in inhomogeneous random graphs
- "Explosive Percolation" Transition is Actually Continuous
- Construction and Analysis of Random Networks with Explosive Percolation
- Explosive percolation: a numerical analysis
- Local cluster aggregation models of explosive percolation
- Achlioptas process phase transitions are continuous
- Finite-size scaling theory for explosive percolation transitions
- Achlioptas processes are not always self-averaging
- Phase transitions for modified Erdös-Rényi processes
- The evolution of subcritical Achlioptas processes
- The Bohman-Frieze Process Near Criticality
- Bounded-size rules: The barely subcritical regime
- A central limit theorem via differential equations