# Monotone properties of random geometric graphs have sharp thresholds

The Annals of Applied Probability 2005, Vol. 15, No. 4, 2535–2552 DOI: 10.1214/105051605000000575 c Institute of Mathematical Statistics, 2005

arXiv:math/0310232v4 [math.PR] 24 Feb 2006

MONOTONE PROPERTIES OF RANDOM GEOMETRIC GRAPHS HAVE SHARP THRESHOLDS By Ashish Goel,1 Sanatan Rai2 and Bhaskar Krishnamachari Stanford University, Stanford University and University of Southern California

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 ≥ 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.

1. Introduction. Consider n points distributed uniformly and independently in the unit cube [0, 1]d . Given a ?xed distance r > 0, connect two points if their Euclidean distance is at most r . Such graphs are called random geometric graphs, and are denoted by G(d) (Xn ; r ), as in [24]. Classically, these graphs have been the subject of much study because of connections to percolation, statistical physics, hypothesis testing and cluster analysis. Further, random geometric graphs are better suited than more combinatorial classes (such as Bernoulli random graphs) to model problems where the existence of an edge between two di?erent nodes depends on their spatial

Received April 2004; revised May 2005. Supported in part by NSF CAREER Award CCR-0339262 and by an Alfred P. Sloan faculty fellowship. 2 Supported by NSF Award CCR-0339262. AMS 2000 subject classi?cations. Primary 60D05; secondary 5C80, 90B10. Key words and phrases. Geometric random graphs, sharp thresholds, wireless networks.

1

This is an electronic reprint of the original article published by the Institute of Mathematical Statistics in The Annals of Applied Probability, 2005, Vol. 15, No. 4, 2535–2552. This reprint di?ers from the original in pagination and typographic detail. 1

2

A. GOEL, S. RAI AND B. KRISHNAMACHARI

distance. As a result, random geometric graphs have received increased attention in recent years in the context of distributed wireless networks (such as sensor networks), see, for example, [12, 13, 14]; and layout problems as in [5, 16, 24]. Another area is cluster analysis, especially its applications in medicine, biology and ecology; these may be found in [10]. In applications such as distributed wireless networks, the connectivity of random geometric graphs is of interest. Gupta and Kumar showed that for d = 2, if πr (n)2 = (log n + cn )/n, then as n ↑ ∞ the graph is connected almost surely as n ↑ ∞ if cn ↑ ∞ and is disconnected almost surely if cn ↓ ?∞ [12]. This result is remarkably similar to the corresponding result for Bernoulli random graphs (also known as Erd? os–Renyi graphs). An instance of a Bernoulli random graph is obtained by taking n points and connecting any two with probability p, independently of all other pairs. This class of graphs is denoted by Gn,p . Erd? os and Renyi [7, 8] showed that if p(n) = (log n + cn )/n, then the graph is a.s. connected or disconnected as cn ↑ ∞ or cn ↓ ?∞. For d = 2, Gupta and Kumar’s result can also be obtained from Penrose’s work on the longest edge of minimal spanning tree of G(Xn ; r (n)) [23]. Connectivity of random geometric graphs for d = 1 was also studied by Godehardt and Jaworski [11]. Connectivity results under the l∞ -norm may be found in [1]. In both random geometric graphs and Bernoulli random graphs, property thresholds are of great interest. To quote Bollob? as [2]:

One of the main aims of the theory of random graphs is to determine when a given property is likely to appear.

Particularly interesting are thresholds for monotone properties, of which connectivity is a classic example. A seminal result of Friedgut and Kalai [9] states that all monotone graph properties have a sharp threshold in Bernoulli random graphs, and the threshold width is δ(ε) = O(log ε?1 / log n). They also demonstrated a monotone property with a threshold width of ?(1/ log2 n) and conjectured that this is tight [i.e., the best upper bound on threshold width is O(1/ log 2 n)]. Their upper bound on threshold width was improved to O(1/ log2?γ n) for all γ > 0 by Bourgain and Kalai [4]. The similarity of the connectivity threshold for random geometric graphs and Bernoulli random graphs led to the conjecture that all monotone properties also have a sharp threshold in random geometric graphs (see [18, 20] for a more detailed discussion). For the d = 1 case, sharp thresholds for monotone properties are implicit in the recent work of McColm [20], though he does not compute bounds on the width. The de?nition of sharp thresholds we use in this paper is the one used by Friedgut and Kalai and is based on the threshold width. The de?nition used by McColm is the one used in the text by Janson, Luczak and Ruci? nski [17], and is stronger than the one used by Friedgut and Kalai; we discuss this in more detail at the end of the

THRESHOLDS FOR RANDOM GEOMETRIC GRAPHS

3

