Monotone properties of random geometric graphs have sharp thresholds
<|reference_start|>Monotone properties of random geometric graphs have sharp thresholds: 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\ge2$. 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.<|reference_end|>
@article{goel2003monotone,
    title={Monotone properties of random geometric graphs have sharp thresholds},
    author={Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari},
    journal={Annals of Applied Probability 2005, Vol. 15, No. 4, 2535-2552},
    year={2003},
    doi={10.1214/105051605000000575},
    number={IMS-AAP-AAP0122},
    archivePrefix={arXiv},
    eprint={math/0310232},
    primaryClass={math.PR cond-mat.stat-mech cs.DM math.CO}
}