LucDevroye AndrásGyörgy GáborLugosi FredericUdina High-dimensionalrandomgeometricgraphsandtheircliquenumber

El e c t ro nic

Journ a l of

Pr

ob a b il i t y

Vol. 16 (2011), Paper no. 90, pages 2481–2508.

Journal URL

http://www.math.washington.edu/~ejpecp/

High-dimensional random geometric graphs and their clique number

Luc Devroye^∗ András György^† Gábor Lugosi^‡ Frederic Udina^‡

Abstract

We study the behavior of random geometric graphs in high dimensions. We show that as the di- mension grows, the graph becomes similar to an Erd˝os-Rényi random graph. We pay particular attention to the clique number of such graphs and show that it is very close to that of the corre- sponding Erd˝os-Rényi graph when the dimension is larger than log³nwherenis the number of vertices. The problem is motivated by a statistical problem of testing dependencies..

Key words:Clique number; dependency testing; geometric graphs; random graphs.

AMS 2010 Subject Classification:Primary 05C80; 62H15.

Submitted to EJP on October 1, 2010, final version accepted November 29, 2011.

∗School of Computer Science, McGill University, 3480 University Street Montreal, Canada H3A 2A7 (email: lucde- vroye@gmail.com). Supported by NSERC.

†Machine Learning Research Group, Computer and Automation Research Institute of the Hungarian Academy of Sci- ences, Kende u. 13-17, 1111 Budapest, Hungary (email: gya@szit.bme.hu). Partially supported by the National Devel- opment Agency of Hungary from the Research and Technological Innovation Fund (KTIA-OTKA CNK 77782), and by the PASCAL2 Network of Excellence (EC grant no. 216886).

‡Department of Economics, Pompeu Fabra University, Ramon Trias Fargas 25-27, 08005, Barcelona, Spain (email: ga- bor.lugosi@gmail.com and frederic.udina@gmail.com). G. Lugosi is also with ICREA. Supported by the Spanish Ministry of Science and Technology grant MTM2009-09063 and by the PASCAL Network of Excellence under EC grant no. 216886.

1 Introduction

Arandom geometric graphis defined bynindependent random points taking values inR^{d, drawn} from the same distribution. These points correspond to the vertices of the graph and two of them are joined by an edge if and only if their Euclidean distance is less than a certain threshold. Such random geometric graphs have been studied extensively and many of their basic properties are now well understood. We refer to Penrose[16]for an extensive treatment. These graphs are usually studied in an asymptotic framework when the numbernof vertices is very large (it grows to infinity) while the dimensiond is held fixed. However, in some applications it is of interest to consider situations when the dimension is large. In such cases the graph is expected to behave differently. In this paper we consider random geometric graphs defined by nindependent vectors uniformly distributed on the surface of the unit ball inR^d. We show that ifd → ∞whilenis held fixed, the random graph becomes, in a very strong sense, similar to an Erd˝os-Rényi random graph. Motivated by a hypothesis testing problem, we pay particular attention to the clique number of such random geometric graphs.

We show that if d is at least of the order of log³n, then the clique number is essentially the same as that of the corresponding Erd˝os-Rényi random graph. This is in sharp contrast to the behavior of the clique number when the dimension is fixed.

The paper is organized as follows. In Section 2 the basic model is described and the asymptotic equivalence of the random geometric graph and the Erd˝os-Rényi random graph is presented (The- orem 2). In Section 3 the main results of the paper are stated and proved on the behavior of the clique number of high-dimensional random geometric graphs. In Section 4 some numerical experi- ments are reported in which the behavior of the clique number is illustrated. In Section 5 we show a statistical application that motivated our research. We describe a hypothesis testing problem arising in applications of remote sensing and finance and propose a test based on computing the clique number of random geometric graphs. Finally, the Appendix contains some of the proofs of results announced in Sections 3 and 5.

2 Notation, set-up

Denote the unit sphere inR^{d by S}_d−1 ={x ∈R^{d :}kxk= 1}where k · k stands for the Euclidean norm. LetX₁, . . . ,X_nbe independent vector-valued random variables, uniformly distributed inS_d−1. We denote the components of the random vector X_i by X_i = (Xi,1, . . . ,X_i,d). For a given value of p ∈ (0, 1) (possibly depending on n and d) we define the random geometric graph G(n,d,p) as follows: the graph hasnvertexes labeled by 1, . . . ,nand vertexiand vertex jare connected by an edge if an only if

