Dieter Mitsche
email: dmitsche@unice.fr

Xavier Pérez-Giménez

Pra Lat
email: pralat@ryerson.ca

The bondage number of random graphs

A dominating set of a graph is a subset D of its vertices such that every vertex not in D is 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 size of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number of G. In this note, we study the bondage number of binomial random graph G (n, p). We obtain a lower bound that matches the order of the trivial upper bound. As a side product, we give a one-point concentration result for the domination number of G (n, p) under certain restrictions.

Introduction

In this paper, we consider the Erdős-Rényi random graph process, which is a stochastic process that starts with n vertices and no edges, and at each step adds one new edge chosen uniformly at random from the set of missing edges. Formally, let e 1 , e 2 , . . . , e ( n 2 ) be a random permutation of the edges of the complete graph K n . The graph process consists of the sequence of random graphs (G(n, m))

( n 2 ) m=0 , where G(n, m) = (V, E m ), V = [n] := {1, 2, . . . , n}, and E m = {e 1 , e 2 , . . . , e m }. It is clear that G(n, m) is a graph taken uniformly at random from the set of all graphs on n vertices and m edges (see, for example, [START_REF] Bollobás | Random Graphs[END_REF][START_REF] Janson | Random Graphs[END_REF] for more details.)

Our results refer to the random graph process. However, it will be sometimes easier to work with the G (n, p) model instead of G(n, m). The (binomial) random graph G (n, p) consists of the probability space (Ω, F, Pr), where Ω is the set of all graphs with vertex set [n], F is the family of all subsets of Ω, and for every G ∈ Ω,

Pr(G) = p |E(G)| (1 -p) ( n 2 )-|E(G)| .
This space may be viewed as the set of outcomes of n 2 independent coin flips, one for each pair {u, v} of vertices, where the probability of success (that is, adding edge uv) is p. Note that p = p n 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 n ∼ b n to denote a n = (1 + o(1))b n . A sequence a n satisfies a certain property eventually if the property 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 G(n, m) and G (n, p) when we mean a graph drawn from the distribution G(n, m) and G (n, p), respectively. All logarithms in this paper are natural logarithms.

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. [START_REF] Fink | The bondage number of a graph[END_REF] 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. [START_REF] Bauer | Domination alteration sets in graphs[END_REF] 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 [START_REF] Walikar | Domination critical graphs[END_REF] in 1979. One of the very first observations [START_REF] Bauer | Domination alteration sets in graphs[END_REF][START_REF] Fink | The bondage number of a graph[END_REF] is the following upper bound:

b(G) ≤ min xy∈E {deg(x) + deg(y) -1} ≤ ∆(G) + δ(G) -1,
where ∆(G) and δ(G) are the maximum and, respectively, the minimum degree of G. Since a.a.s. ∆(G (n, p)) ∼ δ(G (n, p)) ∼ pn provided pn log n (this follows immediately from Chernoff's bound stated below, and the union bound), we get that a.a.s. b(G (n, p)) ≤ 2pn(1 + o(1))

for pn log n. For denser graphs, one can improve the leading constant of this upper bound by using the following observation of Hartnell and Rall [START_REF] Hartnell | Bounds on the bondage number of a graph[END_REF]: Today, many properties of the bondage number are studied. For more details the reader is directed to the survey [START_REF] Xu | On bondage numbers of graphs-a survey with some comments[END_REF] which cites almost 150 papers on the topic.

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 n → 1 and also assume that p does not tend to zero too fast. More precisely, our main results require that p = p n eventually satisfies

n -1/3+ε ≤ p ≤ 1 -ε, (2)
for some constant ε > 0, but most arguments only require the following, milder, constraint:

log 2 n/ √ n p ≤ 1 -ε.
Since our results are asymptotic in n, we will assume that n is large enough so that all requirements in the argument are met. (In particular, the notation "eventually" is often implicitly assumed in the proofs and omitted.) Let D k be the set of dominating sets of size k of G (n, p), and let

X k = |D k |. Clearly, f (n, k, p) := EX k = n k 1 -(1 -p) k n-k . (3)
For a given p = p n , let

r = r n = min{k ∈ N : f (n, k, p) > 1/(pn)}. (4)
Since pn √ n log 2 n > 1 (eventually) and f (n, n, p) = 1, the function r is well defined for n sufficiently large.

Random Graph Process

Consider the random graph process (G(n, m)) 0≤m≤( n 2 ) . Clearly, the random variable

γ(G(n, m)) is a non-increasing function of m, γ(G(n, 0)) = γ(K n ) = n, and γ(G(n, n 2 )) = γ(K n ) = 1
. Suppose that at some point the domination number drops down, that is, there exists a value of m such that γ(G(n, m)) = k + 1 but γ(G(n, m + 1)) = k. The random graph process continues and, as long as the domination number remains to be equal to k, the bondage number, b(G(n, m + )), is a nondecreasing function of . Moreover, we get that b(G(n, m+ )) ≤ , as one can remove the last edges that were added in the process (namely, e m+1 , e m+2 , . . . , e m+ ) in order to increase the domination 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(G(n, m + )) when γ(G(n, m + )) = k but γ(G(n, m + + 1)) = k -1? It turns out that, for the range of p we are interested in, it is of the order of the maximum degree of G(n, m + ), and hence it matches the 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 n be such that eventually ε log n ≤ k ≤ n 1/3-ε . Then, there exists m = m n such that a.a.s.

γ(G(n, m)) = k and b(G(n, m)) = Θ(∆(G(n, m))) = Θ(m/n).

Binomial Random Graph

Consider now the binomial random graph G (n, p). Before we state the main result for this probability space, let us mention some technical difficulties one needs to deal with. It is easy to construct a sequence p n so that a.a.s. γ(G (n, p n )) = k n for some function k n , but the expected number of dominating sets of size k n , f (n, k n , p n ), tends to infinity not too fast. As a result, one can remove relatively few edges to increase the domination number. Similarly, it is also easy to construct a sequence p n that produces many dominating sets of the same size k n (in expectation) and, as a result, we expect the bondage number to be large. One might think that introducing some assumptions (for example, that function p n is non-increasing) should solve the problem but, unfortunately, it is not the case. In fact, even for "natural" functions, such as p n = n -1/4 , it is not true that there are always many dominating sets of minimum cardinality, and so we cannot expect the bondage number to have a nice behaviour. Hence, b(G (n, p n )) usually oscillates reaching both small and large values as n grows. However, assuming that p n is "smooth" enough, we will show that for the range of p n we are interested in, almost all values of n yield the bondage number as large as possible. To make this precise, a set I ⊆ N is said to be dense if

lim n→∞ |I ∩ [n]| n = 1. (5)
In view of this definition, our result for the binomial random graph can be stated as follows.

Theorem 2. Given any constant ε > 0, let p = p n be such that eventually n -1/3+ε ≤ p ≤ 1 -ε. Moreover, suppose there exists a non-increasing non-negative sequence h = h n such that p n+1 /p n = 1 -Θ(h n /n). Then, there exists a dense set I ⊆ N such that, with asymptotics restricted to n ∈ I, a.a.s.

γ(G (n, p)) = r and b(G (n, p)) = Θ(∆(G(n, p))) = Θ(pn).
Although the conditions on p n in Theorem 2 seem restrictive, many common and natural probability functions p n satisfy it. For example, p n = n -1/4 , p n = 1/ log log n and p n = 1/2 meet the requirements (by picking h n = 1, h n = 1/ log n and h n = 0, respectively). Other, seemingly more complicated, choices such as p n = (n + 1) -1/4 log 3 n + n -1/3 also satisfy our conditions. On the other hand, mixed behaviours such as

p n = n -1/4
n even 1/ log log n n odd are not considered here. One can easily relax the conditions on p n a bit further, but we do not aim for it, as it does not appear to be possible to express that in terms of any "natural" assumptions such as "p n being non-decreasing".

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 n log 2 n/ √ n, but bounded away 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 n is defined in (4) (see [START_REF] Glebov | On the Concentration of the Domination Number of the Random Graph[END_REF] and also [START_REF] Wieland | On the domination number of a random graph[END_REF] for an earlier paper where denser 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 . Theorem 3. Given any constant ε > 0, suppose that p = p n eventually satisfies n -1/3+ε ≤ p ≤ 1-ε, and let f and r be defined as in (3) and (4). Suppose that there exists an infinite set I ⊆ N and

ω = ω n → ∞ such that EX r = f (n, r, p) ≥ exp (ω log n) (for n ∈ I ). (6)
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).

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 n satisfying log 2 n/ √ n p ≤ 1 -ε (see Corollary 9 below).

The paper is structured as follows. In Section 3, we show that the results for G(n, m) and G (n, p) can be obtained from Theorem 3. Section 4 develops some tools required to estimate the second moment of X r and some other random variables. Finally, Section 5 is devoted to prove Theorem 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 n and f (n, r, p) defined in (3) and (4). The function p will be assumed to satisfy [START_REF] Bollobás | Random Graphs[END_REF]. We will also show that Theorem 1 and Theorem 2 are implied by Theorem 3.

We will use the following version of Chernoff bound (see e.g. [START_REF] Janson | Random Graphs[END_REF]):

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), Pr[W < (1 -δ)µ] ≤ exp (-µϕ(-δ)) ≤ exp - δ 2 µ 2 ; ( 8
)
and if δ > 0,

