Short paths for first passage percolation on the complete graph

DOI10.1007/S10955-013-0743-7zbMATH Open1314.82021arXiv1211.4569OpenAlexW2038033449MaRDI QIDQ359585FDOQ359585

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

Publication date: 12 August 2013

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Abstract: We study the complete graph equipped with a topology induced by independent and identically distributed edge weights. The focus of our analysis is on the weight W_n and the number of edges H_n of the minimal weight path between two distinct vertices in the weak disorder regime. We establish novel and simple first and second moment methods using path counting to derive first order asymptotics for the considered quantities. Our results are stated in terms of a sequence of parameters (s_n) that quantifies the extreme-value behaviour of the edge weights, and that describes different universality classes for first passage percolation on the complete graph. These classes contain both n-independent and n-dependent edge weight distributions. The method is most effective for the universality class containing the edge weights E^{s_n}, where E is an exponential(1) random variable and s_n log n -> infty, s_n^2 log n -> 0. We discuss two types of examples from this class in detail. In addition, the class where s_n log n stays finite is studied. This article is a contribution to the program initiated in cite{BhaHof12}.

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

Recommendations

• First passage percolation on random geometric graphs and an application to shortest-path trees
• Construction of a short path in high-dimensional first passage percolation
• First-passage percolation on the random graph
• Long paths in first passage percolation on the complete graph. I: Local PWIT dynamics
• First passage percolation on random graphs with finite mean degrees
• Long paths in first passage percolation on the complete graph II. Global branching dynamics
• First passage percolation on inhomogeneous random graphs
• First passage percolation on the Erdős-Rényi random graph
• Universality for first passage percolation on sparse random graphs

zbMATH Keywords

first passage percolationuniversalitycomplete graphhopcountweak disorderfirst and second moment methodpath counting

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Percolation (82B43)

Cites Work

• Title not available (Why is that?)
• Random graphs and complex networks. Volume 1
• Title not available (Why is that?)
• Universality for first passage percolation on sparse random graphs
• Distances in random graphs with finite mean and infinite variance degrees
• First-passage percolation on the random graph
• First passage percolation on the Erdős-Rényi random graph
• Title not available (Why is that?)
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Weak disorder in the stochastic mean-field model of distance. II
• Weak disorder asymptotics in the stochastic mean-field model of distance
• Short paths for first passage percolation on the complete graph
• First passage percolation on locally treelike networks. I. Dense random graphs
• Distances in random graphs with finite variance degrees

Cited In (11)

• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Long paths in first passage percolation on the complete graph. I: Local PWIT dynamics
• 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
• Last passage percolation on the complete graph
• Long-range first-passage percolation on the torus
• Degree distribution of shortest path trees and bias of network sampling algorithms
• Random shortest paths: non-Euclidean instances for metric optimization problems
• Short paths for first passage percolation on the complete graph
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• Successive shortest paths in complete graphs with random edge weights

This page was built for publication: Short paths for first passage percolation on the complete graph

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