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 Kₙ Kn are embedded in the d -dimensional torus Tₙᵈ Tnd , and each edge e is assigned an independent transmission time Tₑ= e Tₙᵈ^α Eₑ Te=‖e‖TndαEe , where Eₑ Ee is a rate-one exponential random variable associated with the edge e , · Tₙᵈ ‖·‖Tnd denotes the torus-norm, and α ≥ 0 α≥0 is a parameter. We are interested in the case α ∈ [0,d) α∈[0,d) , which corresponds to the instantaneous percolation regime for long-range first-passage percolation on Zᵈ Zd studied by Chatterjee and Dey [14], and which extends first-passage percolation on the complete graph (the α =0 α=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 Zᵈ Zd .