Achlioptas process phase transitions are continuous
type: Item
instance of: scholarly article
title: Achlioptas process phase transitions are continuous
zbMATH Open document ID: 1255.05176
DOI: 10.1214/11-AAP798
author: Oliver Riordan
author: Lutz Warnke
published in: The Annals of Applied Probability
publication date: 2012-09-19T00:00:00Z
full work available at URL: https://arxiv.org/abs/1102.5306
full work available at URL: https://projecteuclid.org/euclid.aoap/1344614200
review text: In the well-known Erdős-Rényi graph sequence, the initial graph \(G(0)\) is the empty graph on \(n\) vertices, and \(G(m)\) is obtained from \(G(m-1)\) by inserting an edge at a randomly selected empty vertex-pair site for \(m=1,2,\dots\). The proportion of vertices in the largest connected component converges in probability to zero if and only if \(m/n\) converges to a value not larger than \(1/2\). This phase transition at the critical value \(1/2\) can be changed by modifying the rule for edge selections. It has been conjectured that a certain ``product rule'' exhibits so called ``explosive percolation''. This conjecture is here disproved by investigating a general edge selection rule which specifies how at least one edge is inserted among the vertex-pair sites in a random fixed-size sample of vertices. It is shown that this rule leads to continuous phase transitions. Convergence of the proportion of vertices in any largest component and convergence of the proportions of vertices in components of different orders are investigated.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 6083940
zbMATH Keywords: Random graph processes
zbMATH Keywords: phase transition
zbMATH Keywords: explosive percolation
MaRDI profile type: Publication
arXiv ID: 1102.5306
cites work: Explosive Percolation in Random Networks
cites work: Avoiding a giant component
cites work: Creating a Giant Component
cites work: The Evolution of Random Graphs
cites work: Q3286850
cites work: Phase transitions for modified Erdős--Rényi processes
cites work: Q3496342
cites work: Potpourri
cites work: Birth control for giants
cites work: Q4938890
OpenAlex ID: W1979727552
description: scientific article; zbMATH DE number 6083940