Aspects of Long-Range First-Passage Percolation

Abstract:

Given a graph G with non-negative (possibly random) edge-weights, if one interprets the weight of an edge as its passage time, then the first-passage time to reach u from v is the minimum time required to communicate between them.  Classically this model has been considered on Z^d with nearest neighbor edges.  We consider long-range first-passage models on Z^d and on large N × N torus, in which the weight w<xy> of the edge joining any two vertices x and y is random and has Exponential distribution with mean M(||x – y||) for some nondecreasing function M(∙) and Euclidean norm ||∙||.  The edge weights for different edges are independent.  We analyze the growth of the set of vertices reachable from the origin within time t, and characterize different growth regimes depending on the function M(∙).