Multisource invasion percolation on the complete graph

DOI10.1214/23-AOP1641MaRDI QIDQ6183248zbMATH OpenFDO

Authors Louigi Addario-Berry, Jordan Mitchell Barrett

Publication date 26 January 2024

Published in The Annals of Probability (Search for Journal in Brave)

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

zbMATH Keywords

critical percolationminimum spanning treesinvasion percolationErdős-Rényi random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05) Percolation (82B43) Time-dependent percolation in statistical mechanics (82C43)

Abstract: We consider invasion percolation on the randomly-weighted complete graph $K_n$, started from some number $k(n)$ of distinct source vertices. The outcome of the process is a forest consisting of $k(n)$ trees, each containing exactly one source. Let $M_n$ be the size of the largest tree in this forest. Logan, Molloy and Pralat (arXiv:1806.10975) proved that if $k(n)/n^{1/3}o0$ then $M_n/no1$ in probability. In this paper we prove a complementary result: if $k(n)/n^{1/3}oinfty$ then $M_n/no0$ in probability. This establishes the existence of a phase transition in the structure of the invasion percolation forest around $k(n)asymp{n}^{1/3}$. Our arguments rely on the connection between invasion percolation and critical percolation, and on a coupling between multi-source invasion percolation with differently-sized source sets. A substantial part of the proof is devoted to showing that, with high probability, a certain fragmentation process on large random binary trees leaves no components of macroscopic size.

Recommendations

• Invasion percolation on Galton-Watson trees
• Invasion percolation and the incipient infinite cluster in 2D
• Scaling limit of the invasion percolation cluster on a regular tree
• Invasion percolation on regular trees
• Percolation and minimal spanning forests in infinite graphs

Cites work

• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• A variant of the Erdős–Rényi random graph process
• Capillary displacement and percolation in porous media
• Component behavior near the critical point of the random graph process
• Critical random graphs: limiting constructions and distributional properties
• Cutting down trees with a Markov chainsaw
• Geometry of the minimal spanning tree of a random 3-regular graph
• Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
• Ground-state structure in a highly disordered spin-glass model.
• Invasion percolation on Galton-Watson trees
• Invasion percolation on regular trees
• Invasion percolation on the Poisson-weighted infinite tree
• Limit theorems for 2D invasion percolation
• On finding a minimum spanning tree in a network with random weights
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Random walk in a strongly inhomogeneous environment and invasion percolation
• Scaling limit of the invasion percolation cluster on a regular tree
• The continuum limit of critical random graphs
• The continuum random tree. I
• The fractal volume of the two-dimensional invasion percolation cluster
• The multiplicative coalescent, inhomogeneous continuum random trees, and new universality classes for critical random graphs
• The scaling limit of the minimum spanning tree of the complete graph
• The scaling limits of near-critical and dynamical percolation
• The scaling limits of the minimal spanning tree and invasion percolation in the plane
• The size of a pond in 2D invasion percolation
• Universal height and width bounds for random trees
• École d'été de probabilités de Saint-Flour XIII - 1983

Cited in

(1)

• \(d\)-connectivity of the random graph with restricted budget

This page was built for publication: Multisource invasion percolation on the complete graph

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