Long-Range First-Passage Percolation on the Torus

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\) ${\mathcal{K}}_n$ are embedded in the d-dimensional torus \(\mathbb T_n^d\) ${\mathbb{T}}_n^d$ , and each edge e is assigned an independent transmission time \(T_e=\Vert e\Vert _{\mathbb T_n^d}^\alpha E_e\) $T_e={\Vert e\Vert }_{{\mathbb{T}}_n^d}^{\alpha }{E}_e$ , where \(E_e\) $E_e$ is a rate-one exponential random variable associated with the edge e, \(\Vert \cdot \Vert _{\mathbb T_n^d}\) ${\Vert ·\Vert }_{{\mathbb{T}}_n^d}$ denotes the torus-norm, and \(\alpha \ge 0\) $\alpha \ge 0$ is a parameter. We are interested in the case \(\alpha \in [0,d)\) $\alpha \in [0,d)$ , which corresponds to the instantaneous percolation regime for long-range first-passage percolation on \(\mathbb {Z}^d\) ${\mathbb{Z}}^d$ studied by Chatterjee and Dey [14], and which extends first-passage percolation on the complete graph (the \(\alpha =0\) $\alpha =0$ case) studied by Janson [24]. 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\) ${\mathbb{Z}}^d$ .