All spatial random graphs with weak long-range effects have chemical distance comparable to Euclidean distance

2024/12/17 by Lüchtrath, Lukas · 1 citation
#05C80 #FOS: Mathematics #Primary: 60K35 #Probability (math.PR) #Secondary: 90B15

paper · doi:10.48550/arxiv.2412.12796

Abstract

This note provides a sufficient condition for linear lower bounds on chemical distances (compared to the Euclidean distance) in general spatial random graphs. The condition is based on the scarceness of long edges in the graph and weak correlations at large distances and is valid for all translation invariant and locally finite graphs that fulfil these conditions. The proof is based on a renormalisation scheme introduced by Berger [arXiv: 0409021 (2004)].

Cited by

• Phase transitions for contact processes on sparse random graphs via metastability and local limits

Related

• A lower bound for the chemical distance in sparse long-range percolation models
• The chemical distance in random interlacements in the low-intensity regime
• On the scaling of the chemical distance in long-range percolation models
• Graph distances in scale-free percolation: the logarithmic case
• Chemical Distance for the Level Sets of the Gaussian Free Field