Pr[W > (1 + δ)µ] ≤ exp - δ 2 µ 2 + δ . (9)
Given p = p n ∈ [0, 1), define p = log 1 1-p . Note that p ≥ p (with equality only holding at p = 0), and

     p ∼ p if p = o(1), p = Θ(1) if p = Θ(1) and 1 -p = Θ(1), p → ∞ if p → 1. ( 10
)
We start with a few simple observations. Let us mention that some of the properties we show 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 log 2 n/ √ n p ≤ 1 -ε for some constant ε > 0, and let r be defined as in (4). Then, the following holds:

(i) r = 1 p log pn log 2 (pn) (1 + o(1)) . (ii) Therefore, r = Θ log n p and (1 -p) r = Θ log 2 n pn .
In particular, r = Ω(log n) and r = o( √ n/ log n).

(iii) Moreover, if k = r + O(1), then f (n, k + 1, p) f (n, k, p) = exp(Θ(log 2 n)).
Proof. For a given function g = g n = o(1), we define

s g = s g (n, p) = 1 p log pn log 2 (pn)(1 + g n ) .
First, observe that for p in the range of discussion, log(pn) = Θ(log n). Then, it follows from (10) that

s g = 1 Θ(p) Θ(log(pn)) -O(log log(pn)) = Θ log n p .
Hence, part (ii) applied to s g holds, since p log 2 n/ √ n. (Note that the observation for (1 -p) r in (ii), applied to s g , is obvious.) Now we will show that r = s g for some function g n = o(1), and part (i) will follow immediately.

Using Stirling's formula (k! ∼ √ 2πk(k/e) k ), note that f (n, s g , p) = [n] sg s g ! 1 - log 2 (pn) pn (1 + g n ) n(1-sg/n) = n sg (1 + O(s g /n)) sg (1 + o(1)) 2πs g (s g /e) sg exp - log 2 (pn) p 1 + g n + O log 2 n pn + O s g n = 1 + o(1) 2πs g exp s g log ne s g - log 2 (pn) p 1 + g n + O log 2 n pn , since s g = Θ(log n/p) and p log 2 n/ √ n, which implies that (1 + O(s g /n)) sg = e O(s 2 g /n) = e O(log 2 n/(p 2 n)) ∼ 1 and s g /n = O(log n/(pn)) = o(log 2 n/(pn)). Hence, f (n, s g , p) ∼ 1 2πs g exp log(pn) + O(log log n) p log pn log n + O(1) - log 2 (pn) p 1 + g n + O log 2 n pn = Θ p log n exp - log 2 (pn) p g n + O log log n log n .
By taking, say, g n = log 2 log n/ log n, we get

f (n, s g , p) ≤ exp -Ω((log 2 log n) log(pn)) = o(1/(pn)).
On the other hand, if, say, g n = -log 2 log n/ log n, we get

f (n, s g , p) n -1/4 log n • exp Ω((log 2 log n) log(pn)) > 1/(pn).
Now, 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) f (n, k, p) ∼ [n] k+1 /(k + 1)! [n] k /k! 1 -(1 -p) k+1 1 -(1 -p) k n-k (1 -(1 -p) k+1 ) ∼ n k 1 -(1 -p) k + p(1 -p) k 1 -(1 -p) k n-k = Θ pn log n 1 + Θ(p(1 -p) k ) n-k = Θ pn log n exp Θ(pn(1 -p) k ) = Θ pn log n exp Θ(log 2 n) = exp Θ(log 2 n) .
This finishes the proof of the lemma. Now, we will show that Theorem 1 can be obtained from Theorem 3.

Proof of Theorem 1. Let k = k n be such that ε log n ≤ k ≤ n 1/3-ε for some ε > 0. Our goal is to show that there exists m = m n ∈ N such that a.a.s. γ(G(n, m)) = k and b(G(n, m)) = Θ(∆(G(n, m))) = Θ(m/n).
We assume that Theorem 3 holds and we will use the probability space 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 j . Then, given n ∈ N (sufficiently large), we can define p + to be such that

f (n, k -1, p + ) = 1/(p + n). (11)
Moreover, straightforward computations show that, for 0 < p < 1 and 0

≤ j ≤ n/4, f (n, j, p) f (n, j + 1, p) ≤ n j n j+1 = j + 1 n -j < 1/2, ( 12
)
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 (11) and ( 12), 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. Combining this fact and Lemma 6, we conclude that n -1/3+ε ≤ p + ≤ 1 -ε , for some constant ε = ε (ε), since otherwise r + < ε log n or r + > n 1/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. ( 13
)
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 ω = ω n be a function tending to infinity sufficiently slowly in order to meet all requirements in the argument. Define