€X_i,X_jŠ

≥t_p,d ,

where(x,y)denotes the inner product of the vectorsx and yand t_p,d is determined such that the probability of each edge equalsp, that is,

P^¦€Xi,X_jŠ

≥t_p,d©

=p.

Equivalently, vertexiand vertex j are connected if and only ifkX_i−X_jk ≤p

2(1−t_p,d).

For example, for p = 1/2, t_p,d = 0. To understand the behavior of t_p,d as a function of p, we introduce some notation. Letµ_d−1 denote the uniform probability measure over S_d−1. For a unit

t 1−t u Cd−1(u, t)

Figure 1: A spherical cap of height 1−t.

vectoru∈S_d−1 and real number 0≤t≤1, letC_d−1(u,t) ={x∈R^d:x ∈S_d−1,(x,u)≥t}denote a spherical cap of height 1−t aroundu (see Figure 1). Theangleof a spherical cap C_d−1(u,t) is defined by arccos(t).

Then p = µd−1(Cd−1(e,t_p,d)) is the normalized surface area of a spherical cap of height 1−t_p,d centered at (say) the first standard basis vectore= (1, 0, 0, . . . , 0). The following estimates for the measure of a spherical cap will be used (see Brieden et al.[6]): forp

2/d≤t_p,d≤1, 1

6t_p,dp

d(1−t²_p,d)^d−21 ≤p≤ 1 2t_p,dp

d(1−t²_p,d)^d−21 . (1) These bounds show that ifpis fixed andd is large,t_p,d is of the order of 1/p

d.

Sometimes it is useful to think about random points onS_d−1 as projections of Gaussian vectors on the unit sphere. In particular, letZ₁, . . . ,Z_n be independent standard normal vectors (i.e.,Z_i has mean0= (0, . . . , 0)and unit covariance matrix). Then the vectors

X₁= Z₁

kZ₁k, . . . ,X_n= Z_n kZ_nk

are independent and uniformly distributed onS_d−1. This representation will be used in some proofs.

For example, this representation may be used to determine the asymptotic value of t_p,d. Let Z = (Z₁, . . . ,Z_d)be a standard Gaussian vector and letX=Z/kZk= (X₁, . . . ,X_d). Observe thatEkZk²= d. Also, by the law of large numbers,kZk/p

d→1 in probability. This implies thatX₁p

d converges, in distribution, to a standard normal random variable. In fact, for any fixedk, the joint distribution ofp

d(X₁, . . . ,X_k)is asymptotically standard normal. One consequence of this is that for anys>0, µd−1(C_d−1(e,s/p

d)) =P{X₁>s/p

d}=P{Z₁/kZk>s/p

d} →1−Φ(s)

as d → ∞where Φ(x) = (2π)^−1/2Rx

−∞e^−t2/2d t is the standard normal distribution function. This implies thatt_p,d satisfies, for any fixed p∈(0, 1),

d→∞lim t_p,dp

d= Φ⁻¹(1−p). (2)

Later we will need a quantitative estimate of the rate of convergence. Such a bound is given by the next lemma, proved in Appendix C.

Lemma 1. Assume0<p≤1/2and d≥max¦

(2/p)², 27© . Then

|t_p,d p

d−Φ⁻¹(1−p)| ≤U_p,d , where

U_p,d=κp

plnd/d+κ⁰_p/p d . withκ_p=2p

2Φ⁻¹(1−p)andκ⁰_p=2p

2πe(^{Φ−1(1−p/2)})^2/2.

One of the main messages of this paper is that the random geometric graph G(n,d,p) defined above behaves like an Erd˝os-Rényi random graph whend is large. An Erd˝os-Rényi random graph G(n,p) is defined as a graph on nvertices such that any pair of vertices is connected by an edge with probability p and all edges are present independently. TheG(n,p)random graph model was introduced by Erd˝os and Rényi[10]and most of its properties are well understood – see Bollobás [5], Palmer[15], Janson, Łuczak, and Ruci´nski[11]for monographs dedicated to the subject.

