The diameter of a long range percolation graph

2001/12/04 by Don Coppersmith, David Gamarnik, Coppersmith, Don +3 · 2 citations
Mathematics · Physics and Astronomy · #60C05 #60K35 #82B26 #82B43 #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics #math-ph #math.CO #math.MP #math.PR #msc:60C05 #msc:60K35 #msc:82B26 #msc:82B43

paper · pdf · doi:10.48550/arxiv.math/0112029

To appear in Symposium on Discrete Algorithms, 2002

arxiv created 2001/12/04 · openalex publication_date 2001/12/04 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the following long range percolation model: an undirected graph with the node set \0,1,...,N\^d, has edges (\x,\y) selected with probability ≈ β/||\x-\y||^s if ||\x-\y||>1, and with probability 1 if ||\x-\y||=1, for some parameters β,s>0. This model was introduced by Benjamini and Berger, who obtained bounds on the diameter of this graph for the one-dimensional case d=1 and for various values of s, but left cases s=1,2 open. We show that, with high probability, the diameter of this graph is Θ(log N/loglog N) when s=d, and, for some constants 02d. We also provide a simple proof that the diameter is at most log^O(1)N with high probability, when d

Cited by

• Uniqueness and dimension for the geodesic of the critical long-range percolation metric
• The contact process on Scale-Free Percolation

Related

• A sharp leading order asymptotic of the diameter of a long range percolation graph
• The Diameter of Long-Range Percolation Clusters on Finite Cycles
• Distances in critical long range percolation
• The polynomial growth of the infinite long-range percolation cluster
• On the scaling of the chemical distance in long-range percolation models