Random geometric graph diameter in the unit ball

Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05) Combinatorial probability (60C05) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: The unit ball random geometric graph

G = G_{p}^{d} (l a m b d a, n)

has as its vertices

n

points distributed independently and uniformly in the

d

-dimensional unit ball, with two vertices adjacent if and only if their

l_{p}

-distance is at most

l a m b d a

. Like its cousin the Erdos-Renyi random graph,

G

has a connectivity threshold: an asymptotic value for

l a m b d a

in terms of

n

, above which

G

is connected and below which

G

is disconnected (and in fact has isolated vertices in most cases). In the connected zone, we determine upper and lower bounds for the graph diameter of

G

. Specifically, almost always,

d i a m_{p} (m a t h b f B) (1 - o (1)) / l a m b d a l e q d i a m (G) l e q d i a m_{p} (m a t h b f B) (1 + O ((l n l n n / l n n)^{1 / d})) / l a m b d a

, where

d i a m_{p} (m a t h b f B)

is the

e l l_{p}

-diameter of the unit ball

m a t h b f B

. We employ a combination of methods from probabilistic combinatorics and stochastic geometry.

Recommendations

Cited in

(10)

This page was built for publication: Random geometric graph diameter in the unit ball

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