First we point out that asymptotically (i.e., as d → ∞), the random geometric graph G(n,d,p) converges to G(n,p) in total variation distance. However, our proof only implies a small total variation distance for astronomically large values ofd. Certain characteristics ofG(n,d,p)resemble those of G(n,p)for moderate values of d. In Section 3 we show that when(log³n)/d =o(1), the clique numbers of the two random graphs behave quite similarly.

The next theorem states that the distribution of the random geometric graphG(n,d,p)converges to that of the Erd˝os-Rényi random graphG(n,p)in total variation distance. The total variation distance between two random graphsG andG⁰defined on the same set of vertices (say{1, . . . ,n}) is defined by

d_{T V}(G,G⁰) =max

G |P{G∈ G } −P{G⁰∈ G }|=1 2

X

g

|P{G=g} −P{G⁰= g}|,

where the maximum is taken over all 2²⁽

n 2)

setsG of graphs over nvertices and the sum is taken over all such graphs.

Theorem 2. Fix a positive integer n and0≤p≤1. Then

dlim→∞d_{T V}(G(n,d,p),G(n,p)) =0 .

The proof, given in Appendix A, is based on a relatively straightforward application of the multivari- ate central limit theorem.

Theorem 2 shows that, asymptotically, the random geometric graph behaves like an ordinary random graph. However, by the bounds provided by the proof, astronomical values ofdare required to make

the total variation distance small. (Just note that the total variation distance is the sum over all 2(ⁿ2) possible graphs g and therefored needs to be much bigger than 2ⁿ² in order to make the obtained bound meaningful.) For this reason, the interest in Theorem 2 is purely theoretical.

On the other hand, the notion by which Theorem 2 relates the random geometric graph to an ordinary random graph is very strong. If one is interested in simple characteristics ofG(n,d,p), it may behave as that ofG(n,p)for much smaller values ofd. The main result of the paper, presented in the next section, shows that if d is poly-logarithmic in n, then the clique number of G(n,d,p) already behaves very similarly to that of G(n,p). At the same time, for values of d significantly smaller than logn, the clique number behaves very differently.

In this paper we study the (random) clique numberω(n,d,p)ofG(n,d,p), that is, the number of vertices in the largest clique contained inG(n,d,p). It is well-known (see, e.g., Bollobás [5]) that the clique number of the Erd˝os-Rényi random graphG(n,p)is, with probability converging to one, within a constant of 2 log_1/pn−2 log_1/plog_1/pnwhen p is held fixed as ngrows. This is in sharp contrast with the behavior ofω(n,d,p)for small values of d. It is easy to see that for any fixedd, the clique number grows linearlywith n and even for d = εlogn, for sufficiently small values of ε >0,ω(n,d,p)grows asn^αwhereα→1 asε→0 (see Proposition 4 below).

Theorem 2 implies that, for very large values ofd,ω(n,d,p)behaves similarly to the clique number ofG(n,p). The more interesting question is how larged needs to be. The main result of the paper (Theorem 3) establishes that when d is about log³n, the behavior of the clique number is already similar to that of G(n,p)(for fixed p). This result is complemented by Theorem 5 which implies that ford∼(3 logn)², we haveω(n,d,p) =O_p(log³n).

3 The clique number of G ( n, d , p )

The following result describes the behavior of the clique number of the random geometric graph G(n,d,p)for large values ofd.

Theorem 3. Fix p≤1/2and define the positive constant p⁰=p⁰(p) =

¨ 1/2 if p=1/2 1−Φ(2Φ⁻¹(1−p) +2.5) if p<1/2.

Letδ_n∈(0,p)and suppose

d=d_n≥ κbp

δ²_n log³_1/(p−δ

n)n

where bκp = 65 ln²(1/p⁰). If either δn → 0 or δn ≡ δ for some constant 0 < δ < p, then, with probability converging to1(as n→ ∞),

ω(n,d,p)≤2 log_1/(p+δ

n)n−2 log_1/(p+δ

n)log_1/(p+δ

n)n+O(1). Also, iflim sup_n→∞δnlog²n<∞, then with probability converging to1,

ω(n,d,p)≥2 log_1/(p−δ

n)n−2 log_1/(p−δ

n)log_1/(p−δ

n)n+ Ω(1).

