Monotone properties of random geometric graphs have sharp thresholds

Simple item page
dc.creatorGoel, Ashish
dc.creatorRai, Sanatan
dc.creatorKrishnamachari, Bhaskar
dc.date2003-10-15
dc.date2006-02-24
dc.date.accessioned2026-07-07T06:35:45Z
dc.date.available2026-07-07T06:35:45Z
dc.descriptionRandom 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.
dc.descriptionPublished 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)
dc.identifierhttps://arxiv.org/abs/math/0310232
dc.identifierhttp://arxiv.org/abs/math/0310232
dc.identifierAnnals of Applied Probability 2005, Vol. 15, No. 4, 2535-2552
dc.identifierdoi:10.1214/105051605000000575
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/99890
dc.subjectProbability
dc.subjectStatistical Mechanics
dc.subjectDiscrete Mathematics
dc.subjectCombinatorics
dc.subject60D05 (Primary) 5C80, 90B10 (Secondary)
dc.titleMonotone properties of random geometric graphs have sharp thresholds
dc.typetext

Files

Collections

arXiv