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. Th...
We study inhomogeneous long-range first-passage percolation on $\mathbb{Z}^d$ with edge passage times $\lVert x-y\rVert^\alpha\omega_{xy}/(V_xV_y)$, where vertex weights have polynomial upper-tail exponent $\gamma$ and edge noises have polynomial lower-tail exponent $\theta$ at zero. The model interpolates between long...
Shirshendu Chatterjee, P. Dey, Daecheol Kim· 0 citations
We consider the weight-dependent random connection model on a Poisson point process of intensity $\lambda$ on $\mathbb{R}\times(0,1)$ in which the vertices $(x,t)$ and $(y,s)$ are joined precisely when $(t\vee s)|x-y|\le\beta$. Points at distance $d$ are joined with probability $\min(1,\beta/d)^2$, the critical decay o...
We study bootstrap percolation with independent vertex thresholds taking values one and two, with threshold-one probability $(1-c/d)/d$ for fixed $c>0$. The seed set is chosen uniformly among sets of a prescribed deterministic size, independently of the graph and thresholds. We prove threshold statements at fixed relat...
Consider a simple undirected graph $G$ on $N$ vertices, with each vertex holding an opinion from one of two options. Starting from the initial opinions on day 1, we run majority dynamics: on each subsequent day, all vertices simultaneously adopt the majority opinion among their neighbors, retaining their current opinio...
Let $G_D(n;r)$ be the random geometric graph generated by $n$ independent uniform points on the $D$-dimensional torus, with adjacency defined by torus $L^\infty$-distance at most $r$. We study first-order zero-one and convergence laws at fixed radius and in sparse regimes. At fixed radius, we determine the asymptotics...
Simi Haber, Mostafa Mirabi, S. Shelah· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