Observe that the theorem implies that if d is about log³n thenω(n,d,p) is already of the order of logn. This is obtained by choosing δn as a constant. By letting δn go to zero slowly, we see that if(log³n)/d =o(1)thenω(n,d,p)≤(2+o(1))log_1/pn. Finally, by takingδn ∼1/logn, we obtain that whend∼log⁵nthenω(n,d,p)≤2 log_1/pn−2 log_1/plog_1/pn+O(1)and therefore the clique number is at most as large as in an Erd˝os-Rényi random graph, up to an additive constant.

For the lower bound, we need the extra condition thatδn = O(1/log²n) and therefore the lower bound is only meaningful ford at least of the order of log⁷n. We believe that this condition is not necessary. In fact, we conjecture that for fixed d and p, the clique number is non-increasing in d (in the stochastic sense thatP{ω(n,d,p)≥k}is non-increasing for each k). If this conjecture was true that the lower bound would hold without any condition for d simply because, as d → ∞, by Theorem 2,ω(n,d,p)converges, in distribution, to the clique number of the Erd˝os-Rényi random graph.

The theorem follows from Theorems 8 and 9 (together with the observation that p⁰ ≤min(bp,ep)) which are shown in Section 3.2. Before turning to the proof we note that for small values of d, ω(n,d,p)behaves in an entirely different way, as the next simple proposition shows.

Proposition 4. If d≥8,

Eω(n,d,p)≥ n 3p

d(1+t²_p,d)







 1−

1+t²_p,d

2

4









d−1 2

.

The proposition follows simply by observing that if k points fall in any spherical cap C of angle arccos(tp,d)/2 that is, a spherical cap of height 1−(1+t²_p,d)/2, then they are mutually connected and therefore form a clique. The expected number of points that fall in any such fixed cap C is nµd−1(C)which, by (1) is at least

n 1

3p

d(1+t²_p,d)







 1−

1+t²_p,d2

4









d−1 2

provided p

2/d ≤ (1+t²_p,d)/2. This lower bound may be improved by packing as many non- overlapping spherical caps of height 1−(1+t²_p,d)/2 inS_d−1 as possible and considering the one containing the largest number of points. Even though the number of such caps is exponentially large ind, the refined bound is not significantly better than the one obtained above. The negligible benefit does not justify the inclusion of the more technical details.

On the one hand, Proposition 4 above shows that ifd logn, the clique number grows linearly, or almost linearly, with nwhile according to Theorem 3, ifd is at least of the order of log³n, the clique number is logarithmic inn. The next result, using very different techniques, shows that when d ∼log²n, then the clique number is already poly-logarithmic inn, at least for p<1/2. The proof is given in Appendix B.

Theorem 5. For any p<1/2and0< η <1, the clique numberω(n,d,p)of the random geometric graph G(n,d,p)satisfies, with probability at least1−η,

ω(n,d,p)≤n

È d+1

d(d tp,d+1)exp

‚−(d−1)(d t_p,d+1) 2(d+1)

Œ

+4(d+1)ln 2ne

d+1+4 ln4 η .

To interpret this bound, recall that forp<1/2 fixed andd large,t_p,d≈d^−1/2Φ⁻¹(1−p). Thus, the upper bound is of the ordernd^−1/2exp(−d^1/2/2) +dlog(n/d). Thus, whend∼(3 logn)², we have ω(n,d,p) =O_p(log³n). Notice also that as soon asd→ ∞,ω(n,d,p) =o_p(n).

3.1 The expected number of cliques

The proof of Theorem 3 is based on the first and second moment methods (see, e.g., Alon and Spencer[2]). To this end, first we need to study the expected number of cliques of size k in the random geometric graphG(n,d,p). In particular, we compare it to the expected number of cliques of the same size inG(n,p)which is

n k

p(^k2) .

Denote the (random) number of cliques of sizekbyN_k=N_k(n,d,p). But E^Nk=

n k

P{X₁, . . . ,X_k form a clique}

and therefore it suffices to study the probability thatkpoints are all connected with each other. Let p_k=p_k(d,p) =P{X₁, . . . ,X_kform a clique}denote this probability.

The cases whenp=1/2 and p<1/2 are slightly different and we treat them separately.

Theorem 6. (UPPER BOUND FOR THE EXPECTED NUMBER OF CLIQUES.) Let K≥2be a positive integer, letδn>0, and define

