The evolution of subcritical Achlioptas processes
From MaRDI portal
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. 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 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.
Recommendations
- scientific article; zbMATH DE number 3927727
- A geometric Achlioptas process
- Intermediately subcritical branching process in a random environment: the initial stage of the evolution
- The initial evolution stage of a weakly subcritical branching process in a random environment
- scientific article; zbMATH DE number 6010518
- scientific article; zbMATH DE number 4058583
- scientific article; zbMATH DE number 1526056
- Memoryless rules for Achlioptas processes
- On the connectivity threshold of Achlioptas processes
Cites work
- Achlioptas process phase transitions are continuous
- Aggregation models with limited choice and the multiplicative coalescent
- Avoiding a giant component
- Birth control for giants
- Creating a Giant Component
- Differential equations for random processes and random graphs
- Explosive percolation in random networks
- Networking -- smoothly does it
- Phase transitions for modified Erdős--Rényi processes
- Ramsey games with giants
- Sharpness of the phase transition in percolation models
- The birth of the giant component
- The Bohman-Frieze process near criticality
- The phase transition in inhomogeneous random graphs
Cited in
(20)- Sesqui-type branching processes
- Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
- Critical random graphs and the differential equations technique
- On the critical probability in percolation
- Preferential attachment without vertex growth: emergence of the giant component
- Explosive percolation in Erdős-Rényi-like random graph processes
- Creating small subgraphs in Achlioptas processes with growing parameter
- Connectivity thresholds for bounded size rules
- Memoryless rules for Achlioptas processes
- Avoiding small subgraphs in Achlioptas processes
- Susceptibility in subcritical random graphs
- Achlioptas process phase transitions are continuous
- The augmented multiplicative coalescent, bounded size rules and critical dynamics of random graphs
- Convergence of Achlioptas processes via differential equations with unique solutions
- On the method of typical bounded differences
- Bounded-size rules: the barely subcritical regime
- Given enough choice, simple local rules percolate discontinuously
- Prominent examples of flip processes
- Local limit of the random degree constrained process
- Birth control for giants
This page was built for publication: The evolution of subcritical Achlioptas processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192378)