Introduction. The analysis of random geometric graphs is technically challenging because of dependence of the edges. The triangle inequality implies that the event that points x and z are connected is not independent of the event {(x, y ) and (y, z ) are edges}. This is in stark contrast to the case of Bernoulli random graphs. Hence proof techniques that have been successful for Gn,p cannot be exploited in the case of random geometric graphs. Our results. We show that all monotone graph properties have a sharp threshold for random geometric graphs, thus resolving the above conjecture. In fact, the threshold width for random geometric graphs is much sharper than for Bernoulli random graphs. In order to state our results formally, we need to establish some notation and some de?nitions. We use the symbol ? to mean “distributed as,” so that G ? G(d) (Xn ; r ) means that G is picked from G(d) (Xn ; r ). For ease of notation, we omit the superscript d in G(d) (Xn ; r ) as the dimension will be clear from the context. The critical radius for connectivity is de?ned as rc := (log n/πd n)1/d , where πd is the volume of the unit sphere in Rd . A graph property A is a set of undirected and unlabelled graphs. A property A is increasing if and only if G∈A =? (? G′ )[(V (G′ ) = V (G) and E (G) ? E (G′ )) ? G′ ∈ A].

Intuitively speaking, an increasing property is one that is preserved when edges are added to the graph. A graph property A is monotone if either A or Ac is increasing. Without loss of generality, for the rest of the paper, we shall implicitly mean increasing properties when referring to monotone properties. If A is an increasing property, then for 0 < ε < 1/2, let r (n, ε) = inf {r > 0 : P{G(Xn ; r ) ∈ A} ≥ ε}. De?ne further δ(n, ε) := r (n, 1 ? ε) ? r (n, ε). A property is said to have a sharp threshold if δ(n, ε) = o(1) for all 0 < ε < 1/2. Our main results are: Theorem 1.1. For every monotone property, the width δ(n, ε) is O for d = 1. For d = 2, √ δ(n, ε) = O(rc log1/4 n) ≡ O(log3/4 n/ n ), and for d ≥ 3, the width δ(n, ε) = O(rc ) ≡ O(log1/d n/n1/d ). log ε?1 n

4

A. GOEL, S. RAI AND B. KRISHNAMACHARI

Thus, all monotone properties have sharp thresholds. Observe that the width is much sharper than the threshold width for Gn,p . Moreover, we prove a stronger result: the graphs G(Xn ; r ) become subgraphs of G(Xn ; ρ) for ρ > r , with hight probability (w.h.p.) as n ↑ ∞. Note only that this is not the case for Bernoulli random graphs—we shall make this precise in Section 2. For the lower bounds we have: Theorem 1.2. For d ≥ 2, there exists a monotone property with width δ(n, ε) = ?((log ε?1 )1/d n?1/d ). For d = 1, there exists a monotone property with width √ δ(n, ε) = ?( log ε?1 / n ). Hence, we have a tight characterization of the threshold width for d = 1, and our upper bounds are only a sublogarithmic factor away for d ≥ 2. The key idea is to relate the behavior of monotone properties to the weight of the “bottleneck” matching (to be de?ned later) of the bipartite graph whose vertex sets are obtained by distributing n points uniformly and independently in [0, 1]d . Sharp results on the “bottleneck” matching weight are implicit in the work of Leighton and Shor [19] for d = 2 and Shor and Yukich [26] for d ≥ 3. We repeat them here for convenience. Theorem 1.3 ([19, 26]). Consider the bipartite graph on 2n points, where each set of n points is distributed uniformly and independently in the unit cube [0, 1]d , and independently of each other. If M is the length of the bottleneck matching, then w.h.p. as n ↑ ∞: M= Θ(rc log1/4 n), Θ(rc ), if d = 2, if d ≥ 3.

In Section 4 we present our own proof of the bound for d ≥ 3. The proof for the d ≥ 3 case in Shor and Yukich [26] invokes results from polyhedral geometry. We present a simpler proof that relies only on the properties of order statistics and Cherno? √ bounds. We prove that for d = 1, the bottleneck matching is O( log ε?1 / n ) with probability 1 ? ε. Moreover, our results also hold for any ?p -norm when p > 1, and not just under the Euclidean norm as in the setting of this paper. We omit the details, as they require straightforward modi?cations of the proofs given herein. It might seem curious that we do not report the dependence on ε in some of our bounds on the threshold width. This is because the results of Shor and Yukich as well as those of Leighton and Shor are high probability results: the bottleneck matching length is Θ(rc log1/4 n) in two dimensions and Θ(rc ) in higher dimensions not just in expectation but with probability 1 ? o(n?β ) for some β > 0. Hence, in asymptotic notation, our upper bound on δ(n, ε) in two and higher dimensions does not depend on ε as long as ε = ?(n?β ).

THRESHOLDS FOR RANDOM GEOMETRIC GRAPHS

5

