05999801

j

05999801 Bonato, Anthony Janssen, Jeannette Infinite random geometric graphs. Ann. Comb. 15, No. 4, 597-617 (2011). 2011 Birkh\"auser Verlag (Springer), Basel EN geometric graphs adjacency property random graphs metric spaces isometry

doi:10.1007/s00026-011-0111-8

Summary: We introduce a new class of countably infinite random geometric graphs, whose vertices $V$ are points in a metric space, and vertices are adjacent independently with probability $p \in (0,1)$ if the metric distance between the vertices is below a given threshold. For certain choices of $V$ as a countable dense set in ${\mathbb{R}}^n$ equipped with the metric derived from the $L_{\infty}$-norm, it is shown that with probability 1 such infinite random geometric graphs have a unique isomorphism type. The isomorphism type, which we call $GR_{n}$, is characterized by a geometric analogue of the existentially closed adjacency property, and we give a deterministic construction of $GR_{n}$. In contrast, we show that infinite random geometric graphs in ${\mathbb{R}}^{2}$ with the Euclidean metric are not necessarily isomorphic.