Long paths in first passage percolation on the complete graph. I: Local PWIT dynamics

DOI10.1214/20-EJP484MaRDI QIDQ2201495zbMATH OpenOpenAlexFDO

Authors Maren Eckhoff, Jesse Goodman, Remco van der Hofstad, Francesca Romana Nardi

Publication date 29 September 2020

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

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

zbMATH Keywords

first passage percolationrandom graphsinvasion percolation

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: We study the random geometry of first passage percolation on the complete graph equipped with independent and identically distributed edge weights, continuing the program initiated by Bhamidi and van der Hofstad [9]. We describe our results in terms of a sequence of parameters $(s_n{)}_{ngeq1}$ that quantifies the extreme-value behavior of small weights, and that describes different universality classes for first passage percolation on the complete graph. We consider both $n$-independent as well as $n$-dependent edge weights. The simplest example consists of edge weights of the form $E^{s_n}$, where $E$ is an exponential random variable with mean 1. In this paper, we investigate the case where $s_{n}ightarrowinfty$, and focus on the local neighborhood of a vertex. We establish that the smallest-weight tree of a vertex locally converges to the invasion percolation cluster on the Poisson weighted infinite tree. In addition, we identify the scaling limit of the weight of the smallest-weight path between two uniform vertices.

Recommendations

• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• Short paths for first passage percolation on the complete graph
• Universality for first passage percolation on sparse random graphs
• First passage percolation on the Erdős-Rényi random graph
• The longest minimum-weight path in a complete graph

Cites work

• scientific article; zbMATH DE number 5730481 (Why is no real title available?)
• scientific article; zbMATH DE number 2001586 (Why is no real title available?)
• scientific article; zbMATH DE number 2042286 (Why is no real title available?)
• Diameter of the stochastic mean-field model of distance
• Exponential growth of ponds in invasion percolation on regular trees
• Invasion percolation on regular trees
• Invasion percolation on the Poisson-weighted infinite tree
• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Outlets of 2D invasion percolation and multiple-armed incipient infinite clusters
• Random graphs and complex networks. Volume 1
• Recurrence of distributional limits of finite planar graphs
• Short paths for first passage percolation on the complete graph
• Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees
• The continuum random tree. I
• The continuum random tree. III
• The diameter of sparse random graphs
• The scaling limit of the minimum spanning tree of the complete graph
• Weak disorder asymptotics in the stochastic mean-field model of distance
• Weak disorder in the stochastic mean-field model of distance. II

Cited in

(4)

• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• Last passage percolation on the complete graph
• Long-range first-passage percolation on the torus
• Short paths for first passage percolation on the complete graph

This page was built for publication: Long paths in first passage percolation on the complete graph. I: Local PWIT dynamics

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