Monotone properties of random geometric graphs have sharp thresholds

Abstract

Random geometric graphs result from taking $n$ uniformly distributed points in the unit cube, $[0,1{]}^d$, and connecting two points if their Euclidean distance is at most $r$, for some prescribed $r$. We show that monotone properties for this class of graphs have sharp thresholds by reducing the problem to bounding the bottleneck matching on two sets of $n$ points distributed uniformly in $[0,1{]}^d$. We present upper bounds on the threshold width, and show that our bound is sharp for $d=1$ and at most a sublogarithmic factor away for $d\ge 2$. Interestingly, the threshold width is much sharper for random geometric graphs than for Bernoulli random graphs. Further, a random geometric graph is shown to be a subgraph, with high probability, of another independently drawn random geometric graph with a slightly larger radius; this property is shown to have no analogue for Bernoulli random graphs.

Published at http://dx.doi.org/10.1214/105051605000000575 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)