bp=bp(p) =1−Φ(t_p,d pd) Assume

d≥

8(K+1)²ln¹

bp

δ²_n

Kln4

bp+lnK−1 2

. Then, for any1≤k≤K,

E^Nk(n,d, 1/2)≤e n

k

Φ(δn)(^k2) . Furthermore, for p<1/2, defineβ =2p

ln(4/bp)and forβp

K/d<1, letα=Æ

1−βp

K/d. Then for any0< δ_n< αtp,d

pd we have, for any1≤k≤K,

E^Nk(n,d,p)≤e^1/

p2

n k



1−ց αtp,d

p

d−δ_n‹‹(^k2) .

Remark. Note that (2) implies that asα→1 andδn→0, 1−Φ€ αt_p,dp

d−δn

Š→p.

Proof. Fix ak ≤K. We use the Gaussian representation of the X_i described in Section 2. That is, we write X_i =Z_i/kZ_ikwhereZ₁, . . . ,Z_n are independent standard normal vectors inR^{d. First we} perform Gram-Schmidt orthogonalization forZ^k−₁ ¹=Z₁, . . . ,Z_k−1. In other words, let

v₁= Z₁ kZ₁k

and definer₁=0(thed-dimensional zero vector). For j=2, . . . ,k−1, introduce, recursively, r_j=

j−1

X

i=1

(Z_j,v_i)v_i and v_j= Z_j−r_j kZ_j−r_jk . Thenv₁, . . . ,v_k−1are orthonormal vectors, depending onZ^k₁⁻¹ only.

First we treat the casep<1/2. Introduce the “bad” event B_k−1=

∃j≤k−1 :kr_jk²>2(k+1)²ln(1/bp)or∃j≤k−1 :kZ_jk²< d 2

and write

p_k ≤ P{X₁, . . . ,X_kform a clique,B_k^c₋₁}+P{B_k−1}

= E

– P

¨‚ Z_k kZ_kk, Z_j

kZ_jk

Œ

≥t_p,d for all j≤k−1|Z^k−1₁

«

I_{X₁,...,X_k−1form a clique}I_{B_k−^c ₁}

™

+P{B_k−1}. (3)

Now fixZ^k₁⁻¹ such thatX₁, . . . ,X_k−1 form a clique andB_k−1does not occur. Then, for anyδ_n>0, P

¨‚ Z_k kZ_kk, Z_j

kZ_jk

Œ

≥t_p,d for all j≤k−1|Z^k₁⁻¹

«

= P

¨‚

Z_k, r_j

kZ_jk+kZ_j−r_jk kZ_jk v_j

Œ

≥t_p,dkZ_kkfor all j≤k−1|Z^k₁⁻¹

«

≤ P

¨‚

Z_k,kZ_j−r_jk kZ_jk v_j

Œ

≥t_p,dkZ_kk −δnfor all j≤k−1|Z₁^k−1

«

+

k−1

X

j=1

P

¨‚

Z_k, r_j kZ_jk

Œ

≥δn|Z^k₁⁻¹

«

. (4)

For any fixed 1≤ j≤k−1 andδn>0, P

¨‚

Z_k, r_j kZ_jk

Œ

≥δ_n|Z^k₁⁻¹

«

≤ P^n€Zk,r_jŠ

> δ_np

d/2|Z^k₁⁻¹ o

≤ 1 2e⁻

δ2 n d 4krjk2

≤ 1 2e

−8(k+1)2 ln 1^{δ2n d}

bp , (5)

where we used the fact that, conditionally onZ₁^k−1, (Z_k,r_j)has centered normal distribution with variancekr_jk²≤2(k+1)²ln(1/bp). Furthermore, onB_k−^c ₁, for any 0< α <1, ifαtp,d

pd> δn then

P

¨‚

Z_k,kZ_j−r_jk kZ_jk v_j

Œ

≥t_p,dkZ_kk −δn for all j≤k−1|Z^k−1₁

«

≤ P

§€ Z_k,v_jŠ

≥t_p,dαp

d−δn for all j≤k−1|Z^k−1₁

ª+P{kZ_kk< αp

d} (6)

≤



1−ց αt_p,dp

d−δn

‹‹_k−1

+e^−(1−α)

