Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-05T14:51:44.141Z Has data issue: false hasContentIssue false

Convergence of Achlioptas Processes via Differential Equations with Unique Solutions

Published online by Cambridge University Press:  14 October 2015

OLIVER RIORDAN
Affiliation:
Mathematical Institute, University of Oxford, Andrew Wiles Building, Radcliffe Observatory Quarter, Woodstock Road, Oxford OX2 6GG, UK (e-mail: [email protected])
LUTZ WARNKE
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: [email protected])

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 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.

Type
Paper
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Achlioptas, D., D'Souza, R. M. and Spencer, J. (2009) Explosive percolation in random networks. Science 323 14531455.CrossRefGoogle ScholarPubMed
[2]Aldous, D. (1999) Deterministic and stochastic models for coalescence (aggregation and coagulation): A review of the mean-field theory for probabilists. Bernoulli 5 348.CrossRefGoogle Scholar
[3]Azar, Y., Broder, A. Z., Karlin, A. R. and Upfal, E. (1999) Balanced allocations. SIAM J. Comput. 29 180200.CrossRefGoogle Scholar
[4]Bhamidi, S., Budhiraja, A. and Wang, X. (2015) Aggregation models with limited choice and the multiplicative coalescent. Random Struct. Alg. 46 55116.CrossRefGoogle Scholar
[5]Bhamidi, S., Budhiraja, A. and Wang, X. (2014) Bounded-size rules: The barely subcritical regime. Combin. Probab. Comput. 23 505538.CrossRefGoogle Scholar
[6]Bohman, T. and Frieze, A. (2001) Avoiding a giant component. Random Struct. Alg. 19 7585.CrossRefGoogle Scholar
[7]Bohman, T. and Kravitz, D. (2006) Creating a giant component. Combin. Probab. Comput. 15 489511.CrossRefGoogle Scholar
[8]Bollobás, B., Janson, S. and Riordan, O. (2007) The phase transition in inhomogeneous random graphs. Random Struct. Alg. 31 3122.CrossRefGoogle Scholar
[9]Bollobás, B. and Riordan, O. (2009) Random graphs and branching processes. In Handbook of Large-Scale Random Networks, Vol. 18 of Bolyai Society Mathematical Studies, pp. 15–115.Google Scholar
[10]Cho, Y. S., Kim, S. W., Noh, J. D., Kahng, B. and Kim, D. (2010) Finite-size scaling theory for explosive percolation transitions. Phys. Rev. E 82 042102.CrossRefGoogle ScholarPubMed
[11]da Costa, R. A., Dorogovtsev, S. N., Goltsev, A. V. and Mendes, J. F. F. (2010) Explosive percolation transition is actually continuous. Phys. Rev. Lett. 105 255701.CrossRefGoogle ScholarPubMed
[12]D'Souza, R. M. and Mitzenmacher, M. (2010) Local cluster aggregation models of explosive percolation. Phys. Rev. Lett. 104 195702.CrossRefGoogle ScholarPubMed
[13]Erdős, P. and Rényi, A. (1960) On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl 5 1761.Google Scholar
[14]Friedman, E. J. and Landsberg, A. S. (2009) Construction and analysis of random networks with explosive percolation. Phys. Rev. Lett. 103 255701.CrossRefGoogle ScholarPubMed
[15]Gut, A. (2005) Probability: A Graduate Course, Springer.Google Scholar
[16]Hurewicz, W. (1958) Lectures on Ordinary Differential Equations, MIT Press.CrossRefGoogle Scholar
[17]Janson, S. (2011) Networking: Smoothly does it. Science 333 298299.CrossRefGoogle Scholar
[18]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience.CrossRefGoogle Scholar
[19]Janson, S. and Spencer, J. (2012) Phase transitions for modified Erdős–Rényi processes. Ark. Math. 50 305329.CrossRefGoogle Scholar
[20]Kang, M., Perkins, W. and Spencer, J. (2013) The Bohman–Frieze process near criticality. Random Struct. Alg. 43 221250.CrossRefGoogle Scholar
[21]Norris, J. (1999) Smoluchowski's coagulation equation: Uniqueness, nonuniqueness and a hydrodynamic limit for the stochastic coalescent. Ann. Appl. Probab. 9 78109.CrossRefGoogle Scholar
[22]Radicchi, F. and Fortunato, S. (2010) Explosive percolation: A numerical analysis. Phys. Rev. E 81 036110.CrossRefGoogle ScholarPubMed
[23]Riordan, O. and Warnke, L. (2011) Explosive percolation is continuous. Science 333 322324.CrossRefGoogle ScholarPubMed
[24]Riordan, O. and Warnke, L. (2012) Achlioptas processes are not always self-averaging. Phys. Rev. E 86 011129.CrossRefGoogle Scholar
[25]Riordan, O. and Warnke, L. (2012) Achlioptas process phase transitions are continuous. Ann. Appl. Probab. 22 14501464.CrossRefGoogle Scholar
[26]Riordan, O. and Warnke, L. (2015) The evolution of subcritical Achlioptas processes. Random Struct. Alg. 47 174203.CrossRefGoogle Scholar
[27]Seierstad, T. G. (2009) A central limit theorem via differential equations. Ann. Appl. Probab. 19 661675.CrossRefGoogle Scholar
[28]Spencer, J. and Wormald, N. C. (2007) Birth control for giants. Combinatorica 27 587628.CrossRefGoogle Scholar
[29]Wormald, N. C. (1995) Differential equations for random processes and random graphs. Ann. Appl. Probab. 5 12171235.CrossRefGoogle Scholar
[30]Wormald, N. C. (1999) The differential equation method for random graph processes and greedy algorithms. In Lectures On Approximation and Randomized Algorithms, PWN, pp. 73155.Google Scholar
[31]Ziff, R. M. (2009) Explosive growth in biased dynamic percolation on two-dimensional regular lattice networks. Phys. Rev. Lett. 103 045701.CrossRefGoogle ScholarPubMed