Graph diameter in long-range percolation

DOI10.1002/RSA.20349zbMATH Open1228.05134arXivmath/0406379OpenAlexW3125362494MaRDI QIDQ3094604FDOQ3094604

Authors: M. Biskup 

Publication date: 25 October 2011

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We study the asymptotic growth of the diameter of a graph obtained by adding sparse "long" edges to a square box in $$. We focus on the cases when an edge between $x$ and $y$ is added with probability decaying with the Euclidean distance as $|x-y{|}^{-s+o(1)}$ when $|x-y|oinfty$. For $sin(d,2d)$ we show that the graph diameter for the graph reduced to a box of side $L$ scales like $(logL{)}^{Delta+o(1)}$ where $Delt{a}^{-1}:=lo{g}_2(2d/s)$. In particular, the diameter grows about as fast as the typical graph distance between two vertices at distance $L$. We also show that a ball of radius $r$ in the intrinsic metric on the (infinite) graph will roughly coincide with a ball of radius $exp{r}^{1/Delta+o(1)}$ in the Euclidean metric.

Full work available at URL: https://arxiv.org/abs/math/0406379

Recommendations

• The diameter of a long-range percolation graph
• scientific article; zbMATH DE number 1984541
• scientific article; zbMATH DE number 2119680
• Graph distances of continuum long-range percolation
• The diameter of a scale-free random graph
• The diameter of long-range percolation clusters on finite cycles
• Diameters of random distance graphs

zbMATH Keywords

multiscale analysislong-range percolationdiameter growthgraph-theoretical distance

Mathematics Subject Classification ID

Distance in graphs (05C12)

Cites Work

• Transience, recurrence and critical behavior for long-range percolation
• One dimensional \(1/| j-i| ^ s\) percolation models: The existence of a transition for s\(\leq 2\)
• On the scaling of the chemical distance in long-range percolation models
• Geometry of the uniform spanning forest: transitions in dimensions 4, 8, 12,\dots
• Discontinuity of the percolation density in one dimensional \(1/| x- y| ^ 2\) percolation models
• On the chemical distance for supercritical Bernoulli percolation
• The diameter of a long-range percolation graph
• Inequalities with applications to percolation and reliability
• The diameter of long-range percolation clusters on finite cycles
• The growth of the infinite long-range percolation cluster
• Estimates on the effective resistance in a long-range percolation on \(\mathbb{Z}^d\)
• Simple random walk on long-range percolation clusters. II: Scaling limits
• Long-Range Percolation Mixing Time

Cited In (19)

• A strong law of large numbers for random biased connected graphs
• The diameter of a long-range percolation cluster on generalized pre-Sierpinski carpet and regular tree
• On the scaling of the chemical distance in long-range percolation models
• Sharp asymptotic for the chemical distance in long-range percolation
• Multiple phase transitions in long-range first-passage percolation on square lattices
• The diameter of a long-range percolation cluster on pre-Sierpinski gasket
• Bond percolation in small-world graphs with power-law distribution
• Arithmetic oscillations of the chemical distance in long-range percolation on \(\mathbb{Z}^d\)
• Large, lengthy graphs look locally like lines
• Title not available (Why is that?)
• The growth of the infinite long-range percolation cluster
• The diameter of a long-range percolation graph
• Distances in \(\frac{1}{\|x-y\|^{2d}}\) percolation models for all dimensions
• Inhomogeneous long-range percolation on the hierarchical lattice
• Quenched invariance principle for a class of random conductance models with long-range jumps
• Title not available (Why is that?)
• Spatial Gibbs random graphs
• Long-range contact process and percolation on a random lattice
• Percolation and epidemic processes in one-dimensional small-world networks (extended abstract)

This page was built for publication: Graph diameter in long-range percolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3094604)