2d

4 , (7)

where we used the fact that by rotational invariance of the multivariate standard normal distribu- tion, the (Z_k,v₁), . . . ,(Z_k,v_k−1) are independent standard normal random variables, and the last term follows from the standard tail bound on theχ²distribution

P{χ_d²<d−2p

d t} ≤e^−t (8)

witht= (1−α²)²d/4, whereχ_d²denotes a random variable withχ²distribution withd degrees of freedom (see, e.g., Massart[13]). Therefore, the first term in (3) can be bounded as

E

– P

¨‚ Z_k kZ_kk, Z_j

kZ_jk

Œ

≥t_p,d for all j≤k−1|Z₁^k−1

«

I_{X₁,...,X_k−1form a clique}I_{B^c_k

−1}

™

≤ p_k−1

‚

1−ց αtp,d

p d−δn

‹‹k−1

+e^−(1−α

2)2d

4 + k−1

2 e⁻

δ2 n d 8(k+1)2 ln(1/bp)

Œ

. (9)

Using the definition ofα, the second term above may be bounded, by e^−(1−α

2)2d

4 ≤

bp 4

K

. The last term in (9) can also be bounded by(bp/4)^K using

δ²_n≥

8(k+1)²ln¹

bp

d

Kln4

bp +lnk−1 2

. Thus, (9) is bounded from above as

p_k−1

‚

1−ց

αt_p,dp

d−δ_n‹‹_k−1

+e⁻⁽

1−α2)2d

4 +k−1

2 e⁻

δ2 n d 8(k+1)2 ln(1/bp)

Œ

≤ p_k−1

‚

1−ց

αt_p,dp d−δn

‹‹k−1

+2

bp 4

KŒ

≤ p_k−1€

1+2^−3K+kŠ

1−ց

αt_p,dp

d−δ_n‹‹_k−1

, (10)

where we used the fact thatbp≤1−Φ€ αtp,d

pd−δn

Š<1/2 (asαtp,d

pd> δnby our assumptions).

We may bound the probability of the “bad” event as follows.

P{B_k−1} ≤ P

∃j≤k−1 :kr_jk²>2(k+1)²ln1 bp

+P

∃j≤k−1 :kZ_jk²< d 2

≤ (k−1)P

χ_k−² ₁>2(k+1)²ln1 bp

+ (k−1)P

χ_d²< d 2

.

Here the second term can be bounded by using the tail inequality (8) with t =d/16, which yields P{χ_d²<d/2} ≤e^−d/16. The first term can be bounded using the standard tail bound

P{χ_l²−l>2t+2p

l t} ≤e^−t (11)

(see[13]) with

t=

q

4(k+1)²ln¹

bp)−p k−1

‹2

4 = (k+1)²ln1

bp− q

(k−1)

4(k+1)²ln¹

bp)−k+1 2

andl =k−1, which implies

P{χ_k−1² >2(k+1)²ln(1/bp)} ≤e^{−2(k+1)2ln(1/bp)/4}=bp^(k+1)2/2. Thus

P{B_k−1} ≤(k−1)

bp^(k+1)2/2+e^−d/16

. (12)

If, in addition,d≥8(k+1)²ln(1/bp), we obtain

P{B_k−1} ≤2(k−1)bp^(k+1)2/2, (13) and so, by (3), (9) and (10) we have

p_k≤p_k−1€

1+2^−3K+kŠ

1−ց

αt_p,dp d−δn

‹‹_k−1

+2(k−1)bp^(k+1)2/2. (14) Next we show that

p_k≤



1−ց αtp,d

p d−δn

‹‹(^k2)^k−Y¹

j=1

(1+2^−j−1/2) (15)

which finishes the proof of the theorem forp<1/2 sinceQ_k

j=1(1+2^−j−1/2)≤e

Pk

j=12^−j−1/2<e^{1/sqr t2}. We proceed by induction. (15) trivially holds fork=1. Assuming it holds fork−1 for somek≥2, from (14) we obtain

p_k ≤



1−ց

αt_p,dp d−δn

‹‹(^k−2¹)





k−2

Y

j=1

(1+2^−j−1/2)







€1+2^−3K+kŠ

1−ց αt_p,dp

d−δn

‹‹k−1

+2(k−1)bp^(k+1)2/2

