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

DOI10.1214/20-EJP484zbMATH Open1459.60196arXiv1512.06152OpenAlexW3042614504MaRDI QIDQ2201495FDOQ2201495

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)

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.

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

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

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)

Cites Work

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

Cited In (3)

• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• 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)