The bondage number of random graphs Dieter Mitsche Xavier P´erez-Gim´enez Pawe l Pra lat ∗ † ‡ 6 1 0 2 Abstract r A dominating set of a graph is a subset D of its vertices such that every vertex not in D is a M adjacent to at least one member of D. The domination number of a graph G is the number of vertices in a smallest dominating set of G. The bondage number of a nonempty graph G is the 0 size ofasmallestsetofedgeswhoseremovalfromGresultsinagraphwithdominationnumber 3 greater than the domination number of G. In this note, we study the bondage number of the binomial randomgraphG(n,p). We obtain a lower bound that matches the order of the trivial ] O upper bound. As a side product, we give a one-point concentration result for the domination number of G(n,p) under certain restrictions. C . h t 1 Introduction a m Inthispaper,weconsidertheErd˝os-R´enyi randomgraph process,whichisastochasticprocess [ that starts with n vertices and no edges, and at each step adds one new edge chosen uniformly at 2 random from the set of missing edges. Formally, let e ,e ,...,e be a random permutation of v 1 2 (n) 2 9 the edges of the complete graph K . The graph process consists of the sequence of random graphs n 6 (n) 1 ( (n,m)) 2 , where (n,m) = (V,E ), V = [n] := 1,2,...,n , and E = e ,e ,...,e . It is 0 cGlear thatm=(0n,m) is Ga graph taken umniformly at ran{dom from}the set omf all{gr1aph2s on nmv}ertices 0 G and m edges (see, for example, [2, 6] for more details.) . 2 Our results refer to the random graph process. However, it will be sometimes easier to work 0 5 with the G(n,p) model instead of (n,m). The (binomial) random graph G(n,p) consists of the G 1 probability space (Ω, ,Pr), where Ω is the set of all graphs with vertex set [n], is the family of : F F v all subsets of Ω, and for every G Ω, i ∈ X r Pr(G) = p|E(G)|(1 p)(n2)−|E(G)|. a − This space may be viewed as the set of outcomes of n independent coin flips, one for each pair 2 u,v of vertices, where the probability of success (that is, adding edge uv) is p. Note that p = p n { } (cid:0) (cid:1) may (and usually does) tend to zero as n tends to infinity. All asymptotics throughout are as n (we emphasize that the notations o() and O() refer → ∞ · · to functions of n, not necessarily positive unless otherwise stated, whose growth is bounded; on the other hand, functions hidden in Θ() and Ω() notations are positive). We use the notation a b n n · · ∼ to denote a = (1+o(1))b . A sequence a satisfies a certain property eventually if the property n n n ∗e-mail: [email protected], Universit´e de Nice Sophia-Antipolis, Laboratoire J.A. Dieudonn´e, Parc Valrose, 06108 Nicecedex 02, France †e-mail: [email protected], Department of Mathematics, Ryerson University,Toronto, ON, Canada ‡e-mail: [email protected], Department of Mathematics, Ryerson University, Toronto, ON, Canada; research partially supported byNSERCand Ryerson University 1 holds for all but finitely many terms of the sequence. We say that an event in a probability space holds asymptotically almost surely (or a.a.s.) if the probability that it holds tends to 1 as n goes to infinity. We often write (n,m) and G(n,p) when we mean a graph drawn from the G distribution (n,m) and G(n,p), respectively. All logarithms in this paper are natural logarithms. G A dominating set for a graph G = (V,E) is a subset D of V such that every vertex not in D is adjacent to at least one member of D. The domination number, γ(G), is the number of vertices in a smallest dominating set for G. The bondage number, b(G), of a non-empty graph G is the smallest number of edges that need to be removed in order to increase the domination number; that is, b(G) = min B :B E,γ(G B)> γ(G) . {| | ⊆ − } (If G has no edges, then we define b(G) = .) This graph parameter was formally introduced ∞ in 1990 by Fink et al. [3] as a parameter for measuring the vulnerability of the interconnection network under link failure. However, it was considered already in 1983 by Bauer at al. [1] as “domination line-stability”. Moreover, graphs for which the domination number changes upon the removal of a single edge were investigated by Walikar and Acharya [7] in 1979. One of the very first observations [1, 3] is the following upper bound: b(G) min deg(x)+deg(y) 1 ∆(G)+δ(G) 1, ≤ xy E{ − } ≤ − ∈ where ∆(G) and δ(G) are the maximum and, respectively, the minimum degree of G. Since a.a.s. ∆(G(n,p)) δ(G(n,p)) pnprovidedpn logn(thisfollowsimmediatelyfromChernoff’sbound ∼ ∼ ≫ stated below, and the union bound), we get that a.a.s. b(G(n,p)) 2pn(1+o(1)) (1) ≤ for pn logn. For denser graphs, one can improve the leading constant of this upper bound by ≫ using the following observation of Hartnell and Rall [5]: b(G) min deg(x)+deg(y) 1 N(x) N(y) . ≤ xy E{ − −| ∩ |} ∈ It follows that if p = Ω(1), then a.a.s. b(G(n,p)) (2p p2)n(1+o(1)). ≤ − Today, many properties of the bondage number are studied. For more details the reader is directed to the survey [9] which cites almost 150 papers on the topic. 2 Results Our goal is to investigate the bondage number of the binomial random graph on n vertices and of the random graph process. Throughout the whole paper we will exclude the case p = p 1 and n → also assume that p does not tend to zero too fast. More precisely, our main results require that p = p eventually satisfies n n 1/3+ε p 1 ε, (2) − ≤ ≤ − for some constant ε> 0, but most arguments only require the following, milder, constraint: log2n/√n p 1 ε. ≪ ≤ − 2 Sinceourresults areasymptotic in n,we willassumethat nis large enough sothatall requirements intheargumentaremet. (Inparticular,thenotation “eventually” isoftenimplicitly assumedinthe proofs and omitted.) Let be the set of dominating sets of size k of G(n,p), and let X = . k k k D |D | Clearly, n n k f(n,k,p) := EX = 1 (1 p)k − . (3) k k − − (cid:18) (cid:19) (cid:16) (cid:17) For a given p = p , let n r = r = min k N : f(n,k,p)> 1/(pn) . (4) n { ∈ } Since pn √nlog2n > 1 (eventually) and f(n,n,p) = 1, the function r is well defined for n ≫ sufficiently large. 2.1 Random Graph Process Consider the random graph process ( (n,m)) . Clearly, the random variable γ( (n,m)) is G 0≤m≤(n2) G a non-increasing function of m, γ( (n,0)) = γ(K ) = n, and γ( (n, n )) = γ(K ) = 1. Suppose G n G 2 n that at some point the domination number drops down, that is, there exists a value of m such that (cid:0) (cid:1) γ( (n,m)) = k+1 but γ( (n,m+1)) = k. The random graph process continues and, as long as G G the domination number remains to be equal to k, the bondage number, b( (n,m+ℓ)), is a non- G decreasingfunctionofℓ. Moreover, wegetthatb( (n,m+ℓ)) ℓ,asonecanremovethelastℓedges G ≤ that were added in the process (namely, e ,e ,...,e ) in order to increase the domination m+1 m+2 m+ℓ number. A natural and interesting question is then to ask how large the bondage number is right before the domination number drops again; that is, what can be said about b( (n,m+ℓ)) when G γ( (n,m+ℓ)) = k but γ( (n,m+ℓ+1)) = k 1? It turns out that, for the range of k we are G G − interested in, it is of the order of the maximum degree of (n,m+ℓ), and hence it matches the G trivial, deterministic, upper bound mentioned in the introduction (up to a constant multiplicative factor). Here is the precise statement. Theorem 1. Given any constant ε > 0, let k = k be such that eventually εlogn k n1/3 ε. n − ≤ ≤ Then, there exists m = m such that a.a.s. n γ( (n,m)) = k and b( (n,m)) = Θ(∆( (n,m))) = Θ(m/n). G G G 2.2 Binomial Random Graph Consider now the binomial random graph G(n,p). Before we state the main result for this prob- ability space, let us mention some technical difficulties one needs to deal with. Our one-point concentration result (below) on the domination number of G(n,p) amounts to showing that a.a.s. X 1 (since, trivially, a.a.s. X = 0 for all i r 1). Moreover, our claim about the bondage r i ≥ ≤ − number requires that a.a.s. X = Ω(pn) . This follows from the fact that the number of domi- r → ∞ nating sets of minimum cardinality is an upper bound on the bondage number (since each such set D must have a vertex v / D adjacent to only one vertex in D, and thus D can be neutralized by ∈ removing a single edge). Therefore, we will restrict ourselves to situations in which EX is large r enough and prove concentration of X around its mean. For technical reasons of the argument, we r will require the aforementioned condition to hold for two consecutive values n 1 and n (see (6) − and (7) in Theorem 3). This motivates the assumptions on the ratio p /p in the statement of n+1 n Theorem 2. We point out that, even for “natural” functions satisfying our assumptions, such as p = 1/2, n it is not clear whether there are always many dominating sets of minimum cardinality, or rather 3 X oscillates reaching both small and large values as n grows. All we managed to show is that, rn for such p , almost all values of n satisfy (6) and (7) and thus yield the bondage number as large n as possible. To make this precise, a set I N is said to be dense if ⊆ I [n] lim | ∩ | = 1. (5) n n →∞ In view of this definition, and recalling the definition of r = r in (4), our result for the binomial n random graph can be stated as follows. Theorem 2. Given any constant ε > 0, let p = p be such that eventually n 1/3+ε p 1 ε. n − ≤ ≤ − Moreover, suppose there exists a non-increasing non-negative sequence h = h such that p /p = n n+1 n 1 Θ(h /n). Then, there exists a dense set I N such that, with asymptotics restricted to n I, n − ⊆ ∈ a.a.s. γ(G(n,p)) = r and b(G(n,p)) = Θ(∆( (n,p))) = Θ(pn). G Although the conditions on p in Theorem 2 seem restrictive, many common and natural prob- n ability functions p satisfy it. For example, p = n 1/4, p = 1/loglogn and p = 1/2 meet the n n − n n requirements (by picking h = 1, h = 1/logn and h = 0, respectively). Other, seemingly more n n n complicated, choices such as p = (n+1) 1/4log3n+n 1/3 also satisfy our conditions. On the n − − other hand, mixed behaviours such as n 1/4 n even − p = n (1/loglogn n odd are not considered here. One can easily relax the conditions on p a bit further, but we do not aim n for it, as it does not appear to be possible to express that in terms of any “natural” assumptions such as “p being non-decreasing”. n 2.3 General Result In fact, both Theorem 1 and Theorem 2 are implied by the following, slightly more general, result. It is known that even for sparser graphs (namely, for p = p log2n/√n, but bounded away n ≫ from 1) a.a.s. the domination number of G(n,p) takes one out of two consecutive integer values, r or r +1, where r = r is defined in (4) (see [4] and also [8] for an earlier paper where denser n graphs were considered). The next result shows that if f(n,r,p) (that is, the expected number of dominating sets of cardinality r) is large, then we actually have one-point concentration and the bondage number is of order pn. Note that we may have to restrict asymptotics to an infinite subset of N that guarantees our assumptions on f. Theorem3. Givenanyconstantε > 0, suppose thatp = p eventuallysatisfiesn 1/3+ε p 1 ε, n − ≤ ≤ − and let f and r be defined as in (3) and (4). Suppose that there exists an infinite set I N and ′ ⊆ ω = ω such that n → ∞ EX = f(n,r,p) exp(ωlogn) (for n I ). (6) r ′ ≥ ∈ Then, a.a.s. γ(G(n,p)) = r (for n I ). ′ ∈ Moreover, suppose that I = n N :n I , n 1 I has infinite cardinality. (7) ′ ′ { ∈ ∈ − ∈ } Then a.a.s. b(G(n,p)) = Θ(∆(G(n,p))) = Θ(pn) (for n I). ∈ 4 Remark 4. (i) In many applications of Theorem 3 (for instance, in the proofs of Theorems 1 and 2), I is ′ a dense subset of N. Then, automatically I is also dense, and thus has infinite cardinality as required. (ii) The first part of the theorem, which characterizes the domination number of G(n,p), holds in fact for any p = p satisfying log2n/√n p 1 ε (see Corollary 9 below). n ≪ ≤ − The paper is structured as follows. In Section 3, we show that the results for (n,m) and G G(n,p) can be obtained from Theorem 3. Section 4 develops some tools required to estimate the second moment of X and some other random variables. Finally, Section 5 is devoted to prove r Theorem 3. 3 Preliminaries In this section we are going to introduce a few inequalities used in the paper, and we show some properties of the functions r = r and f(n,r,p) defined in (3) and (4). The function p will be n assumedtosatisfy(2). WewillalsoshowthatTheorem1andTheorem2areimpliedbyTheorem3. We will use the following version of Chernoff bound (see e.g. [6]): Lemma 5 (Chernoff Bound). If W is a binomial random variable with expectation µ, and 0 < δ < 1, then, setting ϕ(x) = (1+x)log(1+x) x for x 1 (and ϕ(x) = for x < 1), − ≥ − ∞ − δ2µ Pr[W < (1 δ)µ] exp( µϕ( δ)) exp ; (8) − ≤ − − ≤ − 2 (cid:18) (cid:19) and if δ > 0, δ2µ Pr[W > (1+δ)µ] exp . (9) ≤ −2+δ (cid:18) (cid:19) Given p = p [0,1), definep = log 1 . Note that p p (with equality only holdingat p = 0), n ∈ 1 p ≥ and − p p if p = o(1), b b ∼ p = Θ(1) if p = Θ(1) and 1 p = Θ(1), (10)  − pb if p 1. → ∞ → b We start with a few simple observations. Let us mention that some of the properties we show  b below are known and can be found in, for example, [4, Observation 2.1] (but mainly for p = o(1)). We present the proof here for completeness and to prepare the reader for similar calculations later on. Lemma 6. Assume log2n/√n p 1 ε for some constant ε > 0, and let r be defined as in (4). ≪ ≤ − Then, the following holds: 5 (i) 1 pn log (1+o(1)) if p = o(1) 1 pn p log2(pn) r = log (1+o(1)) =  (cid:18) (cid:19) p log2(pn) 1 bpn (cid:24) (cid:18) b (cid:19)(cid:25) pblog αlog2(pn) if p = Ω(1), (cid:18) (cid:19) for some 1+bo(1) α 1+o(1) = Θ(1).  b ≤ ≤ 1 p b − (ii) logn log2n r = Θ and (1 p)r = Θ . p − pn (cid:18) (cid:19) (cid:18) (cid:19) In particular, r = Ω(logn) and r = o(√n/logn). (iii) Moreover, if k = r+O(1), then f(n,k+1,p) = exp(Θ(log2n)). f(n,k,p) Proof. For a given function g = g = o(1), we define n 1 pn s = s (n,p) = log . g g p log2(pn)(1+g ) (cid:24) (cid:18) n (cid:19)(cid:25) b First, observe that for p in the range of discussion, log(pn) = Θ(logn). Then, it follows from (10) b that 1 logn s = Θ(log(pn)) O(loglog(pn)) = Θ . (11) g Θ(p) − p (cid:18) (cid:19) (cid:16) (cid:17) Also, from the definition of p and (10), we obtain (1 p)sg = Θ log2n . Hence, part (ii) will − pn follow, once we show that r = sg for some function gn = o(1). In p(cid:16)articul(cid:17)ar, proving part (i) will automatically yield part (ii). b Given any g = o(1), define g and g+ by n n− n 1 pn 1 pn s = log and s 1 = log . g p log2(pn)(1+g ) g − p log2(pn)(1+g+) (cid:18) n− (cid:19) (cid:18) n (cid:19) b b Since z z < z+1 for any z R, we obtain that g g g+. ≤ ⌈ ⌉ b ∈ n− ≤ n ≤b n Now we proceed to estimate f(n,s ,p) and f(n,s 1,p) for any g = o(1). Denoting by g g n − [n] = n(n 1)...(n k+1), and using Stirling’s formula (k! √2πk(k/e)k), we observe that k − − ∼ f(n,s ,p) = [n]sg 1 log2(pn)(1+g ) n(1−sg/n) g s ! − pn n− g (cid:18) (cid:19) nsg(1+O(s /n))sg log2(pn) log2n s g g = exp 1+g +O +O (1+o(1)) 2πbsg(sg/e)sg (cid:18)− p (cid:18) n− (cid:18) pn (cid:19) n (cid:19)(cid:19) (cid:16) (cid:17) 1+o(1) ne log2(pn) log2n p = exp s log 1+g +O , 2πs g s − p b n− pn g (cid:18) (cid:18) g(cid:19) (cid:18) (cid:18) (cid:19)(cid:19)(cid:19) since s = Θ(logn/pp) (by (11)) and p log2n/√n, which implies that g ≫ b (1+O(sg/n))sg = eO(s2g/n) = eO(log2n/(p2n)) 1 ∼ 6 and s /n = O(logn/(pn))= o(log2n/(pn)). Hence, g 1 log(pn)+O(loglogn) pn f(n,s ,p) exp log +O(1) g ∼ 2πsg p (cid:18) (cid:18)logn(cid:19) (cid:19) p log2(pn) log2n − b p 1+gn−+O pn ! (cid:18) (cid:18) (cid:19)(cid:19) p log2(pn) loglogn = Θ logn exp − pb gn− +O logn . (12) ! (cid:18)r (cid:19) (cid:18) (cid:18) (cid:19)(cid:19) Moreover, the same calculations leading to (12) are valid if we replace s by s 1 and g by g+, b g g − n− n so we also get p log2(pn) loglogn f(n,s 1,p) = Θ exp g+ +O . (13) g − logn − p n logn ! (cid:18)r (cid:19) (cid:18) (cid:18) (cid:19)(cid:19) In order to prove part (ii), we first take g = (loglogn)2/logn. From (13) and since g+ g , we n b n ≥ n obtain f(n,s 1,p) exp Ω((log2logn)log(pn)) = o(1/(pn)), g − ≤ − and thus (cid:0) (cid:1) f(n,j,p) < 1/(pn) for all 1 j s 1, g ≤ ≤ − since f(n,j,p) is increasing with respect to j in that range (this can be easily checked by looking at the ratio f(n,j + 1,p)/f(n,j,p) for j = O(logn/p) = o(√n)). Therefore, r > s 1 and, g − since both r and s are natural numbers, r s = s . On the other hand, if we set g g (loglogn)2/logn ≥ g = (loglogn)2/logn then, by (12) and since g g , n − n− ≤ n f(n,s ,p) n 1/4 logn exp Ω((log2logn)log(pn)) > 1/(pn), g − ≫ · and hence r s . Copmbining the(cid:0)two bounds, we conclu(cid:1)de that (loglogn)2/logn ≤ − r = s for some (loglogn)2/logn g (loglogn)2/logn, g n − ≤ ≤ which implies the first equality in part (i). The second equality follows immediately from setting α = 1/(1+g ) and the fact that 1 1 < 1 . n− 1+gn ≤ 1+gn− (1+gn)(1−p) Finally, let us move to part (iii). Using part (ii), it is easy to see that for k = r+O(1) we get f(n,k+1,p) = [n]k+1/(k+1)! 1−(1−p)k+1 n−k 1 (1 p)k+1 −1 f(n,k,p) [n] /k! 1 (1 p)k − − k (cid:18) − − (cid:19) (cid:16) (cid:17) n 1 (1 p)k +p(1 p)k n−k − − − ∼ k 1 (1 p)k (cid:18) − − (cid:19) pn n k = Θ 1+Θ(p(1 p)k) − logn − (cid:18) (cid:19) (cid:16) (cid:17) pn = Θ exp Θ(pn(1 p)k) logn − (cid:18) (cid:19) (cid:16) (cid:17) pn = Θ exp Θ(log2n) = exp Θ(log2n) . logn (cid:18) (cid:19) (cid:0) (cid:1) (cid:0) (cid:1) This finishes the proof of the lemma. 7 Now, we will show that Theorem 1 can be obtained from Theorem 3. Proof of Theorem 1. Let k = k be such that εlogn k n1/3 ε for some ε > 0. Our goal n − ≤ ≤ is to show that there exists m = m N such that a.a.s. γ( (n,m)) = k and b( (n,m)) = n ∈ G G Θ(∆( (n,m))) = Θ(m/n). We assume that Theorem 3 holds and we will use the probability space G G(n,p) to get the result. It follows immediately from definition (3) that, for 1 j < n, f(n,j,p) is both a continuous ≤ and increasing function of p, taking all values between 0 and n . Then, given n N (sufficiently j ∈ large), we can define p to be such that + (cid:0) (cid:1) f(n,k 1,p )= 1/(p n). (14) + + − Moreover, straightforward computations show that, for 0< p < 1 and 0 j n/4, ≤ ≤ n f(n,j,p) j +1 j = < 1/2, (15) f(n,j+1,p) ≤ n n j (cid:0)j+(cid:1)1 − (cid:0) (cid:1) so in particular f(n,j,p) is increasing in j, for j in that range. Let r be defined as r in (4) for + p = p . From (14) and (15), we deduce that f(n,k,p ) > 1/(p n) and f(n,j,p ) 1/(p n) for + + + + + ≤ all j k 1, so we must have r = k. Also observe that r in (4) is a non-increasing function of p. + Comb≤inin−g this fact and Lemma 6(i), we conclude that n 1/3+ε′ p 1 ε, for some constant − + ′ ≤ ≤ − ε = ε(ε), since otherwise r < εlogn or r > n1/3 ε contradicting our assumptions on k and ′ ′ + + − the fact that k = r . Hence, in particular, 1/(p n) = o(1). It follows immediately from the first + + moment method that a.a.s. G(n,p ) has no dominating set of size k 1, and then + − for all 0 p p , γ(G(n,p)) k a.a.s. (16) + ≤ ≤ ≥ since this is a non-increasing property with respect to the addition of edges. In fact, a.a.s. γ(G(n,p )) = k but we do not prove it now, since we will need a stronger statement to hold. + Now, let ω = ω be a function tending to infinity sufficiently slowly in order to meet all n requirements in the argument. Define 2 ω√p+n 2 ωn p := p = p 1 = p (1+o(1)), − +− n2 + − √p+ n2 ! + (cid:0) (cid:1) (cid:0) (cid:1) where the last step follows from the fact that p n 1/3+ε′. Since p p , then p n 1/3+ε′/2 + − + − ≥ − ∼ − ≥ and p is bounded away from 1. Clearly, − 1 1 f(n,k 1,p ) f(n,k 1,p ) = < . (17) + − − ≤ − p+n p n − Let r be defined as r in (4) for p = p . Next we want to show that r = k and then that − − − f(n,k,p ) exp(ωlogn). First, using Lemma 6(ii) and the fact that k = r = Θ(logn/p ), we + + − ≥ 8 get 1 (1 p )k−1 = 1 1 p++Θ ω√p+ k−1 − − − − − n (cid:18) (cid:19) (cid:16) (cid:17) k 1 = 1 (1 p )k 1 1+Θ ω√p+ − − − + − n (cid:16) (cid:16) (cid:17)(cid:17) = 1 (1 p )k 1 1+Θ ωlogn − − + − n√p+ (cid:16) (cid:16) (cid:17)(cid:17) = 1 (1 p )k 1 Θ ωlog3n − − + − − n2p3/2 (cid:18) + (cid:19) = 1 (1 p )k 1 1 Θ ωlog3n . − − + − − n2p3/2 (cid:18) (cid:18) + (cid:19)(cid:19) (cid:16) (cid:17) Hence, n k+1 f(n,k 1,p ) = f(n,k 1,p ) 1 Θ ωlog3n − − − − + (cid:18) − (cid:18)n2p3+/2 (cid:19)(cid:19) = f(n,k 1,p ) 1 Θ ωlog3n − + − np3/2 (cid:18) (cid:18) + (cid:19)(cid:19) f(n,k 1,p ) = (p n) 1 (p n) 1, + + − − ∼ − ∼ − as p n 1/3+ε′. Combining this with (15) and (17), we obtain that f(n,k,p ) > 1/(p n) and + − ≥ − − f(n,j,p ) 1/(p n) for all j < k, so k = r . Now, using Lemma 6 again (this time part (iii)), we − ≤ − − get f(n,k,p ) = f(n,k 1,p )exp(Θ(log2n)) (p n) 1exp(Θ(log2n)) exp(ωlogn), − − − − ∼ − ≥ as desired. The same argument holds clearly with n 1 playing the role of n. Therefore, it follows − from Theorem 3 that a.a.s. γ( (n,p )) = k and b(G(n,p )) = Θ(∆(G(n,p ))) cp n, for some G − − − ≥ − constant c = c(ε) > 0. Let Q be the graph property that we cannot destroy all dominating sets of size k by removing any set of at most cp n edges. Clearly, this is a non-decreasing property with − respect to adding edges in the graph, so for all p p 1, G(n,p) satisfies property Q a.a.s. (18) − ≤ ≤ Finally, define n p +p n n + mˆ = − = p+ ωn√p+ p+, 2 2 2 − ∼ 2 (cid:18) (cid:19) (cid:18) (cid:19) (cid:18) (cid:19) where at the last step we use the fact that p > n 1/3+ε. Easy manipulations yield + − mˆ +ωn√p+ mˆ +(√2+o(1))ω√mˆ mˆ +ω mˆ n2 −mˆ / n2 p = = , (19) + n n ≥ q (cid:0)(cid:0)n (cid:1) (cid:1) (cid:0) (cid:1) 2 2 2 and similarly (cid:0) (cid:1) (cid:0) (cid:1) (cid:0) (cid:1) p = mˆ −ωn√p+ mˆ −ω mˆ n2 −mˆ / n2 . (20) − n ≤ q (cid:0)(cid:0)n (cid:1) (cid:1) (cid:0) (cid:1) 2 2 In view of (16), (18), (19) and (20)(cid:0), (cid:1)we can apply Propo(cid:0)sit(cid:1)ion 1.13 in [6] separately to both the property Q and the property that γ( (n,p)) k, and we conclude that a.a.s. γ( (n,mˆ)) k G ≥ G ≥ and (n,mˆ) satisfies property Q. These two events together imply that γ( (n,mˆ)) = k and G G b( (n,mˆ)) = Θ(p n)= Θ(m/n). The proof is finished. G − 9 Now, we are going to show that Theorem 2 can be obtained from Theorem 3. Proof of Theorem 2. Let p = p be such that n 1/3+ε p 1 ε for some ε > 0, and let r = r n − n ≤ ≤ − be defined as in (4). Moreover, supposethere exists a non-increasing non-negative sequence h = h n such that p /p = 1 Θ(h /n). Our goal is to show that there exists a positive sequence n+1 n n − ω = ω and a dense set I N such that n ′ → ∞ ⊆ f(n,r,p) exp(ωlogn), for n I . ′ ≥ ∈ The result will follow immediately from Theorem 3, and will hold for I defined as in (7). (Note that, since I is dense, it is straightforward to verify that I must be dense too.) ′ Throughout the proof, we set ω = ω = loglogn. Note h = O(1) and so our assumptions on n 1 p and h imply that h = O(1) and so there exists a universal constant 0 < A < 1 such that, for n 1 every n n 3n, ′ ≤ ≤ p n′ A 1. (21) 1 ≤ p ≤ n Given any fixed j 0,1,2 , in view of our assumptions on p and h and by Lemma 6(ii), we have ∈{ } 1 (1 pn)rn+1−j = 1 1 pn+1 1+Θ(hn/n) rn+1−j − − − − = 1 ((cid:16)1 p )(cid:0)rn+1 j 1 Θ(cid:1)(cid:17)pn+1hn rn+1−j − − n+1 − − n (cid:16) (cid:16) (cid:17)(cid:17) = 1 (1 p )rn+1 j 1 Θ hnlogn − − n+1 − − n (cid:16) (cid:16) h lo(cid:17)g(cid:17)3n = 1 (1 p )rn+1 j 1+Θ n . − − n+1 − n2p (cid:18) (cid:18) n+1 (cid:19)(cid:19) (cid:0) (cid:1) Therefore, f(n+1,r j,p ) n+1 1 (1 pn+1)rn+1−j n−rn+1+j+1 n+1 n+1 − − − = f(n,rn+1−j,pn) n+1−rn+1+j (cid:16) 1 (1 pn)rn+1−j(cid:17)n−rn+1+j − − = 1+Θ lnogpn (cid:16)1−(1−pn+1)rn+1−(cid:17)j 1−Θ hnn2lpog3n n−rn+1+j (cid:18) (cid:18) n (cid:19)(cid:19) (cid:18) (cid:18) n+1 (cid:19)(cid:19) (cid:16) (cid:17) logn log2n h log3n n = 1+Θ 1 Θ 1 Θ np − np − np (cid:18) (cid:18) n (cid:19)(cid:19)(cid:18) (cid:18) n+1(cid:19)(cid:19)(cid:18) (cid:18) n+1 (cid:19)(cid:19) g n = 1 Θ , (22) − np (cid:18) n(cid:19) where g := log2n+h log3n. By our assumptions on h , we have log2n g = O(log3n). In n n n n ≤ particular, for every j 0,1,2 and every n, ∈ { } g f(n+1,r j,p ) g n n+1 n+1 n exp C − exp C , (23) 2 1 − np ≤ f(n,r j,p ) ≤ − np (cid:18) n(cid:19) n+1− n (cid:18) n(cid:19) for some universal constants C > C > 0. From (22) (with j = 0) and our assumptions on p, we 2 1 obtain (n+1)p f(n+1,r ,p ) g 1 n+1 n+1 n+1 n = 1 Θ 1+O < 1, np f(n,r ,p ) − np n n n+1 n (cid:18) (cid:18) n(cid:19)(cid:19)(cid:18) (cid:18) (cid:19)(cid:19) 10