Phase Transition and Fluctuation Results for First-Passage Percolation on Spread-Out Cycle Graphs
Abstract
We study first-passage percolation on the ℓ-spread-out one-dimensional cycle of size n, where vertices are connected if their graph distance is at most ℓ. We assign i.i.d.~non-negative random weights from a Weibull distribution ωe ∼ Exp(1)1/θ to the edges for θ>0 fixed. This paper investigates the transition in the asymptotic behavior of the passage time Tn between two typical vertices and the hop-count of the optimal path as the connectivity parameter ℓ diverges with n. We identify two fundamentally distinct geometric regimes. In the mesoscopic regime (1 ≪ ℓ ≪ n), the optimal path locally mimics a spatial branching random walk but remains globally constrained to a one-dimensional geometry. We establish a law of large numbers characterized by the front speed of a Crump--Mode--Jagers branching random walk, prove a central limit theorem with Gaussian fluctuations when ℓ≪ n1/4, and show that the expected hop-count grows proportionally with the spatial distance. In the macroscopic regime (ℓ ≈ λn for λ∈ (0,1/2)), the graph becomes a highly connected mean-field network. We prove that the passage time collapses to a log n scale with constant order non-Gaussian fluctuations, explicitly determining the extreme-value limit driven by the collision of two independent non-spatial CMJ processes. We establish a law of large numbers for the hop-count. Finally, we rigorously trace the transition in the order of the mean of Tn between these two regimes, demonstrating an order transition for the passage time across the critical connectivity threshold ℓ asymp n/log n. Our results provide a comprehensive deterministic-range interpolation from spatial Gaussian fluctuations to mean-field extreme-value fluctuations.
Related
- Fluctuation bounds for rotationally invariant first-passage percolation
- First-Passage Percolation on Spread-out line graphs: Microscopic Regime
- Invariance in half-space last passage percolation and directed polymers
- Stationary Half-space Geometric Last Passage Percolation without Random Shift
- Half-space last passage percolation with inhomogeneous first row
BibTeX
@misc{dey2026phase,
title = {{Phase Transition and Fluctuation Results for First-Passage Percolation on Spread-Out Cycle Graphs}},
author = {Partha S. Dey and Daecheol Kim},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00110},
eprint = {2609.00110},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00110},
}
RIS
TY - UNPB
TI - Phase Transition and Fluctuation Results for First-Passage Percolation on Spread-Out Cycle Graphs
AU - Partha S. Dey
AU - Daecheol Kim
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.00110
UR - https://arxiv.org/abs/2609.00110
AB - We study first-passage percolation on the ℓ-spread-out one-dimensional cycle of size n, where vertices are connected if their graph distance is at most ℓ. We assign i.i.d.~non-negative random weights from a Weibull distribution ω_e ∼ Exp(1)^1/θ to the edges for θ>0 fixed. This paper investigates the transition in the asymptotic behavior of the passage time T_n between two typical vertices and the hop-count of the optimal path as the connectivity parameter ℓ diverges with n. We identify two fundamentally distinct geometric regimes. In the mesoscopic regime (1 ≪ ℓ ≪ n), the optimal path locally mimics a spatial branching random walk but remains globally constrained to a one-dimensional geometry. We establish a law of large numbers characterized by the front speed of a Crump--Mode--Jagers branching random walk, prove a central limit theorem with Gaussian fluctuations when ℓ≪ n^1/4, and show that the expected hop-count grows proportionally with the spatial distance. In the macroscopic regime (ℓ ≈ λn for λ∈ (0,1/2)), the graph becomes a highly connected mean-field network. We prove that the passage time collapses to a log n scale with constant order non-Gaussian fluctuations, explicitly determining the extreme-value limit driven by the collision of two independent non-spatial CMJ processes. We establish a law of large numbers for the hop-count. Finally, we rigorously trace the transition in the order of the mean of T_n between these two regimes, demonstrating an order transition for the passage time across the critical connectivity threshold ℓ asymp n/log n. Our results provide a comprehensive deterministic-range interpolation from spatial Gaussian fluctuations to mean-field extreme-value fluctuations.
ER -