Chemical distance in graphs of polynomial growth

2025/07/12 by Christian Gorski, Gorski, Christian, Eviatar B. Procaccia +1
Computer Science · Mathematics · #Advanced Graph Theory Research #FOS: Mathematics #Graph theory and applications #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2507.09120

openalex publication_date 2025/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove an Antal-Pisztora type theorem for transitive graphs of polynomial growth. That is, we show that if G is a transitive graph of polynomial growth and p > p_c(G), then for any two sites x, y of G which are connected by a p-open path, the chemical distance from x to y is at most a constant times the original graph distance, except with probability exponentially small in the distance from x to y. We also prove a similar theorem for general Cayley graphs of finitely presented groups, for p sufficiently close to 1. Lastly, we show that all time constants for the chemical distance on the infinite supercritical cluster of a transitive graph of polynomial growth are Lipschitz continuous as a function of p away from p_c.

Citations

• Asymptotic Shape of Subadditive Processes on Groups and on Random Geometric Graphs
• Lipschitz-continuity of time constant in generalized First-passage percolation
• Strict monotonicity for first passage percolation on graphs of polynomial growth and quasi-trees
• Continuity of the time and isoperimetric constants in supercritical\n percolation
• Asymptotic Shapes for Ergodic Families of Metrics on Nilpotent Groups
• First passage percolation on nilpotent Cayley graphs and beyond

Related

• Spread-out percolation on transitive graphs of polynomial growth
• A lower bound for the chemical distance in sparse long-range percolation models
• Locality of the critical probability for transitive graphs of\n exponential growth
• Percolation on graphs of polynomial growth is local: analyticity, supercritical sharpness, isoperimetry
• All spatial random graphs with weak long-range effects have chemical distance comparable to Euclidean distance