Related work. There is a vast body of literature that is directly related to this paper. It would require a survey paper to even mention the salient results with any degree of honesty. We can only point the reader to the book by Penrose [24], the papers by Gupta and Kumar [12, 13, 14] and the paper by Shakkottai, Srikant and Shro? [25]. We note here that our techniques imply a sharp threshold for the coverage problem as discussed in [25], which is not a graph problem. We omit the details. The theory of Bernoulli random graphs is covered in the books by Bollob? as [2] and Janson, Luzak and Rucinski [17]. For some results on matchings in a similar context, see the paper by Holroyd and Peres [15] and for some results on covering algorithms see [3]. Sharp thresholds for random geometric graphs were conjectured in [18] and [20]. Muthukrishnan and Pandurangan [21] obtained asymptotically tight thresholds for connectivity, covering and routing-stretch in d dimensions using a new technique called bin-covering. Additive versus multiplicative thresholds. In this paper we are primarily concerned with bounding the threshold width of a property, along the lines of Friedgut and Kalai [9]. Informally, this corresponds to proving sharp “additive” thresholds. As we mentioned earlier, the notion of sharp thresholds presented in [17] or in [20] is stronger in that they require δ(n, ε)/rΠ (n) = o(1). Informally, this corresponds to “multiplicative” thresholds. We observe that our Theorem 1.1 also yields sharp thresholds in this stronger sense, provided the threshold radius is high enough. More precisely, if Π is a monotone property and rΠ (n) is its threshold radius, such that: rc = o(rΠ (n)) √ rc = o(rΠ (n)/ log1/4 n) nrΠ (n) → ∞ when d ≥ 3, when d = 2, when d = 1,

then Π also has a sharp threshold in the sense of Janson, Luczak and Ruci? nski [17]. Plan of this paper. We ?rst establish the relationship between monotone properties and bottleneck matchings and prove the upper bound in Section 2. In Section 3 we furnish the lower bounds. In Section 4 we discuss the upper bound for d ≥ 3, and in Section 5 for d = 1. We conclude in Section 6 with some open problems. 2. Bottleneck matchings and monotone properties. Recall that in a bipartite graph with vertex sets V1 and V2 , a perfect matching is a bijection φ : V1 → V2 , such that each v is adjacent to φ(v ). Thus a perfect matching is a disjoint collection of edges that covers every vertex. If the graph is weighted, then we de?ne the weight of the matching as the maximum weight of any

6

A. GOEL, S. RAI AND B. KRISHNAMACHARI

edge in the matching. A bottleneck matching is the perfect matching with the minimum weight. Let S1 and S2 denote two sets of n points each, where the points are i.i.d., chosen uniformly at random from the set [0, 1]d . Form the complete bipartite graph on (S1 , S2 ) and let the weight of an edge be the Euclidean distance (d) between its endpoints. Let Mn denote the bottleneck matching weight of this graph. We omit the dimension d where it is clear from the context. We ?rst link the weight of the bottleneck matching with a containment property on random geometric graphs. We shall write G ? G′ to mean that the graph G is contained in the graph G′ , that is, is isomorphic to a subgraph of G′ . Lemma 2.1. Suppose P{Mn > γ (n)} ≤ p for some function γ (n) and some constant p. For any radius r , consider independent random samples G ? G(Xn ; r ) and G′ ? G(Xn ; r + 2γ (n)) in d dimensions. Then, P{G ? G′ } ≥ 1 ? p. Proof. Let V represent the set of points in graph G and V ′ the set of points in graph G′ . Let φ denote the bottleneck matching between V and V ′ ; then Mn is the weight of this matching. Suppose (u, v ) ∈ E (G), that is, u ? v 2 ≤ r . Then, using triangle inequality, φ(u) ? φ(v )

2

≤ φ(u) ? u

2

+ u?v

2

+ v ? φ(v ) 2 .

But φ(u) ? u 2 and φ(v ) ? v 2 are both at most Mn , and hence φ(u) ? φ(v ) 2 ≤ 2Mn + r . If Mn ≤ γ (n), then the mapping φ establishes that G ? G′ , and hence P{G ? G′ } ≥ 1 ? p. The main result linking monotone properties to bottleneck matchings is: Theorem 2.2. If P{Mn > γ (n)} ≤ p, then the tone property in d dimensions is at most 2γ (n). √ p-width of any mono-

Proof. Let p = ε2 , so that P{Mn > γ (n)} ≤ ε2 . Let Π be an arbitrary increasing monotone property. Let rL = r (n, ε), rU = rL + 2γ (n). Let G ? G(Xn ; rL ), and G′ ? G(Xn ; rU ), and de?ne q := P{G′ ∈ / Π}. Since G is independent of G′ , P{G ∈ Π, G′ ∈ / Π} = ε · q . The monotonicity of Π implies that if G ∈ Π and G′ ∈ / Π, then G ? G′ . This means that P{G ? G′ } ≥ ε · q . By Lemma 2.1 above, P{G ? G′ } ≤ p, so that we must have q ≤ ε. But then r (n, 1 ? ε) ≤ r (n, 1 ? q ) = rU , so that δ(n, ε) ≤ rU ? rL = 2γ (n). With Theorem 2.2, the upper bound theorem follows with very little more work:

THRESHOLDS FOR RANDOM GEOMETRIC GRAPHS

7

Proof of Theorem 1.1. with probability at least show that

Leighton and Shor [19] show that and Shor and Yukich [26]

(2) Mn = Θ(rc log1/4 n), 1 ? n?κ , for some κ > 0,