p -:= p + - 2 ω √ p + n n 2 = p + 1 - 2 ωn √ p + n 2 = p + (1 + o(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,

f (n, k -1, p -) ≤ f (n, k -1, p + ) = 1 p + n < 1 p -n . ( 14
)
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(ω log n). First, using Lemma 6(ii) and the fact that k = r + = Θ(log n/p + ), we get

1 -(1 -p -) k-1 = 1 -1 -p + + Θ ω √ p + n k-1 = 1 -(1 -p + ) k-1 1 + Θ ω √ p + n k-1 = 1 -(1 -p + ) k-1 1 + Θ ω log n n √ p + = 1 -(1 -p + ) k-1 -Θ ω log 3 n n 2 p 3/2 + = 1 -(1 -p + ) k-1 1 -Θ ω log 3 n n 2 p 3/2 + . Hence, f (n, k -1, p -) = f (n, k -1, p + ) 1 -Θ ω log 3 n n 2 p 3/2 + n-k+1 = f (n, k -1, p + ) 1 -Θ ω log 3 n np 3/2 + ∼ f (n, k -1, p + ) = (p + n) -1 ∼ (p -n) -1 ,
as p + ≥ n -1/3+ε . Combining this with (12) and ( 14), 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(Θ(log 2 n)) ∼ (p -n) -1 exp(Θ(log 2 n)) ≥ exp(ω log n),
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.

γ(G(n, p -)) = k and b(G (n, p -)) = Θ(∆(G (n, p -))) ≥ cp -n, for some 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. ( 15
)
Finally, define

m = n 2 p -+ p + 2 = n 2 p + -ωn √ p + ∼ n 2 p + ,
where at the last step we use the fact that p + > n -1/3+ε . Easy manipulations yield

p + = m + ωn √ p + n 2 = m + ( √ 2 + o(1))ω √ m n 2 ≥ m + ω m n 2 -m / n 2 n 2 , (16)
and similarly

p -= m -ωn √ p + n 2 ≤ m -ω m n 2 -m / n 2 n 2 . ( 17
)
In view of ( 13), ( 15), ( 16) and ( 17), we can apply Proposition 1.13 in [START_REF] Janson | Random Graphs[END_REF] separately to both the property Q and the property that γ(G(n, p)) ≥ k, and we conclude that a.a.s. γ(G(n, m)) ≥ k and G(n, m) satisfies property Q. These two events together imply that

γ(G(n, m)) = k and b(G(n, m)) = Θ(p -n) = Θ(m/n).
The proof is finished. Now, we are going to show that Theorem 2 can be obtained from Theorem 3.

Proof of Theorem 2. Let p = p n be such that n -1/3+ε ≤ p ≤ 1 -ε for some ε > 0, and let r be defined as in [START_REF] Glebov | On the Concentration of the Domination Number of the Random Graph[END_REF]. Moreover, suppose there exists a non-increasing non-negative sequence h = h n such that p n+1 /p n = 1 -Θ(h n /n). Our goal is to show that there exists a positive sequence ω = ω n → ∞ and a dense set

I ⊆ N such that f (n, r, p) ≥ exp(ω log n), for n ∈ I .
The result will follow immediately from Theorem 3, and will hold for I defined as in [START_REF] Walikar | Domination critical graphs[END_REF]. (Note that, since I is dense, it is straightforward to verify that I must be dense too.) Throughout the proof, we set ω = ω n = log log n. Note h 1 = O(1) and so our assumptions on p and h imply that h n = O(1) and so there exist two universal constants A 2 > A 1 > 0 such that, for every n ≤ n ≤ 3n,

A 1 ≤ p n p n ≤ A 2 . ( 18
)
Given any fixed j ∈ {0, 1, 2}, in view of our assumptions on p and h and by Lemma 6, we have

1 -(1 -p n ) r n+1 -j = 1 -1 -p n+1 1 + Θ(h n /n) r n+1 -j = 1 -(1 -p n+1 ) r n+1 -j 1 -Θ p n+1 hn n r n+1 -j = 1 -(1 -p n+1 ) r n+1 -j 1 -Θ hn log n n = 1 -(1 -p n+1 ) r n+1 -j 1 + Θ h n log 3 n n 2 p n+1 .
Therefore,

f (n + 1, r n+1 -j, p n+1 ) f (n, r n+1 -j, p n ) = n + 1 n + 1 -r n+1 -j 1 -(1 -p n+1 ) r n+1 -j n-r n+1 -j+1 1 -(1 -p n ) r n+1 -j n-r n+1 -j = 1 + Θ log n np n 1 -(1 -p n+1 ) r n+1 -j 1 -Θ h n log 3 n n 2 p n+1 n-r n+1 -j = 1 + Θ log n np n 1 -Θ log 2 n np n+1 1 -Θ h n log 3 n np n+1 = 1 -Θ g n np n , ( 19
)
where g n := log 2 n + h n log 3 n. By our assumptions on h n , we have log 2 n ≤ g n = O(log 3 n). In particular, for every j ∈ {0, 1, 2} and every n,

exp -C 2 g n np n ≤ f (n + 1, r n+1 -j, p n+1 ) f (n, r n+1 -j, p n ) ≤ exp -C 1 g n np n , (20)
for some universal constants C 2 > C 1 > 0. From (19) (with j = 0) and our assumptions on p, we obtain (n + 1)

p n+1 f (n + 1, r n+1 , p n+1 ) np n f (n, r n+1 , p n ) = 1 -Θ g n np n 1 + O 1 n < 1,
where the last inequality holds eventually for n sufficiently large. This implies that

f (n, r n+1 , p n ) > (n + 1)p n+1 f (n + 1, r n+1 , p n+1 ) np n > 1 np n ,
where the last inequality uses the definition of r n+1 in (4). Hence, r n+1 ≥ r n for n large enough, and thus r is a nondecreasing sequence of n except, possibly, for a finite number of terms. Similarly, from (19) (with j = 2) and by Lemma 6(iii),

f (n, r n+1 -2, p n ) = 1 + Θ gn npn f (n + 1, r n+1 -2, p n+1 ) ∼ f (n + 1, r n+1 -2, p n+1 ) = f (n + 1, r n+1 -1, p n+1 ) exp -Θ(log 2 n) ≤ 1 (n + 1)p n+1 exp -Θ(log 2 n) < 1 np n ,
for n sufficiently large. Therefore, r n+1 -2 < r n , or equivalently r n+1 ≤ r n + 1, for all but finitely many n (that is, r can increase by at most one). We construct now the set I as follows:

I := {n ∈ N : f (n, r n , p n ) ≥ exp(ω n log n)}.
Since we want to show that I contains almost all n ∈ N, suppose that n 1 / ∈ I for some value n 1 ∈ N. Then we have

1/(n 1 p n 1 ) < f (n 1 , r n 1 , p n 1 ) < exp(ω n 1 log n 1 )
Our goal is to show that n 1 is followed by an interval of naturals [n 1 , n 2 -1] / ∈ I and then by a much longer interval [n 2 , n 3 ] ∈ I . We may assume that n 1 is sufficiently large, since the limiting density of I is not affected by ignoring any finite number of naturals.

Let

n 2 = min{n > n 1 : r n > r n 1 or n = 3n 1 }.
Since r n = r n 1 for all n 1 ≤ n ≤ n 2 -1, applying (20) to that range (with j = 0) we get

f (n 2 -1, r n 2 -1 , p n 2 -1 ) ≤ f (n 1 , r n 1 , p n 1 ) exp -C 1 n 2 -2 n=n 1 g n np n < exp ω n 1 log n 1 - C 1 3A 2 n 1 p n 1 n 2 -2 n=n 1 g n < exp ω n 1 log n 1 + 1 - C 1 3A 2 n 1 p n 1 n 2 -1 n=n 1 g n .
On the other hand, by the definition of r (see ( 4)), we know that

f (n 2 -1, r n 2 -1 , p n 2 -1 ) > 1 p n 2 -1 (n 2 -1) ≥ 1 3A 2 p n 1 n 1 . (21)
Hence, it must be the case that, say,

n 2 -1 n=n 1 g n ≤ n 1 p n 1 ω 2 n 1 log n 1 . (22)
Since g n ≥ log 2 n and by our choice of ω n , it follows that

n 2 -n 1 ≤ n 1 ω 2 n 1 / log n 1 < n 1 . (23)
As a result, n 2 = 3n 1 , and so it follows that r n 2 > r n 1 . In fact, since r can increase by at most one, r n 2 = r n 2 -1 + 1. Now, we get from (20), Lemma 6(iii) and (21) that, for some small constant C 3 > 0 (possibly depending on ε),

f (n 2 , r n 2 , p n 2 ) ≥ C 3 f (n 2 -1, r n 2 , p n 2 -1 ) = C 3 f (n 2 -1, r n 2 -1 + 1, p n 2 -1 ) ≥ C 3 f (n 2 -1, r n 2 -1 , p n 2 -1 ) exp C 3 log 2 n 2 ≥ C 3 /(3A 2 ) p n 1 n 1 exp C 3 log 2 n 2 ≥ exp (C 3 /2) log 2 n 2 ≥ exp (ω n 2 log n 2 ) . ( 24
)
As a result, n 2 belongs to I .

Let

n 3 = min{n > n 2 : f (n, r n 2 , p n ) < exp(2ω n 2 log n 2 ) or n = 3n 2 }. Note that if f (n, r n 2 , p n ) ≥ exp(2ω n 2 log n 2 ) for some n 2 < n ≤ 3n 2 , then f (n, r n 2 , p n ) ≥ exp(ω n log n) > 1/(p n n).
Hence, r n = r n 2 and, more importantly, n ∈ I . If n 3 = 3n 2 , then we are done, since the interval [n 2 , n 3 ] is longer than [n 1 , n 2 -1] by at least a log n 1 /ω 2 n 1 factor (see second step in (23)). Hence, we may assume that f (n 3 , r n 2 , p n 3 ) < exp(2ω n 2 log n 2 ). Applying (20) one more time and by the second last step of (24), we get

f (n 3 , r n 2 , p n 3 ) ≥ f (n 2 , r n 2 , p n 2 ) exp -C 2 n 3 -1 n=n 2 g n np n ≥ exp (C 3 /2) log 2 n 2 - C 2 A 1 n 2 p n 2 n 3 -1 n=n 2 g n ≥ exp (C 3 /2) log 2 n 2 - C 2 A 2 1 n 1 p n 1 n 3 -1 n=n 2 g n , which is at least exp(2ω n 2 log n 2 ), if, say, n 3 -1 n=n 2 g n ≤ n 1 p n 1 log 2 n 1 /ω n 1 . Consequently, n 3 -1 n=n 2 g n > n 1 p n 1 log 2 n 1 ω n 1 . (25)
Finally, note that h n is non-increasing and n 3 -n 1 ≤ 8n 1 , so g n ∼ g n 1 for any n 1 ≤ n ≤ n 3 and, as a result, max{g n :

n 2 ≤ n ≤ n 3 -1} < C • min{g n : n 1 ≤ n ≤ n 2 -1}
for some universal constant C. Combining this observation together with ( 22) and ( 25), it immediately follows that

n 2 -n 1 n 3 -n 2 + 1 ≤ ω 3 n 1 log n 1 .
Putting everything together, given any n 1 / ∈ I sufficiently large, we obtained n 2 and n 3 such that

[n 2 , n 3 ] ⊆ I and n 3 -n 2 + 1 ≥ log n 1 ω 3 n 1 (n 2 -n 1 ).
This proves that I is dense as required, and the proof of the theorem is finished.

Note that the lengths of the intervals [n 1 , n 2 -1] and [n 2 , n 3 ] in the proof of Theorem 2 depend on the value of p n . This is not an artifact of the proof, but rather reflecting the fact that for different values of p n these lengths are indeed different: for p n = n -1/4 , we get that r 2n -r n = Θ(n 1/4 log n), and thus, on average, after Θ( np log n ) integers the value of r increases by 1. On the other hand, for p n = 1 log log n , we get that r 2n -r n = Θ(log log n), and thus, on average, after Θ(np) integers the value of r increases by 1.

Second moment ingredients

For a given function p = p n , let f (n, k, p) and r = r n be defined as in (3) and (4), respectively. Throughout this section, we suppose that, given our choice of p, there exists some infinite set I ⊆ N satisfying (6) for a given function ω = ω n → ∞, and restrict all our asymptotic statements to n ∈ I . For simplicity, we also write X instead of X r and D instead of D r . For each i ∈ {0, 1, . . . , r}, let W i be the random variable counting the number of ordered pairs D, D ∈ D in G (n, p) with |D∩D | = i. One of the key ingredients in our analysis is to estimate the variance of X and other related random variables defined later in the paper. To do so, we will use several bounds on EW i that are stated in Proposition 8 below. In fact, the variance of X r+1 was already studied in [START_REF] Glebov | On the Concentration of the Domination Number of the Random Graph[END_REF] and [START_REF] Wieland | On the domination number of a random graph[END_REF], and we follow some of the ideas in their computations, but we need a more accurate estimation of the error terms involved. Also, the aforementioned papers deal with X r+1 instead of X r , since they make use of the fact that EX r+1 = exp(Θ(log 2 n)). In our case, this fact is replaced by our assumption [START_REF] Janson | Random Graphs[END_REF].

The following lemma uses some of the computations in [START_REF] Glebov | On the Concentration of the Domination Number of the Random Graph[END_REF], and will prepare us for Proposition 8. Given two sets of vertices D, D of size r, let P i denote the probability that D, D dominate each other in G (n, p) (i.e., every vertex in D has a neighbour in D and vice versa).

Lemma 7. Given a constant > 0, suppose that log 2 n/ √ n p ≤ 1 -ε and condition (6) holds for some infinite set I ⊆ N and some function ω = ω n → ∞, where f (n, k, p) and r are defined as in (3) and (4). Then, for each 0.9r ≤ i ≤ r,

rEW i /P i EW 1 /P 1 ≤ exp (-(ω/2) log n) (for n ∈ I ).
Sketch of proof. We follow some of the computations in Section 3.1 of [START_REF] Glebov | On the Concentration of the Domination Number of the Random Graph[END_REF]. In that paper, their choice of r corresponds to our r + 1, and their calculations assume p = o( 1), but everything we use here remains valid in our setting. By adapting (10) in [START_REF] Glebov | On the Concentration of the Domination Number of the Random Graph[END_REF] to our notation and using our assumption (6), we get

rEW i /P i EW 1 /P 1 ≤ (1 + o(1)) EX n r r i n -r r -i 1 + (1 -p) r 1 -(1 -p) r-i 1 -2(1 -p) r + (1 -p) 2r-i -(n-r) ≤ exp -ω log n + log n + 2(r -i) log n -n(1 -p) r 1 -(1 -p) r-i (1 + o(1)) .
(The term -ω log n in the exponent above corresponds to -(1 + o(1)) log 2 (pn) in [START_REF] Glebov | On the Concentration of the Domination Number of the Random Graph[END_REF], because of their different choice of r.) Moreover, equation (11) in [START_REF] Glebov | On the Concentration of the Domination Number of the Random Graph[END_REF] gives that

2(r -i) log n - n 2 (1 -p) r 1 -(1 -p) r-i ≤ 0,
and therefore

rEW i /P i EW 1 /P 1 ≤ exp (-ω log n + log n) ≤ exp (-(ω/2) log n) .
Before we proceed, we need one more definition. Given a constant ε > 0 and for i ∈ {1, 2, . . . , r}, let

Q i = min{i-1,L-1} j=0 Pr(Bin(i -1, p) = j)(Pr(Bin(r -i, p) < L -j)) 2 , ( 26
)
where L = pr with = ε 2 . The following proposition will be central for estimating the variance of several random variables.

Proposition 8. Given a constant ε > 0, assume that log 2 n/ √ n p ≤ 1 -ε and condition (6) is satisfied for some infinite set I ⊆ N. Then, the following holds for G (n, p) with n restricted to I :

(i) EW 0 (EX) 2 ≤ 1 + Θ log 3 n p 2 n and EW 1 (EX) 2 ≤ r 2 n 1 + Θ log 4 n pn + log 3 n p 2 n ; (ii) r i=1 EW i ≤ r i=1 iEW i ≤ r 2 n 1 + Θ log 4 n pn + log 3 n p 2 n (EX) 2 ; (iii) r i=1 iQ i EW i ≤ Q 1 r 2 n 1 + Θ log 4 n pn + log 3 n p 2 n (EX) 2 .
Proof. First, note that

EW i = n! i!(r -i)! 2 (n -2r + i)! 1 -(1 -p) i + (1 -p) i (1 -(1 -p) r-i ) 2 n-2r+i P i , (27)
where P i is, as above, the probability that D, D with intersection of size i dominate each other.

In particular,

EW 0 = n! r! 2 (n -2r)! (1 -(1 -p) r ) 2(n-2r) P 0 , (28)
and

EW 1 = n! (r -1)! 2 (n -2r + 1)! p + (1 -p)(1 -(1 -p) r-1 ) 2 n-2r+1 P 1 . (29)
Also, recall that

(EX) 2 = f (n, r, p) 2 = n! r!(n -r)! (1 -(1 -p) r ) n-r 2 . (30)
Using ( 28), (30) and Lemma 6, we can easily bound the ratio

EW 0 (EX) 2 = [n -r] r [n] r 1 -(1 -p) r -2r P 0 ≤ 1 -(1 -p) r -2r = 1 + Θ(r(1 -p) r ) = 1 + Θ log 3 n p 2 n .
Moreover, from (29), (30), Lemma 6 and the fact that p log 2 n/ √ n,

EW 1 (EX) 2 = r 2 [n -r] r-1 [n] r p + (1 -p)(1 -(1 -p) r-1 ) 2 n-2r+1 (1 -(1 -p) r ) n-r 2 P 1 = r 2 [n -r] r-1 [n] r 1 -2(1 -p) r + (1 -p) 2r-1 n-2r+1 (1 -(1 -p) r ) n-r 2 P 1 = r 2 [n -r] r-1 [n] r 1 + (1 -p) 2r-1 -(1 -p) 2r ) (1 -(1 -p) r ) 2 n-r 1 -2(1 -p) r + (1 -p) 2r-1 -r+1 P 1 = r 2 [n -r] r-1 n[n -1] r-1 1 + p(1 -p) 2r-1 (1 -(1 -p) r ) 2 n-r 1 -2(1 -p) r + (1 -p) 2r-1 -r+1 P 1 = r 2 n 1 -Θ r 2 n 1 + Θ pn(1 -p) 2r (1 + Θ (r(1 -p) r )) P 1 = r 2 n 1 -Θ log 2 n p 2 n 1 + Θ log 4 n pn 1 + Θ log 3 n p 2 n P 1 ≤ r 2 n 1 + Θ log 4 n pn + log 3 n p 2 n .
This proves part (i). Note that, in fact, we get something slightly stronger, namely

EW 1 /P 1 (EX) 2 ≤ r 2 n 1 + Θ log 4 n pn + log 3 n p 2 n . (31)
For i not too close to r, say 1 ≤ i ≤ r -3 log log n/p, we have

EW i+1 /P i+1 EW i /P i = (r -i) 2 (i + 1)(n -2r + i + 1) 1 -(1 -p) i+1 + (1 -p) i+1 (1 -(1 -p) r-i-1 ) 2 n-2r+i+1 (1 -(1 -p) i + (1 -p) i (1 -(1 -p) r-i ) 2 ) n-2r+i = (r -i) 2 (i + 1)(n -2r + i + 1) 1 -2(1 -p) r + (1 -p) 2r-i-1 1 -2(1 -p) r + (1 -p) 2r-i n-2r+i 1 -2(1 -p) r + (1 -p) 2r-i-1 = (r -i) 2 (i + 1)(n -2r + i + 1) 1 + p(1 -p) 2r-i-1 1 -2(1 -p) r + (1 -p) 2r-i n-2r+i 1 -2(1 -p) r + (1 -p) 2r-i-1 ≤ r 2 n -2r 1 + O pn(1 -p) r+3 log log n/p (1 -Θ ((1 -p) r )) ≤ r 2 n -2r 1 + O e -3 log log n log 2 n 1 -Θ log 2 n pn = r 2 n (1 + o(1)) = O(log 2 n/(p 2 n)). (32)
On the other hand, consider now r -3 log log n/p ≤ i ≤ r. Since this range is eventually included in the range 0.9r ≤ i ≤ r then, by Lemma 7,

rEW i /P i EW 1 /P 1 ≤ exp (-(ω/2) log n) . (33)
Now, note that for i ≥ 1 we have

(i + 1)EW i+1 /P i+1 iEW i /P i ≤ 2 EW i+1 /P i+1 EW i /P i .
Combining this with (31), (32) and (33),

r i=1 iEW i ≤ r i=1 iEW i /P i = EW 1 P 1 1 + O log 2 n p 2 n + EW 1 P 1 O (log log n/p) exp (-(ω/2) log n) = EW 1 P 1 1 + O log 2 n p 2 n ≤ (EX) 2 r 2 n 1 + Θ log 4 n pn + log 3 n p 2 n 1 + O log 2 n p 2 n = (EX) 2 r 2 n 1 + Θ log 4 n pn + log 3 n p 2 n ,
and part (ii) follows.

For part (iii), observe first that there exists some C = C(ε) > 0 such that if i ≥ C log n, then i > 2L. Hence, for C log n ≤ i ≤ r -3 log log n/p, substituting B a,b for Pr(Bin(a, p) = b), we get

(i + 1)Q i+1 iQ i = (i + 1) L-1 j=0 Pr(Bin(i, p) = j)(Pr(Bin(r -i -1, p) < L -j)) 2 i L-1 j=0 Pr(Bin(i -1, p) = j)(Pr(Bin(r -i, p) < L -j)) 2 = (i + 1) L-1 j=0 L-j-1 k=0 L-j-1 k =0 i i-j r-i-k r-i r-i-k r-i 1 1-p B i-1,j B r-i,k B r-i,k i L-1 j=0 L-j-1 k=0 L-j-1 k =0 B i-1,j B r-i,k B r-i,k ≤ i + 1 i i i -L + 1 1 1 -p = O(1).
Similarly, for L ≤ i < C log n we have

(i + 1)Q i+1 iQ i = O(log n).
On the other hand, for 1

≤ i ≤ L -1, (i + 1)Q i+1 iQ i = (i + 1) i-1 j=0 L-j-1 k=0 L-j-1 k =0 i i-j r-i-k r-i r-i-k r-i 1 1-p B i-1,j B r-i,k B r-i,k i i-1 j=0 L-j-1 k=0 L-j-1 k =0 B i-1,j B r-i,k B r-i,k + (i + 1)p i L-i-1 k=0 L-i-1 k =0 B r-i-1,k B r-i-1,k i i-1 j=0 L-j-1 k=0 L-j-1 k =0 B i-1,j B r-i,k B r-i,k = O(log n) + (i + 1)p i ( 1 1-p ) 2 L-i-1 k=0 L-i-1 k =0 B r-i,k B r-i,k ip i-1 L-i k=0 L-i k =0 B r-i,k B r-i,k = O(log n).
Finally, for r -3 log log n/p ≤ i ≤ r, by Lemma 7, since Q i ≤ 1, and by Chernoff's bound (see ( 8)),

rQ i EW i /P i Q 1 EW 1 /P 1 ≤ Q i Q 1 exp (-(ω/2) log n) ≤ 1 (Pr(Bin(r -1, p) < L)) 2 exp (-(ω/2) log n) ≤ exp ((1 -) 2 pr/2) -(ω/2) log n ≤ exp (O(log n) -(ω/2) log n) ≤ exp (-(ω/3) log n) ,
where the last inequality follows from p log 2 n/ √ n. Combining all bounds,

r i=1 iQ i EW i ≤ r i=1 iQ i EW i /P i = EW 1 Q 1 P 1 1 + O log 3 n p 2 n = Q 1 (EX) 2 r 2 n 1 + O log 3 n p 2 n + O log 4 n pn ,
and (iii) follows. The proof of the proposition is finished.

As an immediate consequence of this proposition, we can bound the variance of X = X r (which is also done for X r+1 in [START_REF] Glebov | On the Concentration of the Domination Number of the Random Graph[END_REF] and [START_REF] Wieland | On the domination number of a random graph[END_REF]), and obtain the following result.

Corollary 9. Given a constant ε > 0, assume that log 2 n/ √ n p ≤ 1 -ε and condition (6) is satisfied for some infinite set I ⊆ N. Then a.a.s. X ∼ f (n, r, p) (for n ∈ I ). Consequently, a.a.s. γ(G (n, p)) = r (for n ∈ I ). ordered pair of vertices (so uv = vu but -→ uv = -→ vu). Given a pair uv, let D uv be the set of dominating sets of size r of the graph G + uv = (V, E ∪ {uv}). Given a directed pair -→ uv and j ∈ [r], let

D j, -→ uv = D ∈ D uv : v ∈ D, u / ∈ D, | N (u) ∩ D| = j ,
where N (u) denotes the number of vertices adjacent to u in G + uv. Define the damage of -→ uv to be

Z-→ uv = r j=1 | D j, -→ uv | j ,
and the damage of the corresponding pair uv to be Z uv = Z-→ uv + Z-→ vu . Finally, the damage of a set of pairs A is Z A = e∈A Z e . We will see that this notion constitutes a convenient upper bound on the number of dominating sets of size r destroyed by removing a set of pairs A from the edge set. Let Y A be the number of dominating sets in D that are not dominating anymore after deleting a set of pairs A from E, that is, the number of dominating sets of size r of G but not of G -A = (V, E \ A). (Note that the definitions of Z A and Y A do not require A ⊆ E, but in the next observation we do.) Observation 11. Assuming γ(G) = r, clearly, one strategy to prove a lower bound b(G) > a is to show that Y A < X for all sets of edges A ⊆ E of size a, so the removal of any a edges of G cannot destroy all dominating sets of minimal size. Unfortunately, Y A is not easy to compute, since in general Y A = e∈A Y e . Hence, our notion of damage turns useful in view of the following deterministic result. In order to bound Y A , by the previous lemma, it suffices to estimate Z uv = Z-→ uv + Z-→ vu and sum over all pairs uv in A. It is convenient for our analysis to split the damage Z-→ uv of a directed pair -→ uv into its light damage

Z -→ uv = r j=L+1 | D j, -→ uv | j ,
and its heavy damage

Z -→ uv = Z-→ uv -Z -→ uv = L j=1 | D j, -→ uv | j .
(Recall that L = pr with = ε 2 .) Similarly as before, the light damage of a pair uv is Z uv = Z -→ uv + Z -→ vu , and its heavy damage is Z uv = Z -→ uv + Z -→ vu . For a given set of pairs A, its light damage is Z A = e∈A Z e and its heavy damage is Z A = e∈A Z e .

We will now estimate the first and second moments of some of the random variables described above. Given any -→ uv, we can easily estimate EZ-→ uv by summing the probability that a given

In order to bound the variance of Z -→ uv , we will need to use that (6) holds for two consecutive values n -1 and n. Therefore, we assume that there exist infinitely many such pairs of values, and restrict asymptotics to all n such that both n -1 and n satisfy [START_REF] Janson | Random Graphs[END_REF].

Lemma 14. Given a constant ε > 0, assume that log 2 n/ √ n p ≤ 1 -ε. Moreover, suppose there exist infinite sets I ⊆ I ⊆ N satisfying (6) and [START_REF] Walikar | Domination critical graphs[END_REF], and restrict asymptotics to n ∈ I . Then,

VarZ -→ uv = O log 4 n pn + log 3 n p 2 n (EZ -→ uv ) 2 .
Proof. First, observe that G (n, p) -u is distributed as G (n -1, p), and this is independent of the edges emanating from u. By definition, each dominating set D counted by Z -→ uv is a dominating set of G (n, p) -u of size r such that v ∈ D and 0 ≤ |N (u) ∩ D \ {v}| ≤ L -1. Therefore, we get

EZ -→ uv = Pr(Bin(r -1, p) < L) E G (n-1,p) Z v . Furthermore, given u ∈ V , by counting in two different ways the number of pairs D, D of dominat- ing sets of G (n, p) -u of size r with one marked vertex v ∈ D ∩ D such that 0 ≤ |N (u) ∩ D \ {v}| ≤ L -1, we get v∈V \{u} E(Z -→ uv 2 ) = r i=1 iQ i E G (n-1,p) W i ,
where Q i is defined in (26). Therefore, since the distribution of Z -→ uv does not depend on v ∈ V \{u},

E(Z -→ uv 2 ) = 1 n -1 r i=1 iQ i E G (n-1,p) W i .
Recall from our assumption on I that n -1 ∈ I. Then, applying Proposition 8 with n -1 instead of n (at the expense of an additional, negligible, multiplicative factor 1 + O(1/n)), we get

E(Z -→ uv 2 ) = 1 n -1 r i=1 iQ i E G (n-1,p) W i =Q 1 r 2 n 2 1 + Θ log 4 n pn + log 3 n p 2 n (EX) 2 .
Hence,

VarZ -→ uv =Q 1 r n 2 1 + Θ log 4 n pn + log 3 n p 2 n (EX) 2 -Q 1 (E G (n-1,p) Z v ) 2 =Q 1 r n 2 1 + Θ log 4 n pn + log 3 n p 2 n (EX) 2 -Q 1 (1 + O(1/n)) r n EX 2 =Q 1 r n 2 O log 4 n pn + log 3 n p 2 n (EX) 2 =Q 1 (E G (n-1,p) Z v ) 2 O log 4 n pn + log 3 n p 2 n = Pr(Bin(r -1, p) < L) × E G (n-1,p) Z v 2 O log 4 n pn + log 3 n p 2 n =(EZ -→ uv ) 2 O log 4 n pn + log 3 n p 2 n ,
and the desired property holds.

Finally, we proceed to the proof of the main theorem.

Proof of Theorem 3. Let ε > 0 be an arbitrarily small constant such that n -1/3+ε ≤ p ≤ 1 -ε, and recall that G = (V, E) denotes a random outcome of G (n, p). Corollary 9 yields immediately the first part of the statement for a less restrictive range of p. To prove the second part, we combine the strategy described in Observation 11 together with Lemma 12: our goal is to show that, for some sufficiently small constant δ > 0 (only depending on ε), a.a.s. for any set A of at most δnp edges of G, the sum of light and heavy damages of A is strictly less than 3 4 EX. Thus, since a.a.s. X = (1 + o(1))EX (by Corollary 9), we infer that a.a.s. not all dominating sets can be removed by deleting at most δnp edges of G, yielding the desired lower bound on b(G). The upper bound follows from [START_REF] Bauer | Domination alteration sets in graphs[END_REF].

We will first bound the heavy damage of any set of at most δnp edges in E. For convenience, we say that a directed pair -→ uv is present in G (or is a directed edge of G) if the corresponding pair uv belongs to E. Using Lemma 14, by Chebyshev's inequality and noting that O log 4 n pn + log 3 n p 2 n = O log 4 n p 2 n , for any directed pair -→ uv (possibly not present in G) and t > 0

Pr Z -→ uv -EZ -→ uv ≥ tEZ -→ uv ≤ VarZ -→ uv tEZ -→ uv 2 = O log 4 n t 2 p 2 n . ( 35
)
Making use of the subsubsequence principle (see e.g. [START_REF] Janson | Random Graphs[END_REF]), we split the analysis into two cases, depending on the asymptotic behaviour of p:

set ν = 2 -ε/2 if p = o(1); and ν = 1 + ε 2 if p = Θ(1)
and p ≤ 1 -ε. Using Lemma 13, the equation above yields

Pr Z -→ uv ≥ EX (pn) ν (1 + t) = O log 4 n t 2 p 2 n . (36)
Clearly, (36) implies that, uniformly for all i ≥ 1,

Pr Z -→ uv ≥ EX (pn) ν 2 i = O log 4 n 2 2i p 2 n . (37)
We call a directed pair -→ uv (possibly not in G) i-bad if

2 i EX (pn) ν ≤ Z -→ uv < 2 i+1 EX (pn) ν
and bad if it is i-bad for some i ≥ 1. Directed pairs that are not bad will be called good. Observe from its definition that Z -→ uv is independent of the event that -→ uv is present in G. Hence, using (37), the probability that a directed pair -→ uv is i-bad and is present in G is p • O log 4 n 2 2i p 2 n , and therefore the heavy damage of all bad directed edges in the graph G is in expectation at most Consequently, by Markov's inequality, the heavy damage of all bad directed edges in G is a.a.s. at most EX log 5 n/(p 1+ν n ν-1 ) = o(EX), as long as p ≥ n -1/3+ε and p ≤ 1 -ε. On the other hand, the heavy damage of a good directed pair is at most 2 EX (pn) ν by definition. Therefore, given any set A of pairs (possibly not in G) of size at most δpn, the heavy damage of the set of all good directed pairs -→ uv such that uv ∈ A is deterministically at most where in the last step we used again our assumptions on p. Putting all the above together, we conclude that a.a.s. the heavy damage of any set of edges A in the graph G with |A| ≤ δnp is

Z A = o(EX). (38)
Now we proceed to bound the light damage of any set A of edges in G of size at most δnp. The analysis bears some similarities to our previous estimation of the heavy damage, but the role of directed pairs will be taken by vertices.

Using Lemma 10, by Chebyshev's inequality and noting that VarZ v = O log 4 n p 2 n (EZ v ) 2 , for any vertex v and s > 0,

Pr (|Z v -EZ v | ≥ sEZ v ) ≤ VarZ v (sEZ v ) 2 = O log 4 n s 2 p 2 n .
Thus,

Pr Z v ≥ EX r n (1 + s) = O log 4 n s 2 p 2 n . (39)
Clearly, (39) implies that, uniformly for all i ≥ 1,

Pr Z v ≥ EX r n 2 i = O log 4 n 2 2i p 2 n . ( 40
)
We call a vertex v i-exceptional, if

2 i EX r n ≤ Z v ≤ 2 i+1 EX r n ,
and exceptional if it is i-exceptional for some i ≥ 1. Let V 1 ⊆ V be the set of all exceptional vertices in the graph G. We want to bound the number v∈V 1 Z v of dominating sets of size r containing at least one exceptional vertex. Since we are summing over a random set, it is convenient to interprete the previous sum as

v∈V 1 Z v = v∈V Z v 1 {v∈V 1 } ,
where 1 {v∈V 1 } is the indicator function of the event that v ∈ V 1 . Hence, in view of (40) and by the linearity of expectation,

E v∈V 1 Z v = n i≥1 2 i+1 EX r n O log 4 n 2 2i p 2 n = O EX r log 4 n p 2 n i≥0 2 -i = O EX log 5 n p 3 n .
Thus, by Markov's inequality, a.a.s.

v∈V 1 Z v ≤ EX log 6 n p 3 n . ( 41
)
We call a vertex normal if it is not exceptional. For a normal vertex v, Z v is at most 2EX r n by definition. Now, for a given set A of edges in G of size at most δpn, let V (A) be the set of vertices containing all endpoints of edges from A, that is,

V (A) = {v ∈ V | ∃e ∈ A such that v ∈ e}.
Partition V (A) as follows: V (A) = V 0 (A) ∪ V 1 (A), where V 0 (A) is the subset of normal vertices, and V 1 (A) the subset of exceptional vertices. From the definition of light damage, we get

Z A ≤ v∈V (A) Z v /(ε 2 pr) = v∈V 0 (A) Z v /(ε 2 pr) + v∈V 1 (A)
Z v /(ε 2 pr).

(42)

For the first sum on the RHS of (42), we have

v∈V 0 (A) Z v ε 2 pr ≤ 2|V 0 (A)|EX ε 2 pn ≤ 4|A|EX ε 2 pn ≤ 4δEX ε 2 ≤ EX/2,
deterministically and regardless of the choice of A, as long as δ ≤ ε 2 /8. On the other hand, for the second sum on the RHS of (42), we use (41), and obtain that a.a.s. for every choice of A

v∈V 1 (A) Z v ε 2 pr ≤ v∈V 1 Z v ε 2 pr ≤ 1 ε 2 pr EX log 6 n p 3 n = O EX log 5 n p 3 n = o(EX),
since p ≥ n -1/3+ε . Hence, a.a.s. for every set A of edges of G with |A| ≤ δnp, we have

Z A ≤ (1 + o(1)) EX 2 .
Combining this, (38) and Corollary 9, we conclude that a.a.s. for every choice of A,

Z A < 3 4 EX < X,
as required. The second part of the statement follows and the proof is finished.

  b(G) ≤ min xy∈E {deg(x) + deg(y) -1 -|N (x) ∩ N (y)|}. It follows that if p = Ω(1), then a.a.s. b(G (n, p)) ≤ (2p -p 2 )n(1 + o(1)).

Lemma 12 .

 12 For every set A of pairs (not necessarily A ⊆ E), Y A ≤ Z A . Proof. The proof is straightforward. Let D ∈ D be a dominating set of G of size r contributing to Y A . Since D fails to dominate the rest of the graph G -A, there must be some vertex u / ∈ D (but, of course, adjacent to some vertex in D) such that all |N (u) ∩ D| edges connecting u and D in G belong to A (and thus are removed). Each of the corresponding directed pairs -→ uv (for v ∈ N (u) ∩ D) contributes 1/|N (u) ∩ D| to the total damage.

log 4 n 2 2i p 2 n = O EX log 4 n p 1+ν n ν- 1 i≥0 2 -

 12 i = O EX log 4 n p 1+ν n ν-1 .

2δpn • 2

 2 EX (pn) ν = O EX (pn) ν-1 = o(EX),

Proof. From Proposition 8 (i) and (ii), we get EW 0 ≤ (1 + o( 1))(EX) 2 and r i=1

where we used that r 2 /n = o(1) by Lemma 6(ii). Therefore,

and thus, by Chebyshev's inequality, we conclude that X ∼ EX ∼ f (n, r, p) → ∞. The second claim in the statement follows immediately from the fact that EX r-1 = f (n, r -1, p) = o(1) (from the definition of r in ( 4)).

Before we state the next lemma, we need one more definition. For a given vertex v, let Z v be the random variable counting the number of dominating sets of size r containing vertex v. We will use Proposition 8 to prove the following observation.

Lemma 10. Given a constant ε > 0, assume that log 2 n/ √ n p ≤ 1 -ε and condition (6) is satisfied for some infinite set I ⊆ N. Then, the following holds for G (n, p) and any vertex v ∈ [n]:

Proof. First note that

as both sides count dominating sets in D with one vertex marked. So EZ v = r n EX by linearity of expectation and since all Z v have the same distribution, and the first part holds. Similarly,

since both sides count pairs of dominating sets D, D ∈ D with one marked vertex in the intersection.

Therefore,

for some h = Θ( log 4 n pn + log 3 n p 2 n ), by Proposition 8. The bound on the variance in the statement follows immediately, and the proof of the lemma is finished.

Proof of Theorem 3

In order to prove our main result, we first analyze the effect that removing one edge has on the number of dominating sets of smallest size. Given p = p n , recall the definitions of f (n, k, p) and r in (3) and (4). Also recall X = X r and D = D r . Let G = (V, E) be a random outcome of G (n, p).Throughout this section, a pair uv always refers to a pair of different vertices u, v ∈ V (a pair uv may or may not be an edge in E). Similarly, a directed pair -→ uv refers to the corresponding D ∈ D j, -→ uv appears in G + uv, weighted by 1/j, over all possible choices of D.

EZ-

EX ∼ EX pn .

For Z -→ uv we get better bounds:

Lemma 13. Given any constant ε > 0 sufficiently small, assume that log 2 / √ n p ≤ 1-ε. Then, for n sufficiently large and for any -→ uv,

Proof. Arguing as in (34) and by Lemma 6(ii), we have

By the stronger version of Chernoff's bound given in [START_REF] Wieland | On the domination number of a random graph[END_REF], writing = -log , Pr(Bin(r, p) ≤ L) = Pr(Bin(r, p) ≤ pr) ≤ exp(-rpϕ( -1)) ≤ exp(-rp(1 -)).

Note that gets small when does, even if at a slower rate. If p → 0, we have

Now, by our choice of = ε 2 and using the fact that 2ε log ε → 0 as ε → 0, we have 1 -2 = 1 -2 + 2 log > 1 -ε/2, and the statement follows in this case. where we assumed that ε (and thus ) was chosen to be small enough so that the following holds: < (1 -)p/ log(1/(1 -p)) (note that p close to 1 forces a small , and therefore a small ε). The desired statement follows since > = ε 2 .