On random points in the unit disk

Abstract

Abstract Let n be a positive integer and λ > 0 a real number. Let V n be a set of n points in the unit disk selected uniformly and independently at random. Define G (λ, n ) to be the graph with vertex set V n , in which two vertices are adjacent if and only if their Euclidean distance is at most λ. We call this graph a unit disk random graph . Let $\lambda = c \sqrt {\ln n/n}$ and let X be the number of isolated points in G (λ, n ). We prove that almost always X ∼ n when 0 ≤ c < 1. It is known that if $\lambda = \sqrt {(\ln n + \phi (n))/n}$ where ϕ( n ) → ∞, then G (λ, n ) is connected. By extending a method of Penrose, we show that under the same condition on λ, there exists a constant K such that the diameter of G (λ, n ) is bounded above by K · 2/λ. Furthermore, with a new geometric construction, we show that when $\lambda = c \sqrt {\ln n/n}$ and c > 2.26164 …, the diameter of G (λ, n ) is bounded by (4 + o (1))/λ; and we modify this construction to yield a function c (δ) > 0 such that the diameter is at most 2(1 + δ + o (1))/λ when c > c (δ). © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006