The evolution of subcritical Achlioptas processes. Issue 1 (25th March 2014)

• Record Type: Journal Article
• Authors: Riordan, Oliver; Warnke, Lutz
• Is Part Of: Random structures & algorithms. Volume 47:Issue 1(2015)
• Page Start: 174
• Page End: 203
• Publication Date: 2014-03-25
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20530
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>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. 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 <italic>B</italic> 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</p> </abstract>