Monotone properties of random geometric graphs have sharp thresholds

Details Monotone properties of random geometric graphs have sharp thresholds Monotone properties of random geometric graphs have sharp thresholds

2003-10-15

arxiv.org/abs/math/0310232v4

Annals of Applied Probability 2005, Vol. 15, No. 4, 2535-2552

Mathematics

Probability

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

Scientific paper

10.1214/105051605000000575

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.

Affiliated with

Also associated with

No associations

Rating

Monotone properties of random geometric graphs have sharp thresholds does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Monotone properties of random geometric graphs have sharp thresholds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Monotone properties of random geometric graphs have sharp thresholds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-22215