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)

Cited by in corpus (10)

• On Topological Properties of Wireless Sensor Networks under the q-Composite Key Predistribution Scheme with On/Off Channels
• The Peculiar Phase Structure of Random Graph Bisection
• Focusing of Maximum Vertex Degrees in Random Faulty Scaled Sector Graphs
• Properties of metrics and infinite geometric graphs
• A Critical Connectivity Radius for Segmenting Randomly-Generated, High Dimensional Data Points
• Non-equilibrium phase transition and cultural drift in the continuous-trait Axelrod model
• On Characterizing the Local Pooling Factor of Greedy Maximal Scheduling in Random Graphs
• On The Sharp Threshold Interval Length of Partially Connected Random Geometric Graphs During K-Means Classification
• On Cycles in Random Graphs
• Infinite random geometric graphs