Long Paths in First Passage Percolation on the Complete Graph II. Global Branching Dynamics

Area of Science:

• Probability Theory
• Statistical Physics
• Graph Theory

Background:

• First passage percolation models random path lengths on graphs.
• Strong disorder introduces complex behavior and scale crossovers.

Purpose of the Study:

• Analyze first passage percolation on complete graphs with highly separated edge weights.
• Characterize the scaling limit of optimal path weights and path lengths.
• Investigate the crossover between local and global dynamics.

Main Methods:

• Quantification of extreme-value behavior of edge weights.
• Analysis of barely supercritical Erdős-Rényi random graphs using branching processes.
• Decomposition of the smallest-weight tree into invasion percolation and branching process components.

Main Results:

• Identified the scaling limit of optimal path weights.
• Proved a central limit theorem for the number of edges in optimal paths.
• Extended results to n-dependent edge weights, settling a conjecture.

Conclusions:

• The study elucidates the interplay of local and global dynamics in strongly disordered percolation.
• Optimal paths exhibit lengths interpolating between random graphs and minimal spanning trees.
• The findings provide a comprehensive understanding of path length distributions in this model.