Given enough choice, simple local rules percolate discontinuously

DOI10.1140/EPJB/E2014-50278-XzbMATH Open1515.82081arXiv1411.4527OpenAlexW2166739621MaRDI QIDQ6176887FDOQ6176887

Authors: Alex Waagen, Raissa M. D'Souza 

Publication date: 26 July 2023

Published in: The European Physical Journal B. Condensed Matter and Complex Systems (Search for Journal in Brave)

Abstract: There is still much to discover about the mechanisms and nature of discontinuous percolation transitions. Much of the past work considers graph evolution algorithms known as Achlioptas processes in which a single edge is added to the graph from a set of $k$ randomly chosen candidate edges at each timestep until a giant component emerges. Several Achlioptas processes seem to yield a discontinuous percolation transition, but it was proven by Riordan and Warnke that the transition must be continuous in the thermodynamic limit. However, they also proved that if the number $k(n)$ of candidate edges increases with the number of nodes, then the percolation transition may be discontinuous. Here we attempt to find the simplest such process which yields a discontinuous transition in the thermodynamic limit. We introduce a process which considers only the degree of candidate edges and not component size. We calculate the critical point $t_c=(1-heta(frac1k))n$ and rigorously show that the critical window is of size $O(fracnk(n))$. If $k(n)$ grows very slowly, for example $k(n)=logn$, the critical window is barely sublinear and hence the phase transition is discontinuous but appears continuous in finite systems. We also present arguments that Achlioptas processes with bounded size rules will always have continuous percolation transitions even with infinite choice.

Full work available at URL: https://arxiv.org/abs/1411.4527

Recommendations

• Achlioptas process phase transitions are continuous
• Explosive percolation in Erdős-Rényi-like random graph processes
• The evolution of subcritical Achlioptas processes
• Explosive percolation in Erdős-Rényi-like random graph processes
• Explosive percolation in random networks

zbMATH Keywords

statistical and nonlinear physics

Mathematics Subject Classification ID

Percolation (82B43)

Cites Work

• Probability. Theory and examples.
• Networks. An introduction.
• Balanced Allocations
• Title not available (Why is that?)
• Deterministic and stochastic models for coalescence (aggregation and coagulation): A review of the mean-field theory for probabilists
• Explosive percolation in random networks
• Title not available (Why is that?)
• Avoiding a giant component
• Achlioptas process phase transitions are continuous
• Birth control for giants
• The nature of explosive percolation phase transition
• Delaying satisfiability for random 2SAT

Cited In (9)

• Percolation and depinning transitions in cut-and-paste models of adaptation
• Explosive percolation in random networks
• Percolation on complex networks: theory and application
• Achlioptas process phase transitions are continuous
• Explosive percolation in Erdős-Rényi-like random graph processes
• Discontinuous percolation transitions in growing networks
• The Kuramoto model in complex networks
• Explosive transitions in complex networks' structure and dynamics: percolation and synchronization
• Discontinuous percolation transitions in cluster merging processes

This page was built for publication: Given enough choice, simple local rules percolate discontinuously

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6176887)