(d) Mn = Θ(rc )

′ 1 ? n ?κ ,

for some κ′ > 0. Hence Theorem 2.2 implies with probability at least 1/4 that δ(n, ε) = O(rc log n) for d = 2 and δ(n, ε) = O(rc ) for d ≥ 3, for any constant ε > 0. In fact, the bound on δ(n, ε) holds for any ε = ?(n?c ), where c > 0 is a constant. In Proposition 5.1 (see Section 5), we show that for d = 1, β (1) P Mn ≤√ ≥ 1 ? exp(?cβ 2 ), n for some c > 0. By applying Theorem 2.2 with ε = exp(?cβ 2 ) we obtain δ(n, ε) = O log ε?1 n .

for d ≥ 3,

Remark 1. We have in fact shown that G(Xn ; r ) is a subset of G(Xn ; r ′ ) w.h.p., when r ′ = r + o(1). The corresponding result does not hold for Bernoulli random graphs. To see this suppose that G ? Gn,p and G′ ? Gn,P . For G ? G′ , every edge in G must exist in G′ . Hence, for M = n 2 , q =1?p and Q = 1 ? P , and a given matching φ:

M

P{G ? G′ under φ} =

K =0

M K ×

p K q M ?K M ?K L P K + L QM ? K ? L

M ?K L=0

M

=

K =0

M K × PK

p K q M ?K

M ?K L=0

M ?K L

P L QM ? K ? L

M

=

K =0

M K

(pP )K q M ?K (P + Q)M ?K

= (pP + q )M = (p(1 ? Q) + q ) = (1 ? pQ)M .

8

A. GOEL, S. RAI AND B. KRISHNAMACHARI

Choose p = 1/4, and P = 3/4. As there are n! matchings: P{G ? G′ } ≤ n! exp ? n(n ? 1) . 32

The last expression goes to zero as n ↑ ∞. Hence, even in this extreme case when P ? p = 1/2, we do not have Gn,p ? Gn,P with constant probability. 3. The lower bounds. We now present examples of monotone properties to show that our bounds are tight in the d = 1 case and within a sublogarithmic factor for d ≥ 2. For the d = 1 case, we consider the property Π, de?ned by G∈Π ?? min deg(u) ≥

u∈V

|V | , 4

where V is the vertex set of G. Let x1 , . . . , xn be the n uniformly distributed points in [0, 1]; these are the vertices of the graph G. Let x(i) denote the ith order statistic. We have the following two estimates: Lemma 3.1. If 0 < ε ≤ 0.5e?44/6 , then for property Π: r (n, 1 ? ε) ≥ 1 + 4 log 1/2ε . 2n

Proof. Let u = 1/4 + ?, where ? > 0 is to be determined later. Pick G ? G(Xn ; u), and let the vertices be x1 , . . . , xn . Then x1 , . . . , xn are distributed uniformly in [0, 1]. Observe that P{x(n/4) > u} ≥ ε =? =? P deg(x(1) ) < P{G ∈ / Π} ≥ ε,

d

n ≥ε 4

where in the ?rst implication we have used the fact that deg(x(1) ) < n/4 ?

x(n/4+1) ? x(1) > u, and that x(n/4+1) ? x(1) = x(n/4) . Now, P{x(n/4) > u} = P{Bin(n, u) < n/4}, and for some suitably large n0 , √ P{ Norm(0, 1) < ? n?} ≥ 2ε =? P{Bin(n, u) < n/4} ≥ ε,

whenever n > n 0 , by the Normal approximation to the Binomial. √ Put ? = β/ n for β = 6 log(0.5/ε)/11. Then for 0 < ε ≤ 0.5e?44/6 , we have β ≥ 2. With a little bit of work, one can see that β 2 /2 ≤ ?4β/3 ? log 2ε. Since x ≥ log x for x ≥ 1, the last inequality implies that β 2 /2 ≤ log(3β ?1 /4) ? log(2ε). Observe that any β ≥ 2 satis?es 3 1 1 ≤ ? 3 4β β β

THRESHOLDS FOR RANDOM GEOMETRIC GRAPHS

9

so that 1 1 β2 ≤ log ? 3 2 β β or (β ?1 ? β ?3 ) exp ? β2 2 ≥ 2ε. + log 1 , 2ε

But then by Theorem 1.4 of [6], we can conclude P{Norm(0, 1) > β } ≥ 2ε. This shows that P G Xn ; 1 + 4 log (2ε)?1 2n ∈ / Π ≥ ε,

and since Π is increasing, this means that r (n, 1 ? ε) ≥ Lemma 3.2. For property Π: r n, for some ?xed constant c > 0. Proof. Suppose G ? G(Xn , l). For any u ∈ V (G), write degL (u) for the number of points to the left of u and adjacent to it, and similarly let degR (u) stand for the number of right neighbors. Note that if deg(x(1) ) ≥ n/4, then necessarily deg(x(i) ) ≥ n/4 for all 1 ≤ i ≤ n/4. With this observation we have: P{G ∈ / Π} = P ≤P +P

