The diameter of a long-range percolation graph

From MaRDI portal





The authors consider a random graph \(G=G(N)\) on the node set \([N]_d\equiv\{0,1,\dots,N\}^d\) equipped with the \(l^1\) norm~\(\|\cdot\|\). Nodes \({\mathbf x}\), \({\mathbf y}\in[N]_d\) are connected with probability \(1\) if \(\|{\mathbf x}-{\mathbf y}\|=1\), and, otherwise, with probability \(1-\exp\{-\beta/\|{\mathbf x}-{\mathbf y}\|^s\}\), where \(\beta>0\), \(s>0\) are some fixed parameters. It is believed that the (random) diameter \(D(N)\) of the graph \(G\) exhibits a phase transition at \(s=d\) and \(s=2d\). A one-dimensional version of this model with periodic boundary conditions (i.e., on a circle) was studied by \textit{I. Benjamini} and \textit{N. Berger} [Random Struct.\ Algorithms 19, No.~2, 102-111 (2001; Zbl 0983.60099)], but cases \(s=1\) and \(s=2\) were left open. In the current paper the authors obtain various bounds on \(D(N)\) supporting the double phase transition conjecture in dimensions \(d\geq 1\) and, in particular, finish the description of the one-dimensional case at \(s=1\) and \(s=2\).




Cited in
(29)








This page was built for publication: The diameter of a long-range percolation graph

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