Mathematics – Probability
Scientific paper
2012-04-23
Mathematics
Probability
33 pages, 2 figures
Scientific paper
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.
Riordan Oliver
Warnke Lutz
No associations
LandOfFree
The evolution of subcritical Achlioptas processes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The evolution of subcritical Achlioptas processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The evolution of subcritical Achlioptas processes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-444394