The evolution of subcritical Achlioptas processes

Journal article

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. Although the evolution of such `local' modifications of the Erd{\H o}s--R\'enyi 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 rules: 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.

Authors: Riordan, O; Warnke, L

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Wiley
• Journal: Random Structures and Algorithms
• Volume: 47
• Issue: 1
• Pages: 174–203
• Publication date: 2014-01-01
• DOI: 10.1002/rsa.20530
• EISSN: 1098-2418
• ISSN: 1042-9832
• Language: English
• Keywords: susceptibility; random graphs; Achlioptas processes; size rules; branching processes