Given enough choice, simple local rules percolate discontinuously

DOI10.1140/EPJB/E2014-50278-XMaRDI QIDQ6176887zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

statistical and nonlinear physics

Mathematics Subject Classification ID

Percolation (82B43)

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.

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

Cites work

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

Cited in

(9)

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

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)