n/4<i<3n/4

1 + 4

log (2ε)?1 . 2n

1 c 1 ≤ +√ , 2 4 n

deg(x(i) ) <

1≤i≤n

n 4

deg(x(1) ) <

n n or deg(x(n) ) < 4 4 degL (x(i) ) < n 8 n 8 n . 8

+P

n/4<i<3n/4

degR (x(i) ) < n 4

≤ 2 P deg(x(1) ) <

(1)

+ n P deg(x(i) ) <

(2)

10

A. GOEL, S. RAI AND B. KRISHNAMACHARI

To bound the ?rst term (1), ?rst observe that by arguing as in the last lemma P{deg(x(1) ) < n/4} = P{Bin(n, l) < n/4}. By applying Cherno? 2 /2 ?C1 bounds, we can , when √ ?nd a C1 > 0 so that P{Bin(n, l) < n/4} < e l = 1/4 + C1 / n. To bound the second term (2), √ again apply Cherno?’s bounds to ?nd C2 > 0, such that for l = 1/4 + C2 / n, n n n = nP Bin(n, l) < ≤ n exp ? , 8 8 32 so that for n large enough this term √ is overwhelmingly small. Therefore, for c ≥ max(C1 , C2 ), and l = 1/4 + c/ n, we have nP deg(x(1) ) < √ so that r (n, 1/2) ≤ 1/4 + c/ n, for a suitably chosen c. Lemmas 3.1 and 3.2 show that for the graph property Π de?ned by G∈Π we have rΠ (n, 1 ? ε) ≥ rΠ n, 1 2 ≤ 1 + 4 log 1/2ε 2n when 0 < ε ≤ 0.5e?44/6 , ?? min deg(u) ≥

u∈V

P{G ∈ / Π} ≤ e?c

2 /2

+ n exp ?

n , 32

|V | , 4

c 1 +√ . 4 n

Hence we have shown the d ≥ 2 case of Theorem 1.2: Proof of Theorem 1.2, lower bound for d = 1. the last two lemmas. Immediate from

Theorem 3.3. For d ≥ 2, there exists an increasing property Π such that for 0 < ε < 1/2, the threshold width satis?es δ(n, ε) = ?(n?1/d ). Proof. Let Π be the property that the graph is complete. This is trivially a monotone property. √ Suppose 0 < ε < 1/2. Let u := d(1 ? 2?+ ) [see Figure 1(a)], for ?+ such that √ 1 0 < ?+ ≤ ?1/d [min( 2ε, log 2/2)]1/d , n and pick G ? G(Xn ; u). Fix a pair of diagonally opposite corner cubes with side ?+ , and consider the event that there is exactly one point in each. If

THRESHOLDS FOR RANDOM GEOMETRIC GRAPHS

11

this happens, then the graph is not complete, since the points are more than u apart. Hence: P{G ∈ / Π} ≥ n 2 d n?2 (?d , + ) · 2 · (1 ? 2?+ ) 2

n?2

since ?+ < (log 2/(2n))1/d . Thus, for large enough n we have

n?2 (1 ? 2?d ≥ 1? +)

2 log 2 2n

1 ≥ , 2

which implies that P{G ∈ / Π} ≥ n 2 (?d + ) ≥ ε. 2

√ ?1 × min( 2ε, log 2/2). The last inequality follows because we chose ?d +≤n Therefore, (1) r (n, 1 ? ε) ≥ u ≥ √ cε1/2d d 1 ? 1/d . n

Now we shall bound r (n) above. To this end set l = d ? 1 + (1 ? 4?? )2 [see Figure 1(b)]. Now suppose that ?? = (log ε?1 )1/d /(4n1/d ), and pick G ? G(Xn ; l). Using elementary geometry it is easy to see that, if none of the n points lies in any of the 2d cubes of side 2?? at the corners of [0, 1]d , then the graph is complete. Hence, for n large: where we have used the fact that 1 ? x ≥ e?x , when x ≥ 0, so that (1 ? x)n ≥ e?nx , if x < 1. Since exp(?n(4?? )d ) = ε, by our choice of ?? , it must be that (2) rn (ε) ≤ l = d?1+ 1? (log ε?1 )1/d n1/d

2

P{G ∈ Π} ≥ (1 ? 2d (2?? )d )n ≥ exp(?n(4?? )d ),

.

Putting (1) and (2) together: δ(n, ε) = rn (1 ? ε) ? rn (ε) ≥ u ? l ≥ = = √ cε1/d d 1 ? 1/d n √ cε1/d d 1 ? 1/d n √ d 1? cε1/d n1/d ? ? ? d?1+ 1? d?2 1? log ε?1 n 2 log ε?1 d n log ε?1 n

1/d 1/d 2

+

1/d

log ε?1 n

2/d

+

1 log ε?1 d n

2/d

12

A. GOEL, S. RAI AND B. KRISHNAMACHARI

Fig. 1.

De?nition of ?+ and ?? .

=

√ d

1?c + +

ε n

1/d

?1

1/d

1 2 log ε?1 2d n 1 4 log ε?1 8 d2 n

