If I have $n$ points uniformly distributed on the surface of a torus, and form a graph by adding an edge between pairs whenever they are within a unit distance (induced by the Euclidean metric), I have a random geometric graph.

The Euclidean geodesic between two vertices is just the shortest path, but where short means the Euclidean lengths of the edges along the path sum to the smallest value available (i.e. over all available paths).

The passage time, as well as the maximum transversal wandering of the path w.r.t. the straight line joining them, are conjectured to follow a power law $L^{\chi}$ and $L^{\xi}$, where $L$ is the Euclidean distance between the endpoints (norm of the straight line segment joining them). The first exponent $\chi$ gives the scaling of the root of the variance of the travel time, while the second $\xi$ gives instead the scaling of the expected wandering. See e.g. "The universal relation between scaling exponents in first-passage percolation", S. Chatterjee, Ann. Maths 177, 2013.

The relation $\chi = 2 \xi -1$ is meant to hold, relating the orders of the expected magnitude of the transversal wandering, and the time fluctuations about their expectation.

Though we don't know the exponents, should such a relation also hold in the spatial setting of the random geometric graph, where the edge lengths are not i.i.d., but induced by a point process?

enter image description here


The answer is yes. All that is required for the relation to hold, at least in principle, is that the curvature exponent of the limit shape in direction $u$ to be exactly 2.

See the review of Auffinger and Damron, Section 4.3.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.