≤



1−ց αtp,d

p d−δn

‹‹(^k2)





k−2

Y

j=1

(1+2^−j−1/2)







1+2^−3K+k+2(k−1)2^−3k+21

≤



1−ց αtp,d

p d−δn

‹‹(^k2)Y^k−1

j=1

(1+2^−j−1/2)

where we used thatbp≤1−Φ€ αt_p,dp

d−δn

Š <1/2 (asαt_p,dp

d > δn by our assumptions) and that 2^−3K+k+2(k−1)2^−3k+12 <2^−k+1/2forK≥2 since 2(k−1)2^−k/2≤3/2 for allk. This completes the proof of (15), and hence that of the theorem forp<1/2.

Forp=1/2, we need the following modifications. B_k−1 is now defined as B_k−1=

∃j≤k−1 :kr_jk²>2(k+1)²ln 2 or ∃j≤k−1 :kZ_j−r_jk²< d 2

.

Then (3) still holds, but instead of (4) we write P

¨‚ Z_k kZ_kk, Z_j

kZ_jk

Œ

≥0 for all j≤k−1|Z^k₁⁻¹

«

≤ P^¦€Zk,v_jŠ

≥ −δ_n for all j≤k−1|Z^k₁⁻¹© +

k−1X

j=1

P

¨‚

Z_k, r_j kZ_j−r_jk

Œ

> δ_n|Z^k₁⁻¹

« .

From here, similarly to (5) and (7), the following analog of (9) can be obtained:

E h

P^¦€Xk,X_jŠ

≥t_p,d for all j≤k−1|Z^k₁⁻¹©

I_{X₁,...,X_k−1form a clique}I_{Bk^c

−1}

i

≤ p_k−1

‚

1−Φ −δn

k−1

+k−1 2 e⁻

δ2 n d 8(k+1)2 ln 2

Π.

As the bound (12) remains valid for the redefined B_k−1 (with bp=1/2), the proof may be finished as before ford≥8(k+1)²ln 2 and

δ²_n≥ 8(K+1)²ln 2 d

Kln 4

Φ(δ_n)+lnK−1 2

.

Theorem 7. (LOWER BOUND FOR THE EXPECTED NUMBER OF CLIQUES.)Introduce

ep=ep(p) =