1?

2/d

1 log ε?1 2 n 1 log ε?1 2 n

1/d

1/d 2

1?

+ ···

=

√ log1/d ε?1 ? cdε1/d 1 d + o 1/d 1 /d dcn n log1/d ε?1 . n1/d

=?

Observe that for any κ > 0 constant, if ε = n?κ , our lower bound for d ≥ 3 matches our upper bound on the threshold width, and is only a factor of Θ(log1/4 n) away for d = 2. For any constant ε, the di?erence between the bounds is O(log1/d n) and O(log3/4 n), respectively. 4. Bounding the bottleneck matching for d ≥ 3. We now present a simpler proof of Mn = Θ(rc ) when d ≥ 3 than the proof presented in [26]. We emphasize that even though we also recursively subdivide the cube, our principle is di?erent. In our proof, at the end of each step, the points are distributed uniformly in each subcuboid. This requires careful choice of the cutting plane and a linear transformation based on order statistics. This, however, permits us to bound the matching length via Cherno? bounds, as opposed to estimating the aspect ratios of rectangular solids as in [26].

THRESHOLDS FOR RANDOM GEOMETRIC GRAPHS

13

The basic idea is to divide the unit square into n equal boxes. Given n points distributed uniformly on the square, move the points so that there is roughly a single point in each box. Now consider the two samples of red and blue points. Apply this process to both samples. Let ? be the maximum distance by which a red point is shifted, and similarly, let ?′ be the maximum shift for any blue point, along any coordinate direction. Then the inequality tells us that the bottleneck matching is less than √ triangle d(? + ?′ + n?1/d ). We shall now use this idea to bound the bottleneck matching in [0, 1]d . To move each point into its unique box we follow a recursive process. We shall provide only an informal description here, relegating the details to the Appendix. Moreover, for simplicity, we shall suppose n to be a power of 2. First divide the square by drawing a vertical line so that there are exactly n/2 points in each half. Transform the x-coordinates of the points in each half so that they are uniformly distributed in [0, 1/2] and [1/2, 1]. Now repeat the process along the y -axis for each rectangle, and then along the z -axis and so on. Repeat when all coordinate axes have been done once, and so on. One can carry this process for log n steps so that there is exactly one point in each box. However, for d ≥ 3 it is better to stop at the j th step, where j < log n. Choose j = ?d?1 log2 (n/ log n)?. Then the side of the box and hence the shift thereafter is ≤ 2?j . With this observation we can now show Proposition 4.1. If Mn is the weight of the bottleneck matching on a geometric random bipartite graph on 2n points in [0, 1]d , for d ≥ 3, then for any β > 1, we can ?nd a constant cd > 0 such that P{Mn > cd βrc } ≤ so that Mn = O(rc ) w.h.p. Proof. To estimate Mn , we compute the total shift experienced by an arbitrary point. To this end, we shall ?nd the shift along each axis, and so shall concentrate on one coordinate at a time. Let x1 , . . . , xd denote the coordinates. We regard a step as one cycle in which divisions along all axes have been completed, according to the scheme described above. Therefore, if a step begins with a d-dimensional cube of side l containing n points, by the end of the step, the cube has been divided into 2d cubes of side l/2, with n/2d points each. Let ni = n/2d(i?1) denote the number of points in a subcube at the beginning of the ith step, and let li = 2?i+1 denote the length of the side of the cube. Lemma A.2 implies that for any point in the left half of such a 1 , n β 2 ?1

14

A. GOEL, S. RAI AND B. KRISHNAMACHARI

(k )

subcube, the shift δi satis?es

(k )

in the xk -direction experienced during the ith step

2 γi 2 ni li

P{|δi | > γi } ≤ 2 exp ?

for any γi > 0.

Therefore, if δi is the total shift su?ered by a point during the ith step P{|δi | > γi } ≤ P

(k ) max |δi | > γi 1≤k ≤d d

≤

k =1

P{|δi | > γi }

(k )

2 ≤ 2d exp ?γi

n 2(i?1)(d?2)

.

2 · n/2(i?1)(d?2) = β 2 log n. Observe Now ?x a β > 1, and choose γi such that γi that with this choice, γi is decreasing with i only when d > 2. Let ? be the maximum total shift experienced by any point. Then it must be that

P |?| >

√

j

d

i=1

γi ≤ 2dnj exp(?β 2 log n),

which follows from taking the union bound over all n points, and all d coordinates, and the fact that after j steps, we divided a given coordinate at most j times. Notice that after j = log n steps, the side of the subcube reduces to 2? log n+1 = Θ(1/n), and therefore subsequent shifts cannot move the point by more than O(1/n). Hence we can halt the subdivisions after log n steps, knowing that the matched point is already within O(1/n). Hence, P |?| > √

log n

d

i=1

γi ≤ 2dn log n exp(?β 2 log n).

However, with a little bit of work, one can see that

log n

γi = β

i=1

log n n

log n

2(i?1)(d?2)/2

i=1

≤2·β = 2β

