Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
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/log log N) when s = d, and, for some constants 0 < η1 < η2 < 1, it is at most Nη2 when s = 2d, and is at least Nη1 when d = 1, s = 2, β < 1 or when s > 2d. We also provide a simple proof that the diameter is at most logO(1) N with high probability, when d < s < 2d, established previously in [2]. © 2002 Wiley Periodicals, Inc.
Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Chai Wah Wu
Linear Algebra and Its Applications
Moutaz Fakhry, Yuri Granik, et al.
SPIE Photomask Technology + EUV Lithography 2011
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems