Long-range first-passage percolation on the torus

Abstract

We study a geometric version of first-passage percolation on the complete graph, known as long-range first-passage percolation. Here, the vertices of the complete graph ${\mathcal{K}}_n$ are embedded in the $d$-dimensional torus ${\mathbb{T}}_n^d$, and each edge $e$ is assigned an independent transmission time $T_e=\Vert e{\Vert }_{{\mathbb{T}}_n^d}^{\hat{I}}\pm E_e$, where $E_e$ is a rate-one exponential random variable associated with the edge $e$, $\Vert \cdot {\Vert }_{{\mathbb{T}}_n^d}$ denotes the torus-norm, and $\hat{I}\pm \ge 0$ is a parameter. We are interested in the case $\hat{I}\pm \in [0,d)$, which corresponds to the instantaneous percolation regime for long-range first-passage percolation on ${\mathbb{Z}}^d$ studied by Chatterjee and Dey, and which extends first-passage percolation on the complete graph (the $\hat{I}\pm =0$ case) studied by Janson. We consider the typical distance, flooding time, and diameter of the model. Our results show a $1,2,3$-type result, akin to first-passage percolation on the complete graph as shown by Janson. The results also provide a quantitative perspective to the qualitative results observed by Chatterjee and Dey on ${\mathbb{Z}}^d$.

16 pages