We study first-passage percolation on the $\ell$-spread-out line graph, where each vertex $i\in\{0,1,\dots,n\}$ is connected to all others at distance at most $\ell$. Here, we focus on the microscopic regime, with $\ell$ fixed as $n\to\infty$. Independent nonnegative weights are assigned to these edges. We obtain a law of large numbers and precise fluctuation results for the passage time $T_n$ from $0$ to $n$. If the weight distribution has finite variance or a heavy tail with exponent above $2/\ell_c$ where $\ell_c=\ell(\ell+1)/2$, then $T_n$ satisfies a Gaussian CLT with $\sqrt{n}$ scaling. In contrast, for heavier-tailed distributions, with index below the threshold, we show that $T_n$, appropriately centered and scaled, converges to a non-Gaussian stable law. We also prove an LLN and CLT for the number of edges in the minimizing path. The key tool is a pivot-node decomposition; the geodesic can be segmented into i.i.d. blocks, leading to a renewal structure. Our results extend the classical one-dimensional CLT to include finite-range connectivity and heavy tails, revealing a new distributional phase transition in the fluctuations of $T_n$.
We study first-passage percolation on the $\ell$-spread-out one-dimensional cycle of size $n$, where vertices are connected if their graph distance is at most $\ell$. We assign i.i.d.~non-negative random weights from a Weibull distribution $\omega_e \sim \mathrm{Exp}(1)^{1/\theta}$ to the edges for $\theta>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 $\ell$ diverges with $n$. We identify two fundamentally distinct geometric regimes. In the mesoscopic regime ($1 \ll \ell \ll 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 $\ell\ll n^{1/4}$, and show that the expected hop-count grows proportionally with the spatial distance. In the macroscopic regime ($\ell \approx \lambda n$ for $\lambda \in (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 $\ell \asymp n/\log n$. Our results provide a comprehensive deterministic-range interpolation from spatial Gaussian fluctuations to mean-field extreme-value fluctuations.
P. Dey, Daecheol Kim· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