log n (d?2)/2(log2 n?log2 log n)/d 2 n log n n

1/d j i=1 1/d

.

Recall that (log n/n)1/d = rc πd , so that we have just shown γi ≤ 2βπd rc .

1/d

THRESHOLDS FOR RANDOM GEOMETRIC GRAPHS

15

Therefore, we have √ √ 1/d P{|?| > 2 dβπd rc } ≤ P |?| > d

j i=1

γi ≤

2d log n . 2 n β ?1

After j steps the side of the cube is 2?j and hence√ if we arbitrarily move points within the subcube, the extra shift is at most d2?j . Therefore, if we √ √ 1/d choose cd to be any constant larger than d + 2 dπd , we get |?| ≤ cd βrc 2 with probability at least 1 ? n1?β . We note in passing that for the above method to provide a bound in the d = 2 case, one must proceed for log n steps, so that there is only a single point in each box. However, in this case, one only gets an O(rc log n) bound, which is o? by log1/4 n from the sharp bound in [19]. 5. The bound for d = 1. Given n points uniformly distributed in [0, 1], follow the recursive division procedure described in the last section. In this case, at each step the number of points decreases by half. Therefore, we obtain a stronger result: Proposition 5.1. For any β > 0 √ (1) P{Mn ≥ β/ n } = O(exp(?cβ 2 ))

for some positive constant c. Proof. For the sake of simplicity we assume that n = 2k for some k ∈ N; this makes no di?erence to the proof except for simplifying some expressions. In the ith step there are 2i sets of n/2i points each. Therefore, if δi is the shift of an arbitrary set, then for βi > 0, by Lemma A.2: βi P |δi | ≥ √ n

i βi P max |?| ≥ √ n 2 ≤ 2 exp(?2i βi ),

so that the maximum shift ? of any point satis?es ≤2 n 2 exp(?2i βi ). 2i

i βi

2 = β 2 + i, for some β . Then Choose the βi ’s such that 2i βi 0 0 some suitable constant K > 0. Taking β = Kβ0 , we get

≤ Kβ0 for

β (1) P Mn ≥√ n for some constants c, c′ > 0.

≤ c′ exp(?cβ 2 ),

16

A. GOEL, S. RAI AND B. KRISHNAMACHARI

6. Conclusion. We have shown that all monotone graph properties have a sharp threshold for random geometric graphs. Moreover, this threshold is sharper than the one for Bernoulli random graphs. We have a sharp result for d = 1. For the d ≥ 3 we believe the upper bound of O(rc ) to be actually tight. For the d = 2 case we believe the upper bound to be O(rc ) as well, though this cannot be obtained via bottleneck matchings. APPENDIX: ESTIMATING THE SHIFT IN EACH RECURSIVE STEP To establish a bound on the amount by which each point is moved, we must examine the “shrinking” and “stretching” process formally. For simplicity we concentrate on the d = 2 case. Ignore the y -coordinates. Then we have n i.i.d. Unif [0, 1] points x1 , . . . , xn . It is well known [22] that the k smallest points are i.i.d. uniform in [0, x(k+1) ), and that the n ? k largest points are i.i.d. uniform in (x(k) , 1], where x(i) is the ith order statistic. Suppose that n is even—the analysis below applies mutatis mutandis when n is odd. Set δl = x(n/2+1) ? 1/2 and δr = 1/2 ? x(n/2) . Then transform the points as follows: ? 1/2 n ? (i) ? , for i = 1, . . . , , ?x 1/2 + δl 2 x(i) → 1 / 2 n ? ? 1 ? (1 ? x(i) ) ? , for i = + 1, . . . , n. 1/2 + δr 2

This transform leaves the smallest n/2 points uniformly distributed in [0, 1/2] and the largest n/2 points uniformly distributed in [1/2, 1]. This process is now repeated ?log n? times alternating the x- and y -coordinates. The maximum shift at any step is not more than |δl | for the points on the left and not more than |δr | for points on the right. We shall use δ = max{δl , δr }. Let Xt be the number of points in [0, t] prior to the transformation. The following result is immediate: Lemma A.1. For 0 < γ < 1/2, P{|δ| > γ } ≤ 2P X1/2+γ < n . 2

To bound the last probability, observe that Xt is just the sum of n i.i.d. Bernoulli’s that are 1 with probability t. Hereafter β > 0 is some constant. Lemma A.2. The shift δ of any point in the recursion step satis?es P{|δ| > γ } = O(exp(?n′ (γ/l)2 )),

where n′ is the number of points in the subcuboid being divided, and l is length of the side that is being divided.

THRESHOLDS FOR RANDOM GEOMETRIC GRAPHS

17

Proof. The proof is a straightforward application of Cherno?’s bound. Assume wlog that l = 1: P{|δ| > γ } ≤ 2P X1/2+γ < n′ 2 1 + γ ? n′ γ 2

= 2P X1/2+γ < n′ ≤ 2 exp ?

n′2 γ 2 2n′ (γ + 1/2) since γ ≤ 1/2.

≤ 2 exp(?n′ γ 2 )