(1/2 if p=1/2;

1−Φ€ 2t_p,dp

d+1Š

if p<1/2;

and letδn∈(0, 2/3]and K≥3. Assume

d> 8(K+1)²ln¹

ep

δ²_n

Kln4

ep+ln(K−1) 2

. (16)

Then, for any1≤k≤K,

E^Nk(n,d, 1/2)≥ 4 5

n k

1−Φ(δn)(^k2) . For p<1/2, defineα >0as

α²=1+ r8K

d ln4 ep . Then

E^Nk(n,d,p)≥ 4 5

n k

€1−Φe_K(d,p)Š(^k2) , (17)

whereΦeK(d,p) = Φ ^αtp,d

pd+δn

q

1−2(K+1)2 ln(1/ep) d

! .

Proof. The proof is a simple variant of the previous theorem, and we use the notation introduced there. Fix ak≤K. Define the “bad” eventBe_k−1as

Be_k−1=

∃j≤k−1 :kr_jk²>2(k+1)²ln(1/ep)or ∃j≤k−1 :kZ_j−r_jk²< d 2

. (18)

Then

p_k ≥ P{X₁, . . . ,X_kform a clique ,eB_k^c₋₁} (19)

= E

– P

¨‚ Z_k kZ_kk, Z_j

kZ_jk

Œ

≥t_p,d for all j≤k−1|Z₁^k−1

«

I_{X1,...,X_k−1form a clique}I_{eB^c

k−1}

™

FixZ₁, . . . ,Z_k−1 such that they form a clique andBe_k−1does not occur. Then P

¨‚ Z_k kZ_kk, Z_j

kZ_jk

Œ

≥t_p,d for all j≤k−1|Z^k−₁ ¹

«

≥ P

¨‚

Z_k,kZ_j−r_jk kZ_jk v_j

Œ

≥t_p,dkZ_kk+δ_nfor all j≤k−1|Z^k₁⁻¹

«

−

k−1X

j=1

P

¨‚

Z_k, r_j

kZ_jk≤ −δ_n

Œ

|Z^k₁⁻¹

«

. (20)

Now for anyα >1, the first term can be bounded as P

¨‚

Z_k,kZ_j−r_jk kZ_jk v_j

Œ

≥t_p,dkZ_kk+δnfor all j≤k−1|Z^k₁⁻¹

«

≥ P









Z_k, r

1−2(k+1)²ln(1/ep)

d v_j



≥t_p,dkZ_kk+δ_nfor all j≤k−1|Z^k₁⁻¹







≥ P







€Z_k,v_jŠ

≥ αtp,d

pd+δ_n q

1−^2(k+1)2_d^ln(1/ep)

for all j≤k−1|Z₁^k−1







−P

§

kZ_kk> αp d

ª

≥ €

1−Φek(d,p)Š_k−1

−e⁻

d

4·^(α2_α⁻2¹⁾² , (21)

where the first inequality holds since r_j andZ_j−r_j are orthogonal andkr_jk²<2(k+1)²ln(1/ep) onBe_k−1, implyingkZ_j−r_jk/kZ_jk ≥p

1−2(k+1)²ln(1/ep)/d, and the last inequality follows again by (11) (witht = ^d₄·^(α2_α⁻2¹⁾²) and the fact that the(Z_k,v₁), . . . ,(Z_k,v_k−1)are independent standard normal random variables. The second term in (20) can be bounded similarly to (5). The conditions

of the theorem forαanddimply P

¨‚ Z_k kZ_kk, Z_j

kZ_jk

Œ

≥t_p,d for all j≤k−1|Z₁^k−1

«

≥ €

1−Φek(d,p)Š_k−1

−e⁻

d

4·^(α2_α⁻2¹⁾² − k−1 2 e

−8(k+1)2 ln 1^{δ2n d}

ep (22)

≥ €

1−Φek(d,p)Š_k−1

−2

ep 4

K

≥ €

1−Φe_k(d,p)Šk−1€

1−2^−2K+1Š

(23) where at the last step we used the fact thatep<1−Φek(d,p)<1/2,¹

To finish the proof of (17), we proceed, again, by induction, to prove that p_k≥η^k_K 1−

k

X

i=2

4⁻ⁱ

!

€1−Φek(d,p)Š(^k2)

withηK =€

1−2^−2K+1Š

. This is sufficient to prove the theorem becauseη^k_K 1−Pk

i=24⁻ⁱ

>4/5 for allk≤KwhenK≥3. This clearly holds fork=1. Assuming it holds for somek−1,k≥2, and taking into account that, similarly to (13),

P{Be_k−1} ≤2(k−1)ep^(k+1)2/2≤2(k−1)€

1−Φek(d,p)Š_(k+1)²/2

, we obtain

p_k ≥ ηK

€1−Φek(d,p)Šk−1€

p_k−1−P{Be_k−1}Š

+

≥ ηK

€1−Φek(d,p)Š_k−1

× η^k−_K ¹ 1−

k−1

X

i=2

4⁻ⁱ

!

€1−Φek(d,p)Š(^k−2¹)

−2(k−1)€

1−Φek(d,p)Š₍k+1)²/2

!

+

= ηK

€1−Φek(d,p)Š(^k2) η^k−_K ¹ 1−

k−1

X

i=2

4⁻ⁱ

!

−2(k−1)€

1−Φek(d,p)Š₍5k+1)/2

!

+

≥ η^k_K€

1−Φe_k(d,p)Š(^k2) 1− Xk−1

i=2

4⁻ⁱ−4^−k

!

where x₊=max(x, 0)denotes the positive part of a real numberx and we used that 1−Φek(d,p)<

1/2 and 2(k−1)2^−k/2−1< η^k_K< η^k−_K ¹ for all 2≤k≤K whenK≥3.

1The second inequality is trivial. The first one can be obtained by noting that (16) impliesα≤p

1+δn≤1+δn/2 and 2(K+1)²ln(1/ep)/d< δ²_n/4. From here, usingδn≤2/3, we have

αt_p,dp d+δn

q

1−^2(K+1)2_d^ln(1/ep)

<(1+δn/2)t_p,dp d+δn

1−δn/2 <2tp,d

p d+1

which impliesep<1−ΦeK(d,p).