
arXiv: 1204.5068
AbstractIn 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. AlthouSgh the evolution of such ‘local’ modifications of the Erdős–Rényi random graph process has received considerable attention during the last decade, so far only rather simple rules are well understood. Indeed, the main focus has been on ‘bounded‐size’ rules, where all component sizes larger than some constant B are treated the same way, and for more complex rules very few rigorous results are known. In this paper we study Achlioptas processes given by (unbounded) size rules such as the sum and product rules. Using a variant of the neighbourhood exploration process and branching process arguments, we show that certain key statistics are tightly concentrated at least until the susceptibility (the expected size of the component containing a randomly chosen vertex) diverges. Our convergence result is most likely best possible for certain generalized Achlioptas processes: in the later evolution the number of vertices in small components may not be concentrated. Furthermore, we believe that for a large class of rules the critical time where the susceptibility ‘blows up’ coincides with the percolation threshold. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 174–203, 2015
branching processes, Probability (math.PR), Random graphs (graph-theoretic aspects), unbounded size rules, susceptibility, Achlioptas process, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), random graphs, Mathematics - Probability
branching processes, Probability (math.PR), Random graphs (graph-theoretic aspects), unbounded size rules, susceptibility, Achlioptas process, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), random graphs, Mathematics - Probability
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 11 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
