Invasion percolation on Galton-Watson trees

DOI10.1214/19-EJP281MaRDI QIDQ2631857zbMATH OpenOpenAlexFDO

Authors Marcus Michelen, Robin Pemantle, Josh Rosenberg

Publication date 16 May 2019

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.10672, https://projecteuclid.org/euclid.ejp/1554256913

zbMATH Keywords

backboneincipient infinite clusterlimit uniformpivotPoisson point processself-organized criticality

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We consider invasion percolation on Galton-Watson trees. On almost every Galton-Watson tree, the invasion cluster almost surely contains only one infinite path. This means that for almost every Galton-Watson tree, invasion percolation induces a probability measure on infinite paths from the root. We show that under certain conditions of the progeny distribution, this measure is absolutely continuous with respect to the limit uniform measure. This confirms that invasion percolation, an efficient self-tuning algorithm, may be used to sample approximately from the limit uniform distribution. Additionally, we analyze the forward maximal weights along the backbone of the invasion cluster and prove a limit law for the process.

Recommendations

• Invasion percolation on the Poisson-weighted infinite tree
• Exponential growth of ponds in invasion percolation on regular trees
• Invasion percolation on regular trees
• Critical percolation and the incipient infinite cluster on Galton-Watson trees
• Scaling limit of the invasion percolation cluster on a regular tree

Cites work

• Approximate counting, uniform generation and rapidly mixing Markov chains
• Asymptotic properties of supercritical branching processes I: The Galton-Watson process
• Biased random walks on Galton-Watson trees
• scientific article; zbMATH DE number 1354815 (Why is no real title available?)
• scientific article; zbMATH DE number 1405898 (Why is no real title available?)
• scientific article; zbMATH DE number 3410334 (Why is no real title available?)
• scientific article; zbMATH DE number 3190745 (Why is no real title available?)
• Invasion percolation on regular trees
• Poisson-Dirichlet branching random walks
• Probability Inequalities for Sums of Independent Random Variables
• Probability. Theory and examples.
• Problèmes rélatifs à l'itération de fonctions suggérés par les processus en cascade
• Quenched survival of Bernoulli percolation on Galton-Watson trees
• Random walks and percolation on trees
• Relations between invasion percolation and critical percolation in two dimensions
• Scaling limit of the invasion percolation cluster on a regular tree
• Self-testing algorithms for self-avoiding walks
• The fractal volume of the two-dimensional invasion percolation cluster
• The incipient infinite cluster in two-dimensional percolation
• Weighted sums of certain dependent random variables

Cited in

(9)

• Scaling limit of the invasion percolation cluster on a regular tree
• On transience of frogs on Galton-Watson trees
• The frog model on non-amenable trees
• Invasion percolation on regular trees
• Critical percolation and the incipient infinite cluster on Galton-Watson trees
• Invasion percolation on the Poisson-weighted infinite tree
• Multisource invasion percolation on the complete graph
• Invasion percolation on power-law branching processes
• Scaling of the cumulative weights of the invasion percolation cluster on a branching process tree

This page was built for publication: Invasion percolation on Galton-Watson trees

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