Generalization to the d ≥ 3 case is straightforward. Acknowledgments. We should like to thank Peter Glynn, David Kempe, Rajeev Motwani and Devavrat Shah for useful discussions. We are especially grateful to Greg McColm for his comments on an earlier draft of the paper. REFERENCES

[1] Appel, M. J. B. and Russo, R. P. (2002). The connectivity of a graph on uniform points on [0, 1]d . Statist. Probab. Lett. 60 351–357. MR1947174 ? s, B. (2001). Random Graphs. Cambridge Univ. Press, New York. [2] Bolloba [3] Booth, L., Bruck, J., Franceschetti, M. and Meester, R. (2003). Covering algorithms, continuum percolation and the geometry of wireless networks. Ann. Appl. Probab. 13 722–741. MR1970284 [4] Bourgain, J. and Kalai, G. (1997). In?uences of variables and threshold intervals under group symmetries. Geom. Funct. Anal. 7 438–461. MR1466334 [5] D? iaz, J., Penrose, M. D., Petit, J. and Sema, M. (1998). Approximating layout problems on geometric random graphs. Technical Report TR-417-98. [6] Durrett, R. (1996). Probability : Theory and Examples, 2nd ed. Duxbury Press, Paci?c Grove, CA. ? s, P. and Renyi, A. (1959). On random graphs I. Publ. Math. Debrecen 6 [7] Erdo 290–291. MR120167 ? s, P. and Renyi, A. (1960). On the evolution of random graphs. Magyar Tud. [8] Erdo Akad. Mat. Kut. Int. Kozl. 5 17–61. MR125031 [9] Friedgut, E. and Kalai, G. (1996). Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124 2993–3002. MR1371123 [10] Godehardt, E. (1990). Graphs as Structural Models : The Applications of Graphs and Multigraphs in Cluster Analysis. Vieweg, Brunswick. MR1128322 [11] Godehardt, E. and Jaworski, J. (1996). On the connectivity of a random interval graph. Random Structures Algorithms 9 137–161. MR1611752 [12] Gupta, P. and Kumar, P. R. (1998). Critical power for asymptotic connectivity in wireless networks. In Stochastic Analysis, Control, Optimization and Applications : A Volume in Honor of W. H. Fleming 547–566. Birkh¨ auser, Boston. MR1702981 [13] Gupta, P. and Kumar, P. R. (2000). The capacity of wireless networks. IEEE Trans. Inform. Theory IT-46 388–404. MR1748976

18

A. GOEL, S. RAI AND B. KRISHNAMACHARI

[14] Gupta, P. and Kumar, P. R. (2001). Internets in the sky: The capacity of three dimensional wireless networks. Commun. Inf. Syst. 1 33–50. MR1907507 [15] Holroyd, A. and Peres, Y. (2003). Trees and matchings from point processes. Electron. Comm. Probab. 8 17–27. MR1961286 [16] i Silvestre, J. P. (2001). Layout problems. Ph.D. thesis, Universitat Polit` ecnica de Catalunya, Barcelona. ? ski, A. (2000). Random Graphs. Wiley, New [17] Janson, S., Luczak, T. and Rucin York. MR1782847 [18] Krishnamachari, B., Wicker, S., Bejar, R. and Pearlman, M. (2002). Critical density thresholds in distributed wireless networks. In Communications, Information and Network Security 1–15. Kluwer, Dordrecht. [19] Leighton, F. T. and Shor, P. W. (1989). Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms. Combinatorica 9 161–187. MR1030371 [20] McColm, G. (2004). Threshold functions for random graphs on a line segment. Combin. Probab. Comput. 13 373–387. MR2056406 [21] Muthukrishnan, S. and Pandurangan, G. (2003). The bin-covering technique for thresholding random geometric graph properties. Technical Report 2003-39, DIMACS. [22] Nevzorov, V. B. (2001). Records : A Mathematical Theory. Amer. Math. Soc., Providence, RI. MR1843029 [23] Penrose, M. D. (1997). The longest edge of the random minimal spanning tree. Ann. Appl. Probab. 7 340–361. MR1442317 [24] Penrose, M. D. (2003). Random Geometric Graphs. Oxford Univ. Press. MR1986198 [25] Shakkottai, S., Srikant, R. and Shroff, N. B. (2003). Unreliable sensor grids: Coverage, connectivity and diameter. In Proc. of IEEE Infocom 2 1073–1083. San Francisco, CA. [26] Shor, P. W. and Yukich, J. E. (1991). Minmax grid matching and empirical measures. Ann. Probab. 19 1338–1348. MR1112419

A. Goel Department of Management Science and Engineering and (by courtesy) Department of Computer Science Stanford University Stanford, California 94305 USA e-mail: ashishg@stanford.edu S. Rai Department of Management Science and Engineering Stanford University Stanford, California 94305 USA e-mail: sanat@stanford.edu

B. Krishnamachari Department of Electrical Engineering and Department of Computer Science University of Southern California Los Angeles, California 90089 USA e-mail: bkrishna@usc.edu