Marek Biskup
On the scaling of the chemical distance in long-range percolation models
(288K, PDF)
ABSTRACT. We consider the (unoriented) long-range percolation on~$\Z^d$ in dimensions~$d\ge1$, where distinct sites~$x,y\in\Z^d$ get connected with probability~$p_{xy}\in[0,1]$. Assuming~$p_{xy}=|x-y|^{-s+o(1)}$ as~$|x-y|\to\infty$, where~$s>0$ and~$|\cdot|$ is a norm distance on~$\Z^d$, and supposing that the resulting random graph contains an infinite connected component~$\scrC_\infty$, we let~$D(x,y)$ be the graph distance between~$x$ and~$y$ measured on~$\scrC_\infty$.
Our main result is that, for~$s\in(d,2d)$,
$$
D(x,y)=(\log|x-y|)^{\Delta+o(1)},
\qquad x,y\in \scrC_\infty,\,\,|x-y|\to\infty,
$$
where~$\Delta^{-1}$ is the binary logarithm of~$2d/s$ and~$o(1)$ is a quantity tending to zero in probability as $|x-y|\to\infty$.
Besides its interest for general percolation theory, this result sheds some light on a question that has recently surfaced in the context of ``small-world'' phenomena. As part of the proof we also establish tight bounds on the probability that the largest connected component in a finite box contains a positive fraction of all sites in the box.