THE DELETION METHOD FOR UPPER TAIL ESTIMATES

SVANTE JANSON AND ANDRZEJ RUCIŃSKI

Abstract. We present a new method to show concentration of the upper tail of random variables that can be written as sums of variables with plenty of independence. The method is formally different from a recent method by Kim and Vu, but in many cases it leads to the same results.

Several applications to random graphs are given. In particular, for X_{K_{4}} being the number of copies of K_{4} in the random graph 𝔾(n, p), with p ≤ n^{1/2}, we almost precisely determine the asymptotics of ln ℙ(X_{K_{4}} ≥ 2 𝔼 X_{K_{4}}).

1. Introduction

Kim and Vu [6] and Vu [12, 14, 15] have developed a very interesting new method to show concentration of certain random variables, i.e. to obtain upper bounds (typically exponentially small) of the probabilities ℙ(X ≤ μ − t) and ℙ(X ≥ μ + t), where X is the random variable, μ = 𝔼 X and t > 0; see also the further references with various applications given in these papers. Two key features of their method are that a basic martingale inequality is used inductively, and that, when applied to a function of some underlying independent random variables, the obtained estimates use the average influence of one or several of the underlying variables, in contrast to e.g. Azuma’s inequality where the maximum influence appears; the latter improvement is crucial for many applications.

In the present paper, we introduce another method, based on ideas by Rödl and Ruciński [8], to obtain bounds for the upper tail ℙ(X ≥ μ + t). The new method, which we call the deletion method, see Remark 2.10, is formally quite different from the method of Kim and Vu; it is based on different ideas and the basic estimate differs from their results. Nevertheless, in many situations both methods naturally lead to induction yielding very similar estimates. Indeed, in the applications we have tried so far, we obtain, up to the values of inessential numerical constants, the same results as by the method of Kim and Vu. The only exception is Example 6.7 which gives a new and essentially sharp bound on the probability of having e.g. twice as many copies of K_{4} as expected in a random graph, improving an earlier bound by Vu [14], but we guess that the new bound could be derived using Kim and Vu’s method too.

There are several reasons for presenting the new method, even if we cannot claim that it produces new results. First, in some applications, although the methods yield the same final result, our method may be somewhat easier to apply. In other applications, the required estimates are the same, and we invite the reader to form his or her own opinion by comparing the two methods on the examples in Section 6.

Date: October 26, 2000; revised December 18, 2000.

Research of the second author supported by KBN grant 2 P03A 032 16.

Secondly, the new method is stated in a different and more general setting than Kim and Vu’s method, at least in current versions. Kim and Vu generally study variables that can be expressed as polynomials in independent random variables; we have no need for this constraint and instead use certain independence assumptions. Hence it is conceivable that applications will emerge where only the new method can be applied.

Thirdly, applications may emerge where the numerical constants in the results are important. In such cases, we do not know which of the methods can be trimmed to yield the best result.

Fourthly, we want to stimulate more research into these methods. Neither of the methods seems yet to be fully developed and in a final version, and it is likely that further versions will appear and turn out to be important for applications. It would be most interesting to find formal relations and implications between Kim and Vu’s method and our new method, possibly by finding a third approach that encompasses both methods. Conversely, it would also be very interesting and illuminating to find applications where the methods yield different results.

Of course, our method has the drawback that it applies to the upper tail only, but this is not serious, since bounds for the lower tail easily are obtained by other well-known methods, see Janson [1], Suen [11] and Janson [2], or the survey in [3, Chapter 2]. As a complement to our estimates for the upper tail, we give in Section 7 as an appendix a new version of Suen’s inequality that applies in the setting of our basic theorem. Note that the bounds for the lower tail obtained by these methods often are much better (i.e. show faster decay) than the bounds obtained for the upper tail by the deletion method. Indeed, it seems that in many applications, the lower tail really is much more concentrated than the upper tail, see Example 6.7 for an example and some explanation. Nevertheless, it is convenient to obtain estimates for both tails at the same time, as by Kim and Vu’s method, so we leave the question whether the deletion method can be extended to the lower tail as an important open problem.

Problem 1.1. Does the bound for ℙ(X ≥ μ + t) in Theorem 2.1 below apply to ℙ(X ≤ μ − t) too?

The basic theorem is stated and proved in Section 2, together with some immediate consequences. These results are directly applicable in some situations. In other cases, the basic result may be used repeatedly with an inductive argument. We give in Section 3 several results obtained in that way for rather general situations. These theorems are still a bit technical, and we give in Section 4 several more easily applicable corollaries.

The results in this paper are to a large extent inspired by the results of Kim and Vu. In Sections 5 and 6 we give several examples where we rederive some of their results using our method. We give also a few other applications. For comparisons with other methods, we refer to [5].

We use ln for natural logarithms and lg for logarithms with base 2. If Γ is a set and k ≥ 1 a natural number, then [Γ]^{k} denotes the family of all subsets I ⊆ Γ with |I| = k and [Γ]^{≤k} := ⋃_{j=0}^{k}[Γ]^{j} denotes the family of all subsets I ⊆ Γ with |I| ≤ k. We use c or C, sometimes with subscripts or superscripts, to denote various constants that may depend on the parameter k only, unless we explicitly give some parameters; we often give explicit values for these constants, but we have not tried to optimize them.

2. The basic theorem

We begin with a general theorem stated for sums of random variables with a dependency graph given for the summands. We need here only the weak version of dependency graphs with independence between a single vertex and the set of its non-neighbours. Cf. Theorem 7.1, where a stronger version is used. Note that, except in trivial cases, we demand α ∼ α in the theorem, because a non-constant random variable is not independent of itself; in other words, we define dependency graphs to have loops at every vertex except when the corresponding variable is constant.

Theorem 2.1. Suppose that Y_{α}, α ∈ A, is a finite family of non-negative random variables and that ∼ is a symmetric relation on the index set A such that each Y_{α} is independent of {Y_{β} : β ≁ α}; in other words, the pairs (α, β) with α ∼ β define the edge set of a (weak) dependency graph for the variables Y_{α}. Let X := ∑_{α} Y_{α} and μ := 𝔼 X = ∑_{α} 𝔼 Y_{α}. Let further, for α ∈ A, X̃_{α} := ∑_{β∼α} Y_{β} and

X^{∗} := max_{α∈A} X̃_{α}.

If t > 0, then for every real r > 0,

\begin{aligned}ℙ(X ≥ μ + t) & ≤ (1 + \frac{t}{2μ})^{−r} + ℙ(X^{∗} > \frac{t}{2r}) \\ & ≤ (1 + \frac{t}{μ})^{−r/2} + ∑_{α∈A} ℙ(X̃_{α} > \frac{t}{2r}). \end{aligned}

Remark 2.2. In applications, a suitable value of r has to be found that makes both terms in the estimate small; note that the first terms in the estimates decrease with r, while the second terms increase. Of course, the theorem is useless unless we can bound the probability that X̃_{α} is large. We will later see several ways of doing this.

For the first terms it is often convenient to use the estimate

(1 + \frac{t}{μ})^{−r/2} ≤ \begin{cases}e^{−rt/3μ}, & t ≤ μ; \\ e^{−r/3}, & t ≥ μ; \end{cases}

this follows since ln(1 + t/μ) ≥ min(t/μ, 1) ln 2 by concavity, and ln 2 > 2/3.

Proof. Let ^{∑*}_{α_{1},...,α_{m}} denote the sum over all sequences of α_{1}, …, α_{m} ∈ A such that α_{j} ≁ α_{j} for 1 ≤ i < j ≤ m. We first show that for every integer m ≥ 1, letting X_{+} := max(X, 0),

\begin{matrix}∑ & * \\ α_{1},...,α_{m} \end{matrix} Y_{α_{1}} ⋯ Y_{α_{m}} ≥ ∏_{j=0}^{m−1}(X − jX^{∗})_{+} ≥ (X − (m − 1)X^{∗})_{+}^{m}.  (2.1)

To verify this, suppose that α_{1}, …, α_{m−1} are given. Then

∑_{α∼α_{i} for some i<m} Y_{α} ≤ ∑_{i=1}^{m−1} X̃_{α_{i}} ≤ (m − 1)X^{∗},

and consequently

∑_{α≁α_{i}, i≤m−1} Y_{α} ≥ (X − (m − 1)X^{∗})_{+}.

Hence,

\begin{matrix}∑ & * \\ α_{1},...,α_{m} \end{matrix} Y_{α_{1}} ⋯ Y_{α_{m}} ≥ (X − (m − 1)X^{∗})_{+} \begin{matrix}∑ & * \\ α_{1},...,α_{m−1} \end{matrix} Y_{α_{1}} ⋯ Y_{α_{m−1}}

and (2.1) follows by induction.

Next, taking the expectations in (2.1) and observing that the factors in each term in the sum are assumed to be independent,

𝔼(X − (m − 1)X^{∗})_{+}^{m} ≤ \begin{matrix}∑ & * \\ α_{1},...,α_{m} \end{matrix} 𝔼 Y_{α_{1}} ⋯ 𝔼 Y_{α_{m}} ≤ (∑_{α} 𝔼 Y_{α})^{m} = μ^{m}. (2.2)

Now, take m = ⌈r⌉. If X ≥ μ + t and X^{∗} ≤ t/2r, then (m − 1)X^{∗} ≤ t/2 and thus X − (m − 1)X^{∗} ≥ μ + t/2. Consequently, using Markov’s inequality and (2.2),

ℙ(X ≥ μ + t) ≤ ℙ(X^{∗} > t/2r) + ℙ(X − (m − 1)X^{∗} ≥ μ + t/2)

≤ ℙ(X^{∗} > t/2r) + (μ + t/2)^{−m} 𝔼(X − (m − 1)X^{∗})_{+}^{m}

≤ ℙ(X^{∗} > \frac{t}{2r}) + (\frac{μ}{μ + t/2})^{m}

≤ ℙ(X^{∗} > \frac{t}{2r}) + (1 + \frac{t}{2μ})^{−r}.

This shows the first inequality in the statement. The second follows easily, using (1 + x/2)^{2} > 1 + x and thus (1 + x/2)^{−1} < (1 + x)^{−1/2} for x > 0. □

In combinatorial applications, the variables Y_{α} usually are indexed by subsets of some index set Γ. We then obtain the following estimate.

Theorem 2.3. Suppose that H ⊆ [Γ]^{≤k} for an integer k ≥ 1, and that Y_{I}, I ∈ H, is a family of non-negative random variables such that each Y_{I} is independent of {Y_{J} : J ∩ I = ∅}. Let X := ∑_{I} Y_{I} and μ := 𝔼 X = ∑_{I} 𝔼 Y_{I}. Let further, for I ⊆ Γ, X_{I} := ∑_{J⊇I} Y_{J} and

X_{1}^{∗} := max_{i∈Γ} X_{{i}}.

If t > 0, then for every real r > 0,

\begin{aligned}ℙ(X ≥ μ + t) & ≤ (1 + \frac{t}{2μ})^{−r} + ℙ(X_{1}^{∗} > \frac{t}{2kr}) \\ & ≤ (1 + \frac{t}{μ})^{−r/2} + ∑_{i∈Γ} ℙ(X_{\{i\}} > \frac{t}{2kr}). \end{aligned}

Proof. We apply Theorem 2.1 with A = H and I ∼ J if I ∩ J ≠ ∅, and note that

X̃_{I} = ∑_{J∩I≠∅} Y_{J} ≤ ∑_{i∈I} X_{{i}} ≤ kX_{1}^{∗}.  □

In some applications, the summands Y_{I} satisfy a stronger independence assumption: two common elements are needed for dependence. For example, this is the case for variables that are indexed by subsets of vertices of the random graph 𝔾(n, p), but are functions of edge indicators. (See e.g. [3] for definition of 𝔾(n, p).) In this case, we have the following alternative to Theorem 2.3, which usually gives stronger bounds.

Theorem 2.4. Suppose that H ⊆ [Γ]^{≤k} for an integer k ≥ 2, and that Y_{I}, I ∈ H, is a family of non-negative random variables such that each Y_{I} is independent of {Y_{J} : |J ∩ I| ≤ 1}. Let X := ∑_{I} Y_{I} and μ := 𝔼 X = ∑_{I} 𝔼 Y_{I}. Let further, for I ⊆ Γ, X_{I} := ∑_{J⊇I} Y_{J} and

X_{2}^{∗} := max_{i≠j∈Γ} X_{{i,j}}.

If t > 0, then for every real r > 0,

\begin{aligned}ℙ(X ≥ μ + t) & ≤ (1 + \frac{t}{2μ})^{−r} + ℙ(X_{2}^{∗} > \frac{t}{k(k − 1)r}) \\ & ≤ (1 + \frac{t}{μ})^{−r/2} + ∑_{\{i,j\}∈[Γ]^{2}} ℙ(X_{\{i,j\}} > \frac{t}{k(k − 1)r}). \end{aligned}

Proof. This time we apply Theorem 2.1 with I ∼ J if |I ∩ J| ≥ 2, and note that

X̃_{I} = ∑_{|J∩I|≥2} Y_{J} ≤ ∑_{\{i,j\}∈[I]^{2}} X_{\{i,j\}} ≤ \binom{k}{2}X_{2}^{∗}.  □

Remark 2.5. For random graphs, another possibility leading to the same bounds is to use Theorem 2.3 with Γ being the set of edges of the complete graph; nevertheless, Theorem 2.4 is often more convenient and will be useful in Section 3.

As remarked in Remark 2.2, there are several ways to bound the term ℙ(X̃_{α} > t/2r) in Theorem 2.1 and the corresponding terms in Theorems 2.3 and 2.4. It seems that this problem has to be approached on a case to case basis, and that there is room for ingenuity and ad hoc arguments.

In some cases, these terms can be estimated directly, for example using a Chernoff bound for sums of independent variables as in Example 6.6 below. We use a related but more complicated argument, using two Chernoff estimates, in Example 6.7.

In other applications, the terms are naturally estimated by induction; we explore this in detail in Section 3.

The simplest possibility to estimate these probabilities is to choose r so small that they trivially vanish, as in the following corollaries.

Corollary 2.6. Let the assumptions of Theorem 2.1 hold. Suppose further that M is a number such that 0 ≤ Y_{α} ≤ M for each α, and let Δ := max_{i} |{j : j ∼ i}|, the maximum degree of the dependency graph (with loops contributing 1). Then

ℙ(X ≥ μ + t) ≤ (1 + \frac{t}{μ})^{−t/(4MΔ)}.

Proof. Take r = t/(2MΔ) in Theorem 2.1 and observe that then X̃_{α} ≤ ΔM = t/2r. □

Corollary 2.7. Let the assumptions of Theorem 2.3 hold. Suppose further that M is a number such that 0 ≤ Y_{I} ≤ M for each I, and let N := |Γ| and Δ_{1} := max_{i∈Γ} |{J ∈ H : i ∈ J}|. Then

ℙ(X ≥ μ + t) ≤ (1 + \frac{t}{μ})^{−t/(4kMΔ_{1})} ≤ (1 + \frac{t}{μ})^{−t/(4kMN^{k−1})}.

Proof. Take r = t/(2kMΔ_{1}) in Theorem 2.3 and observe that Δ_{1} ≤ N^{k−1}. □

Corollary 2.8. Let the assumptions of Theorem 2.4 hold. Suppose further that M is a number such that 0 ≤ Y_{I} ≤ M for each I, and let N := |Γ| and Δ_{2} := max_{i≠j∈Γ} |{J ∈ H : i, j ∈ J}|. Then

ℙ(X ≥ μ + t) ≤ (1 + \frac{t}{μ})^{−t/(2k(k−1)MΔ_{2})} ≤ (1 + \frac{t}{μ})^{−t/(2k^{2}MN^{k−2})}.

Proof. Take r = t/(k(k − 1)MΔ_{2}) in Theorem 2.4 and observe that Δ_{2} ≤ N^{k−2}. □

These corollaries yield essentially the same estimate as the one obtained (for a special case) in [3, Proposition 2.44] by another method, based on another idea by Rödl and Ruciński [7]. See also [5].

Note further that for the case of independent summands (Δ = 1 in Corollary 2.6, k = 1 in Corollary 2.7 or k = 2 in Corollary 2.8), we obtain, at least for t = O(μ), up to a constant in the exponent, the well-known Chernoff bound, see e.g. [3, Chapter 2].

Remark 2.9. Sometimes, for example when studying random hypergraphs, even stronger independence properties than in Theorem 2.4 may hold; for instance that Y_{I} is independent of {Y_{J} : |J ∩ I| < 3}. All such cases are easily handled by Theorem 2.1, and we leave the formulation of analogues of Theorem 2.4 to the reader.

Remark 2.10. The reason that we call this approach “the deletion method” is that the original version stated roughly, in the setting of Theorem 2.3, that with probability at least 1 − (1 + t/μ)^{−r}, it is possible to find a subset E of Γ of order at most rk such that if we delete all Y_{I} with I ∩ E ≠ ∅, then the sum of the remaining Y_{I}’s is at most μ + t, see [8] and [3, Lemma 2.51]. The theorems above combine this with trivial estimates of the deleted terms.

3. Induction

In many cases, Theorem 2.3 can be used inductively. A general setting where this is possible is described by the following set of assumptions, which will be used throughout this section and the next one.

(H1) Let, as above, X := ∑_{I} Y_{I}, where Y_{I}, I ∈ H ⊆ [Γ]^{≤k} for some finite index set Γ and an integer k ≥ 1, is a family of non-negative random variables.

Suppose further that A is another index set and that there is a family ξ_{α}, α ∈ A, of independent random variables and a family of subsets A_{I} ⊆ A, I ∈ [Γ]^{≤k}, such that each Y_{I} is a function of {ξ_{α} : α ∈ A_{I}} and, further, A_{∅} = ∅ and A_{I} ∩ A_{J} = A_{I∩J} for all I, J ∈ [Γ]^{≤k}.

Let μ := 𝔼 X and N := |Γ|. To avoid trivialities, assume N > 1.

Note that although Y_{I} is defined for I ∈ H only, we want A to be defined for all I ∈ [Γ]^{≤k}. Actually, we can without loss of generality assume that Y_{I} is defined for all I ∈ [Γ]^{≤k} too, by setting Y_{I} = 0 for I ∉ H, but this is slightly inconvenient in applications.

It is easily seen that the assumptions of Theorem 2.3 hold under (H1). The situation studied here is more special than in Theorem 2.3, but applications are usually of this type. The conditions (H1) are a bit technical, and we give some examples.

Example 3.1. In many applications we simply take A = Γ and A_{I} = I. In other words, ξ_{i}, i ∈ Γ, are independent random variables and Y_{I} is a function of {ξ_{i} : i ∈ I}.

Example 3.2. An important special case of Example 3.1 is when each ξ_{i} is an indicator random variable, i.e. attains the values 0 and 1 only, and Y_{I} = ∏_{i∈I} ξ_{i}. In other words, the indicator random variables ξ_{i} describe a random (Bernoulli) subset Γ_{p} of Γ, p = (p_{1}, …, p_{N}), where p_{i} = ℙ(ξ_{i} = 1), and X is the number of elements of H that are contained in Γ_{p}.

Example 3.3. We may treat subgraph counts in the random graph 𝔾(n, p) as in Example 3.2, letting Γ be the set of all edges in the complete graph K_{n}, H the family of edge sets of copies of a given graph G assumed to have no isolated vertices, and ξ_{i} the indicator that edge i is present in 𝔾(n, p); we thus take k to be the number of edges in G. (See e.g. [3] for various properties of subgraph counts of 𝔾(n, p).)

Example 3.4. To treat the number of induced copies in 𝔾(n, p) of a given graph G with v(G) vertices, we may again let Γ, A, A_{I} and ξ_{i} be as in Examples 3.3 and 3.1, but now letting H be the family of edge sets of copies of K_{v(G)} and Y_{I} the indicator of the event that the subgraph of 𝔾(n, p) defined by I is isomorphic to G. Here k = \binom{v(G)}{2}.

We now consider some examples where A and Γ are not the same.

Example 3.5. Subgraph counts can also be treated as follows. Let Γ = V (K_{n}) be the vertex set of the complete graph K_{n} and let A = [Γ]^{2} be its edge set. Let ξ_{α} be the indicator variable showing whether the edge α is present or not in 𝔾(n, p), and let, for I ⊆ Γ, A_{I} = [I]^{2}, the set of all edges in K_{n} with both endpoints in I. Again, let G be a fixed graph, and let Y_{I} be the number of copies of G in 𝔾(n, p) that have vertex set I; this time we thus take k to be the number of vertices of G and H = [Γ]^{k}. Induced copies of G can be treated in exactly the same way.

Example 3.6. For substructure counts in random ℓ-uniform hypergraphs, we similarly may take A = [Γ]^{ℓ}. Here ℓ can be any positive integer.

Example 3.7. For an example with A = ⋃_{j=1}^{2}[Γ]^{j} and A_{I} = [I]^{≤2}∩A, suppose that the vertices in the random graph 𝔾(n, p) are randomly coloured using 7 different colours. Then the number of rainbow 7-cycles, i.e. cycles containing exactly one vertex of each colour, is a sum X of this type; we let ξ_{i}, i ∈ [Γ]^{1} = Γ, be the colour of vertex i, and ξ_{α}, α ∈ [Γ]^{2}, be the indicator of edge α. Further examples with such A are given in [4].

Example 3.8. More generally, we can take any A ⊆ ⋃_{j=1}^{ℓ}[Γ]^{j} = [Γ]^{≤ℓ}\{∅}, for some ℓ, and A_{I} = [I]^{≤ℓ}∩A. For another example with ℓ = 2 and A = ⋃_{j=1}^{2}[Γ]^{j}, consider the number of extensions of a given type in 𝔾(n, p) with fixed roots {1, …, r}; we take Γ = {r + 1, …, n}, let ξ_{{i,j}}, {i, j} ∈ [Γ]^{2}, be the random indicator of the edge ij and let ξ_{i}, i ∈ [Γ]^{1} = Γ, be the random vector of edge indicators (ξ_{i1}, …, ξ_{ir}).

Subgraph counts in random graphs can thus be treated in two different ways; this is similar to the choice between vertex exposure and edge exposure in martingale arguments. It turns out that in many cases, the approach in Example 3.5 yields better results with the theorems below, although we do not know whether that always holds. One reason why the latter approach is better is that it usually gives a lower value of k; another is that it exhibits the stronger independence assumption in Theorem 2.4.

In order to formulate our results, we need some more notation. Let as above X_{I} := ∑_{J⊇I} Y_{J} and consider 𝔼(X_{I} | ξ_{α}, α ∈ A_{I}), the conditional expectation of X_{I} when we fix the values of ξ_{α} for α ∈ A_{I} (i.e. taking the expectation over ξ_{α}, α ∉ A_{I}). This is a function of ξ_{α}, α ∈ A_{I}, and we define μ_{I} to be its maximum (or, in general, supremum):

μ_{I} := sup 𝔼(X_{I} | ξ_{α}, α ∈ A_{I}).  (3.1)

Further let, for l ≤ k,

μ_{l} := max_{|I|=l} μ_{I}.  (3.2)

In other words, μ_{l} is the smallest number such that 𝔼(X_{I} | ξ_{α}, α ∈ A_{I}) ≤ μ_{l} for every I ∈ H with |I| = l and every choice of values of ξ_{α}, α ∈ A_{I}.

Note that if |I| = k, then X_{I} = Y_{I}, which is a function of ξ_{α}, α ∈ A_{I}, and consequently, 𝔼(X_{I} | ξ_{α}, α ∈ A_{I}) = Y_{I} and μ_{I} = sup Y_{I}. Hence,

μ_{k} = max_{|I|=k} sup X_{I} = max_{|I|=k} sup Y_{I}.  (3.3)

Moreover, trivially μ_{0} = μ = 𝔼 X.

Example 3.9. In Example 3.2, μ_{I} is the expected number of elements J ∈ H such that I ⊆ J ⊆ Γ_{p}, given that I ⊆ Γ_{p}. In the special case ℙ(ξ_{i} = 1) = p for all i, we obtain μ_{I} = ∑_{J∈H, J⊇I} p^{|J|−|I|}.

We now can state one of our principal results.

Theorem 3.10. Assume (H1). With notation as above, for every t > 0 and r_{1}, …, r_{k} such that

r_{1} ⋯ r_{j} · μ_{j} ≤ t,  j = 1, …, k,  (3.4)

we have, with c = 1/8k,

ℙ(X ≥ μ + t) ≤ (1 + \frac{t}{μ})^{−cr_{1}} + ∑_{j=1}^{k−1} N^{j}(1 + \frac{t}{r_{1} ⋯ r_{j} μ_{j}} )^{−cr_{j+1}}.  (3.5)

Proof. We apply Theorem 2.3 with r = r_{1}/4k and obtain, letting t_{1} = t/r_{1} = t/4kr,

ℙ(X ≥ μ + t) ≤ (1 + \frac{t}{μ})^{−r/2} + ∑_{i∈Γ} ℙ(X_{\{i\}} > 2t_{1}).  (3.6)

If k = 1, we have by (3.3) and (3.4), for every i ∈ Γ, X_{{i}} ≤ μ_{1} ≤ t/r_{1} = t_{1}, and the result follows by (3.6). (Alternatively, use Corollary 2.7 with M = μ_{1} and Δ_{1} = 1).

If k ≥ 2 we use induction, assuming the theorem to hold for k − 1. Fix i ∈ Γ and let Γ̃ = Γ \ {i}. Then X_{{i}} = ∑_{I∈H̃} Ỹ_{I}, with Ỹ_{I} = Y_{I∪{i}} and H̃ = {I ⊆ Γ̃ : I ∪ {i} ∈ H} ⊆ [Γ̃]^{≤k−1}. Conditioned on ξ_{α}, α ∈ A_{{i}}, the random variables Ỹ_{I} satisfy the assumptions (H1), with Ã = A \ A_{{i}} and Ã_{J} = A_{J∪{i}} \A_{{i}}; the numbers defined by (3.1) and (3.2) become μ̃_{I} ≤ μ_{I∪{i}} and μ̃_{l} ≤ μ_{l+1}. Note further that, by (3.1), (3.2) and (3.4),

𝔼(X_{{i}} | ξ_{α}, α ∈ A_{{i}}) ≤ μ_{{i}} ≤ μ_{1} ≤ t/r_{1} = t_{1}.

Consequently, still conditioning on ξ_{α}, α ∈ A_{{i}}, we can apply the induction hypothesis, with r_{j} replaced by r̃_{j} = r_{j+1} and t replaced by t_{1}, noting that (3.4) holds for these numbers because

r̃_{1} ⋯ r̃_{j} · μ̃_{j} ≤ r_{2} ⋯ r_{j+1} · μ_{j+1} ≤ t/r_{1} = t_{1}.

This yields

\begin{aligned}ℙ(X_{\{i\}} > 2t_{1}) & ≤ ℙ(X_{\{i\}} ≥ 𝔼(X_{\{i\}} | ξ_{α}, α ∈ A_{\{i\}}) + t_{1}) \\ & ≤ (1 + \frac{t_{1}}{μ_{1}} )^{−cr_{2}} + ∑_{j=1}^{k−2} N^{j}(1 + \frac{t_{1}}{r_{2} ⋯ r_{j+1} μ_{j+1}} )^{−cr_{j+2}} \\ & = (1 + \frac{t}{r_{1}μ_{1}} )^{−cr_{2}} + ∑_{j=2}^{k−1} N^{j−1}(1 + \frac{t}{r_{1} ⋯ r_{j} μ_{j}} )^{−cr_{j+1}}. \end{aligned} (3.7)

The same estimate then holds unconditionally, and the result follows from (3.6) and (3.7). □

We still have the freedom, and burden, of choosing suitable values of r_{1}, … r_{k} when applying Theorem 3.10. In the next section, we give several corollaries that are suitable for immediate application, and the impatient reader may proceed there directly.

In the remainder of this section we give some variants of Theorem 3.10 that yield better results under some circumstances.

Stronger independence. In the case of random graphs treated as in Example 3.5, we have the stronger independence property of Theorem 2.4, since we need a common edge, i.e. two common vertices, to get dependence between two variables Y_{I} (or families of such variables). This is expressed by the following property.

(H2) A_{I} = ∅ when |I| ≤ 1. In such cases, we can improve the estimate above. Note that there is no r_{1} in the following statement.

Theorem 3.11. Assume (H1) and (H2). Then, with notation as above, for every t > 0 and r_{2}, r_{3}, …, r_{k} such that

r_{2}r_{3} ⋯ r_{j} · μ_{j} ≤ t,  j = 2, …, k,  (3.8)

we have, with c = 1/4k^{2},

ℙ(X ≥ μ + t) ≤ (1 + \frac{t}{μ})^{−cr_{2}} + ∑_{j=2}^{k−1} N^{j}(1 + \frac{t}{r_{2}r_{3} ⋯ r_{j} μ_{j}} )^{−cr_{j+1}}.  (3.9)

Proof. We apply Theorem 2.4 with r = r_{2}/2k^{2} and obtain, letting t_{1} = t/r_{2} = t/2k^{2}r,

ℙ(X ≥ μ + t) ≤ (1 + \frac{t}{μ})^{−r/2} + ∑_{\{i,j\}∈[Γ]^{2}} ℙ(X_{\{i,j\}} > 2t_{1}).  (3.10)

Each term in the sum is estimated as in the proof of Theorem 3.10; this time we fix two indices i, j ∈ Γ, let Γ̃ = Γ \ {i, j} and have X_{{i,j}} = ∑_{I∈H̃} Ỹ_{I} with Ỹ_{I} = Y_{I∪{i,j}} and H̃ = {I ⊆ Γ̃ : I ∪ {i, j} ∈ H} ⊆ [Γ̃]^{≤k−2}. Conditioned on ξ_{α}, α ∈ A_{{i,j}}, the random variables Ỹ_{I} satisfy (H1), with Ã = A \ A_{{i,j}} and Ã_{J} = A_{J∪{i,j}} \ A_{{i,j}}; the numbers defined by (3.1) and (3.2) become μ̃_{I} ≤ μ_{I∪{i,j}} and μ̃_{l} ≤ μ_{l+2}. Moreover, by (3.1), (3.2) and (3.8),

𝔼(X_{{i,j}} | ξ_{α}, α ∈ A_{{i,j}}) ≤ μ_{{i,j}} ≤ μ_{2} ≤ t/r_{2} = t_{1}.

Consequently, still conditioning on ξ_{α}, α ∈ A_{{i,j}}, we obtain by Theorem 3.10 with k replaced by k − 2, r_{j} replaced by r̃_{j} = r_{j+2} and t replaced by t_{1},

\begin{aligned}ℙ(X_{\{i,j\}} & > 2t_{1}) ≤ ℙ(X_{\{i,j\}} ≥ μ_{\{i,j\}} + t_{1}) \\ & ≤ (1 + \frac{t_{1}}{μ_{2}} )^{−cr_{3}} + ∑_{j=1}^{k−3} N^{j}(1 + \frac{t_{1}}{r_{3} ⋯ r_{j+2} μ_{j+2}} )^{−cr_{j+3}}. \end{aligned}  (3.11)

The same estimate then holds unconditionally, and the result follows from (3.10) and (3.11). □

Note that unlike the proof of Theorem 3.10, this proof does not use induction, since the additional independence hypothesis (H2) does not have to be satisfied by the variables Ỹ_{I}. Instead, we combine Theorem 2.4 and Theorem 3.10, i.e. we combine one application of Theorem 2.4 and repeated applications of Theorem 2.3. This is thus a kind of combination of edge exposure and vertex exposure.

As remarked in Remark 2.9, we sometimes may have even stronger independence properties. For example, for random hypergraphs as in Example 3.6, we need ℓ common vertices to get dependence; more precisely, the following generalization of (H2) holds. (Here ℓ is any integer with 2 ≤ ℓ ≤ k.)

(Hℓ) A_{I} = ∅ when |I| ≤ ℓ − 1. We then have the following generalization of Theorem 3.11.

Theorem 3.12. Assume (H1) and (Hℓ), for some ℓ ≥ 2. Then, with notation as above, for every t > 0 and r_{ℓ}, …, r_{k} such that

r_{ℓ} ⋯ r_{j} · μ_{j} ≤ t,  j = ℓ, …, k,  (3.12)

we have, with c = c(k, ℓ),

ℙ(X ≥ μ + t) ≤ (1 + \frac{t}{μ})^{−cr_{ℓ}} + ∑_{j=ℓ}^{k−1} N^{j}(1 + \frac{t}{r_{ℓ} ⋯ r_{j} μ_{j}} )^{−cr_{j+1}}.  (3.13)

Proof. We apply Theorem 2.1 with I ∼ J when |I ∩ J| ≥ ℓ, estimate X̃_{I} ≤ ∑_{J∈[I]^{ℓ}} X_{J} and use conditioning and Theorem 3.10 as in the proof of Theorem 3.11 to estimate ℙ(X_{J} > t/2r\binom{k}{ℓ}) for |J| = ℓ; we omit the details. □

Further refinements. We define, for 1 ≤ j ≤ k,

M_{j} := max_{|J|=j} sup X_{J}.  (3.14)

Hence M_{k} = μ_{k} by (3.3). We then have the following extension of Theorem 3.10 (which is the case k_{0} = k). It sometimes yields better bounds, but often there is no advantage in taking k_{0} < k because typically then M_{k_{0}} is much larger than μ_{k_{0}}.

Theorem 3.13. Assume (H1), and let k_{0} be an integer with 1 ≤ k_{0} ≤ k. Then, with notation as above, for every t > 0 and r_{1}, …, r_{k_{0}} such that

\begin{matrix}r_{1} ⋯ r_{j} · μ_{j} ≤ t,  j = 1, …, k_{0} − 1, \\ r_{1} ⋯ r_{k_{0}} · M_{k_{0}} ≤ t, \end{matrix}  (3.15)

we have, with c = 1/8k,

ℙ(X ≥ μ + t) ≤ (1 + \frac{t}{μ})^{−cr_{1}} + ∑_{j=1}^{k_{0}−1} N^{j}(1 + \frac{t}{r_{1} ⋯ r_{j} μ_{j}} )^{−cr_{j+1}}.

Proof. If k_{0} = 1, we have by (3.15), for every i ∈ Γ, X_{{i}} ≤ M_{1} ≤ t/r_{1}, and the result follows by taking r = r_{1}/2k in Theorem 2.3.

If k_{0} ≥ 2 we use induction; this time on k_{0}. The same argument as in the proof of Theorem 3.10 completes the proof; we leave the verification to the reader. □

With the stronger independence property (H2), or more generally (Hℓ), we similarly get the following extension of Theorem 3.12.

Theorem 3.14. Assume (H1) and (Hℓ), for some ℓ ≥ 2. Then, with notation as above, for every t > 0, ℓ ≤ k_{0} ≤ k and r_{ℓ} …, r_{k_{0}} such that

r_{ℓ} ⋯ r_{j} · μ_{j} ≤ t, j = ℓ, …, k_{0} − 1,
r_{ℓ} ⋯ r_{k_{0}} · M_{k_{0}} ≤ t,

we have for some c > 0,

ℙ(X ≥ μ + t) ≤ (1 + \frac{t}{μ})^{−cr_{ℓ}} + ∑_{j=ℓ}^{k_{0}−1} N^{j}(1 + \frac{t}{r_{ℓ} ⋯ r_{j} μ_{j}} )^{−cr_{j+1}}.  □

Remark 3.15. In most applications, all summands Y_{I} have |I| = k, but we allow the possibility that different cardinalities occur. In that case, we can make another improvement of the estimates above.

Let X′_{I} := ∑_{J⊋I} Y_{J}, thus omitting the term Y_{I}, and define

μ′_{I} := sup 𝔼(X′_{I} | ξ_{α}, α ∈ A_{I}),
μ′_{l} := max_{|I|=l} μ′_{I}.

Conditioned on ξ_{α}, α ∈ A_{I}, the difference X_{I} − X′_{I} = Y_{I} is a constant, and thus we can in the induction step (3.7) in the proof of Theorem 3.10 use X′_{{i}} instead of X_{{i}}. This leads to the following result; we omit the details: We may replace μ_{j} by μ′_{j} in (3.5) (keeping μ_{j} in (3.4)), and similarly in Theorems 3.11, 3.12, 3.13 and 3.14.

4. Corollaries

We give in this section several corollaries of the theorems in the preceding section, obtained by suitable choices of r_{i}. These corollaries are more convenient for applications, and are often as powerful as the theorems. They have, however, more restricted applicability, so we give several different versions to cover different situations. We continue with the notation of Section 3.

We begin with a consequence of Theorem 3.10. The following explicit bounds are widely applicable and form one of our principal results.

Corollary 4.1. Assume (H1). With notation as above, and c = 1/12k, for every t > 0,

ℙ(X ≥ μ + t) ≤ 2N^{k−1} exp(−c min_{1≤j≤k}(\frac{t lg(1 + t/μ)}{μ_{j}})^{1/j})

≤ \begin{cases}2N^{k−1} exp(−c min_{1≤j≤k}(\frac{t^{2}}{μμ_{j}} )^{1/j}), & t ≤ μ; \\ 2N^{k−1} exp(−c min_{1≤j≤k}(\frac{t}{μ_{j}} )^{1/j}), & t ≥ μ. \end{cases} (4.1)

Proof. We estimate the terms in the sum in (3.5) using (3.4), which implies

1 + \frac{t}{r_{1} ⋯ r_{j} μ_{j}} ≥ 2.  (4.2)

Hence, (3.5) yields, writing τ = lg(1 + t/μ) and c_{1} = 1/8k

ℙ(X ≥ μ + t) ≤ 2^{−c_{1}r_{1}τ} + ∑_{j=2}^{k} N^{j−1}2^{−c_{1}r_{j}}.  (4.3)

We choose r_{1} = r/τ and r_{2}, …, r_{k} = r, where r is the largest number that makes (3.4) hold, i.e.

r = min_{1≤j≤k}(\frac{tτ}{μ_{j}} )^{1/j}.

This makes all exponents of 2 in (4.3) equal to −c_{1}r, and the right hand side of (4.2) can be bounded by

2^{−c_{1}r} ∑_{j=1}^{k} N^{j−1} < e^{−(c_{1} ln 2)r}(2N^{k−1}).

The first estimate follows using c_{1} ln 2 > 2c_{1}/3 = 1/12k = c. The second estimate follows because lg(1 + t/μ) ≥ min(1, t/μ) by concavity. □

Remark 4.2. It is easily seen that the choice of r_{j} in the proof of Corollary 4.1 is essentially optimal in (4.3); any other choice would make one of the exponents of 2 smaller in absolute value, and thus the corresponding term larger; hence the resulting estimate differs from the optimum in (4.3) by at most the factor 2N^{k−1}.

When the stronger independence hypothesis (H2) holds, we obtain a stronger result using Theorem 3.11. This is another of our principal results.

Corollary 4.3. Suppose that (H1) and (H2) hold. With notation as above, and c = 1/6k^{2}, for every t > 0,

ℙ(X ≥ μ + t) ≤ 2N^{k−1} exp(−c min_{2≤j≤k}(\frac{t lg(1 + t/μ)}{μ_{j}})^{1/(j−1)})

≤ \begin{cases}2N^{k−1} exp(−c min_{2≤j≤k}(\frac{t^{2}}{μμ_{j}} )^{1/(j−1)}), & t ≤ μ; \\ 2N^{k−1} exp(−c min_{2≤j≤k}(\frac{t}{μ_{j}} )^{1/(j−1)}), & t ≥ μ. \end{cases} (4.4)

Proof. We use Theorem 3.11 with (4.2), now without r_{1}, choosing r_{2} = r/τ and r_{3}, …, r_{k} = r, where

r = min_{2≤j≤k}(\frac{tτ}{μ_{j}} )^{1/(j−1)}.  □

More generally, we similarly obtain from Theorem 3.12 the following. (As above, we can replace t lg(1 + t/μ) by t^{2}/μ when t ≥ μ.)

Corollary 4.4. Assume (H1) and (Hℓ), for some ℓ ≥ 2. With notation as above, for every t > 0,

ℙ(X ≥ μ + t) ≤ 2N^{k−1} exp(−c min_{ℓ≤j≤k}(\frac{t lg(1 + t/μ)}{μ_{j}})^{1/(j−ℓ+1)}).  □

If we compare Corollaries 4.1 and 4.3, we see that the power in the exponent in Corollary 4.3 is larger. For example, it is often the case that the terms with j = k are the minimum ones; if, for simplicity, further t = μ and μ_{k} = 1, then the estimates are, ignoring the factor 2N^{k−1}, exp(−cμ^{1/k}) and exp(−cμ^{1/(k−1)}), respectively. The difference between the two corollaries stems from the fact that the basic estimate Theorem 2.1 is used (unravelling the induction) k times in the proof of Theorem 3.10 and thus of Corollary 4.1, but only k − 1 times in the proof of Theorem 3.11 and Corollary 4.3, since we there jump by two in the first step. (Corollary 4.4 with ℓ > 2 is even better.)

This is typical for this kind of induction; if we apply the basic estimate inductively m times, and want a final estimate of exp(−λ), we need to choose r_{1}, …, r_{m} roughly equal to λ, at least, and for the final step we need something like t/(r_{1} ⋯ r_{m}) ≥ 1; hence, again for t = μ, typically λ^{m} ≤ μ. Although this is not completely rigorous, it shows that often it is advantageous to avoid too many induction steps.

One way to cut down the number of induction steps is to use Theorems 3.13 and 3.14. Again using (4.2) and choosing r_{j} as in the proofs above, for the largest r now allowed, we obtain the following corollaries. They are sometimes better than Corollaries 4.1, 4.3 and 4.4, but as remarked above, the advantage gained by taking k_{0} < k (and thus reducing the number of induction steps) is often lost because M_{k_{0}} may be much larger than μ_{k_{0}}. We omit the proofs.

Corollary 4.5. Assume (H1). With notation as above, and c = 1/12k, for every k_{0} ≤ k and t > 0,

ℙ(X ≥ μ + t)

≤ 2N^{k_{0}−1} exp(−c min( min_{1≤j≤k_{0}−1}(\frac{t lg(1 + t/μ)}{μ_{j}})^{1/j}, (\frac{t lg(1 + t/μ)}{M_{k_{0}}})^{1/k_{0}})).

□

Corollary 4.6. Assume (H1) and (Hℓ), for some ℓ ≥ 2. With notation as above and some c > 0, for every t > 0 and ℓ ≤ k_{0} ≤ k,

ℙ(X ≥ μ + t)

≤ 2N^{k_{0}−1} exp(−c min( min_{ℓ≤j≤k_{0}−1}(\frac{t lg(1 + t/μ)}{μ_{j}})^{1/(j−ℓ+1)},

(\frac{t lg(1 + t/μ)}{M_{k_{0}}})^{1/(k_{0}−ℓ+1)})).

□

All the corollaries above are useful only when the exponents in them are large. Consider, for simplicity, the case t ≤ μ. The factor N^{k−1} in Corollary 4.1 is harmless when the exponent is much larger than (k − 1) ln N, i.e. if t^{2}/μ ≥ Cμ_{j} ln^{j} N for some large constant C and all 1 ≤ j ≤ k. On the other hand, the corollary is useless if t^{2}/μ ≤ cμ_{j} ln^{j} N for some small constant c and some j ≤ k. In such cases, the following version is better; it yields non-trivial results when t^{2}/μ ≥ Cμ_{j} ln^{j−1} N, 1 ≤ j ≤ k.

Corollary 4.7. Assume (H1). With notation as above and some c > 0, for every t > 0,

ℙ(X ≥ μ + t) ≤ 2 exp(−c min( min_{1≤j≤k}(\frac{t lg(1 + t/μ)}{μ_{j}})^{1/j}, min_{2≤j≤k} \frac{t lg(1 + t/μ)}{μ_{j} ln^{j−1} N})).

Proof. As in the proof of Corollary 4.1, we use (4.3), where τ = lg(1 + t/μ) and c_{1} = 1/8k, but now choose r_{1} = r/τ and r_{j} = r + kc_{1}^{−1} lg N, j ≥ 2, with

r = min(\frac{1}{2} min_{1≤j≤k}(\frac{tτ}{μ_{j}} )^{1/j}, min_{1≤j≤k} \frac{c_{1}^{j−1}tτ}{μ_{j}(2k)^{j−1} lg^{j−1} N} ).

(This yields c = 2^{−(4k−1)}k^{−(2k−1)} ln^{k−1} 2 for k > 1, which certainly can be improved.) □

Again we obtain a stronger result when (Hℓ) holds.

Corollary 4.8. Assume (H1) and (Hℓ), for some ℓ ≥ 2. With notation as above and some c > 0, for every t > 0,

ℙ(X ≥ μ + t)

≤ 2 exp(−c min( min_{ℓ≤j≤k}(\frac{t lg(1 + t/μ)}{μ_{j}})^{1/(j−ℓ+1)}, min_{ℓ+1≤j≤k} \frac{t lg(1 + t/μ)}{μ_{j} ln^{j−ℓ} N})).

Proof. We choose r_{ℓ} = r/τ and r_{j} = r + C lg N, j > ℓ, in Theorem 3.12 and optimize r; we leave the details as an exercise. □

Similarly, we obtain from Theorems 3.13 and 3.14 the following more general results, here condensed into one statement; we omit the proof.

Corollary 4.9. Let 1 ≤ ℓ ≤ k_{0} ≤ k. If ℓ = 1, assume (H1), and if ℓ ≥ 2, assume (H1) and (Hℓ). With notation as above, let μ̄_{j} = μ_{j} for j < k_{0} and μ̄_{k_{0}} = M_{k_{0}}. Then, for every t > 0,

ℙ(X ≥ μ + t)

≤ 2 exp(−c min( min_{ℓ≤j≤k_{0}}(\frac{t lg(1 + t/μ)}{μ̄_{j}})^{1/(j−ℓ+1)}, min_{ℓ+1≤j≤k_{0}} \frac{t lg(1 + t/μ)}{μ̄_{j} ln^{j−ℓ} N})).

□

We have so far used (4.2) and (4.3), and the corresponding estimates obtained from the other theorems, but in some situations with t^{2}/μ small, the full strength of (3.5) etc. is needed. In the following result, we assume that μ_{1}, …, μ_{k−1} are small, while μ_{k} may be 1.

Corollary 4.10. Assume (H1). For every α, β > 0, there is a constant c = c(k, α, β) > 0 such that, with notation as above, if μ_{j} ≤ N^{−α} for 1 ≤ j ≤ k − 1 and μ_{k} ≤ 1, then for 0 < t ≤ μ,

ℙ(X ≥ μ + t) ≤ e^{−ct^{2}/μ} + N^{−β}.

Proof. Let A ≥ 1 be a constant, and choose r_{2}, …, r_{k} = A and r_{1} = A^{1−k}t. Then (3.4) is satisfied, and Theorem 3.10 yields

ℙ(X ≥ μ + t) ≤ (1 + \frac{t}{μ})^{−cA^{1−k}t} + ∑_{j=1}^{k−1} N^{j}(N^{α})^{−cA}.

The result follows by choosing A so that cαA = β + k. □

We obtain two immediate corollaries by letting one of the terms on the right hand side dominate the other.

Corollary 4.11. Assume (H1). For every α, β, ε > 0, there is a constant Q = Q(k, α, β, ε) > 0 such that, with notation as above, if μ_{j} ≤ N^{−α} for 1 ≤ j ≤ k − 1, μ_{k} ≤ 1, and μ ≥ Q ln N, then

ℙ(X ≥ (1 + ε)μ) ≤ N^{−β}.  □

Corollary 4.12. Assume (H1). For every α > 0, there is a constant c = c(k, α) > 0 such that, with notation as above, if μ_{j} ≤ N^{−α} for 1 ≤ j ≤ k − 1, μ_{k} ≤ 1, 0 < ε ≤ 1 and μ ≤ ln N, then

ℙ(X ≥ (1 + ε)μ) ≤ 2e^{−cε^{2}μ}.  □

Remark 4.13. Remark 3.15 implies that in Corollaries 4.10–4.12, the assumptions on μ_{j} may be weakened to μ′_{j} ≤ N^{−α}, 1 ≤ j ≤ k − 1, and Y_{I} ≤ 1, I ∈ H.

5. Relations with Kim and Vu’s results

As said earlier, the results in Sections 3 and 4 are inspired by the results and methods in Kim and Vu [6] and Vu [12, 14, 15], where similar induction arguments are used.

The general setting of Kim and Vu is to consider a random variable X which is a polynomial X(ξ_{1}, …, ξ_{N}) of degree k in N independent random variables ξ_{1}, …, ξ_{N}. (We change their notation to correspond to ours.) It is furthermore assumed that the polynomial has only non-negative coefficients and that 0 ≤ ξ_{i} ≤ 1; sometimes it is further assumed that the variables ξ_{i} are binary, i.e. ξ_{i} ∈ {0, 1}.

Let, for a multi-set A = {i_{1}, …, i_{j}}, ∂_{A}X denote the partial derivative \frac{∂^{j}}{∂ξ_{i_{1}}···∂ξ_{i_{j}}} X(ξ_{1}, …, ξ_{N}), and define E′_{j} := max_{|A|=j} 𝔼(∂_{A}X) and

E_{j} := max_{|A|≥j} 𝔼(∂_{A}X) = max_{l≥j} E′_{l}.

In particular, E_{0} ≥ E′_{0} = 𝔼 X = μ.

This setting is an instance of (H1) as in Example 3.1; we take Γ = A = {1, …, N} and let Y_{I} be the sum of all terms a_{i_{1}···i_{j}}ξ_{i_{1}} ⋯ ξ_{i_{j}} in X such that {i_{1}, …, i_{j}} = I. (If no variable occurs to higher power than 1, Y_{I} is just a single term. Example 3.2 is a special case of this case.)

If no variable occurs to a higher power than 1 in X, then ∂_{A}X = 0 if A contains any repetition, and otherwise ∂_{A}X equals our X_{A} with ξ_{i} replaced by 1 for i ∈ A; hence (assuming sup ξ_{i} = 1 for each i) 𝔼 ∂_{A}X = μ_{A} and μ_{j} = E′_{j}. In general, it is easily seen that

μ_{j} ≤ c ∑_{l=j}^{k} E′_{l} ≤ CE_{j}.  (5.1)

Let us begin with the first estimate by Kim and Vu’s method, the main theorem of [6].

Example 5.1. Let λ ≥ 1, and take t = \sqrt{E_{0}E_{1}}λ^{k}, r_{1} = c_{1}λ\sqrt{E_{0}/E_{1}} and r_{i} = λ for i ≥ 2 in Theorem 3.10. By (5.1), μ_{j} ≤ CE_{1} for every j ≥ 1; hence it is easily checked that if c_{1} = 1/C, then (3.4) is satisfied. Moreover, t/μ ≥ t/E_{0} ≥ (E_{1}/E_{0})^{1/2} and thus

r_{1} lg(1 + t/μ) ≥ r_{1} lg(1 + (E_{1}/E_{0})^{1/2}) ≥ r_{1}(E_{1}/E_{0})^{1/2} = c_{1}λ.

Hence Theorem 3.10 yields the estimate

ℙ(X ≥ μ + (E_{0}E_{1})^{1/2}λ^{k}) ≤ 2N^{k−1}e^{−c_{2}λ}, λ ≥ 1,

which is equivalent to the upper tail part of the main theorem in Kim and Vu [6], see also [15, Theorem 3.1], apart from the numerical value of the constants.

Corollary 4.1 easily yields the somewhat better estimate

ℙ(X ≥ μ + (E_{0}E_{1})^{1/2}λ^{k}) ≤ 2N^{k−1} exp(−c min(λ^{2}, λ(E_{0}/E_{1})^{1/2k})), λ ≥ 1.

These estimates trivially hold for λ ≤ 1 too.

This first result by Kim and Vu is superseded by later results by Vu; we begin with a simplified version.

Example 5.2. Suppose that λ ≥ 1 and that E_{0}, …, E_{k} are numbers such that

E_{j} ≥ E_{j}, 0 ≤ j ≤ k,  (5.2)
E_{j}/E_{j+1} ≥ λ, 0 ≤ j ≤ k − 1.  (5.3)

Take t = (λE_{0}E_{1})^{1/2}. Then t/μ = t/E′_{0} ≥ t/E_{0} by (5.2) and, by (5.3), t ≤ E_{0}; hence t lg(1 + t/μ) ≥ t lg(1 + t/E_{0}) ≥ t^{2}/E_{0} = λE_{1}. Consequently, using (5.1) together with (5.2) and (5.3) again,

\frac{t lg(1 + t/μ)}{μ_{j}} ≥ \frac{λE_{1}}{CE_{j}} ≥ C^{−1}λ^{j}.  (5.4)

Hence, Corollary 4.1 yields

ℙ(X ≥ μ + (λE_{0}E_{1})^{1/2}) ≤ 2N^{k−1}e^{−cλ}.  (5.5)

The result in (5.5) is useful when λ ≥ C ln N; then we can remove the factor N^{k−1}. For smaller λ, the same can be done with a stronger hypothesis.

Example 5.3. If we strengthen (5.3) to

E_{j}/E_{j+1} ≥ λ + j ln N,  0 ≤ j ≤ k − 1,  (5.6)

we see by (5.4) also

\frac{t lg(1 + t/μ)}{μ_{j}} ≥ \frac{λE_{1}}{CE_{j}} ≥ C^{−1}λ(ln N)^{j−1}.

Corollary 4.7 thus implies

ℙ(X ≥ μ + (λE_{0}E_{1})^{1/2}) ≤ 2e^{−cλ}.

This result yields the upper tail parts of Theorem 2.3 in [13] and of the case k̃ = k in Theorem 3.2 in [15]. In general, the upper tail part of the latter theorem follows by Corollary 4.9 (with ℓ = 1). Indeed, Vu [15] inspired both Theorem 3.13 and Corollaries 4.7–4.9.

The results discussed so far in this section all use, in our version, A = Γ as in Example 3.1. The more general setting in (H1) is inspired by Vu [14]. In particular, our Theorems 3.10 and 3.11 and the corresponding Corollaries 4.1 and 4.3, owe much to Theorems 2 and 1, respectively, in [14]. The upper tail parts of these theorems by Vu follow from our Corollaries 4.1 and 4.3 as shown below.

Example 5.4. Vu [14] studies the subgraph count X_{G} in 𝔾(n, p), where G is a fixed graph with k vertices; see Section 6 below where we do the same in detail. He defines F_{j} as the minimum of 𝔼 X_{H} over all subgraphs H of G with at least j vertices, and E_{j} := 𝔼(X_{G})/F_{j}. Thus E_{0} ≥ μ and E_{k} = 1.

Vu further studies the corresponding, more general, problem of counting extensions with a fixed set of roots; we denote this random number by X_{L}, where L is a given rooted graph with k non-root vertices. Vu defines M_{j} corresponding to, and generalizing, E_{j}; see [14] for details. Again, M_{0} ≥ μ and M_{k} = 1.

Note that the subgraph case is an instance of our Example 3.5 where (H2) holds, while the extension case is an instance of Example 3.8 where (H2) fails; thus we (and Vu) obtain better bounds for the subgraph case.

In the subgraph case, it is easily seen that μ_{j} ≤ CE_{j}, 0 ≤ j ≤ k, see (6.1) below; similarly, in the extension case μ_{j} ≤ CM_{j}.

In his Theorem 2, Vu [14] assumes that λ ≥ C ln n and M_{0}, …, M_{k} are numbers, with M_{k} = 1, such that

M_{j} ≥ M_{j}, j = 0, …, k,
M_{j}/M_{j+1} ≥ λ, j = 0, …, k − 1.

It then follows from Corollary 4.1, exactly as in Example 5.2 above, that

ℙ(X_{L} ≥ μ + (λM_{0}M_{1})^{1/2}) ≤ 2n^{k−1}e^{−c_{1}λ} ≤ e^{−cλ},

which is the upper tail part of Vu’s result.

In Theorem 1, for subgraphs, Vu [14] assumes, more weakly, that λ ≥ C ln n and E_{0}, E_{2}, …, E_{k} are numbers, with E_{k} = 1, such that

E_{j} ≥ E_{j},  j = 0, 2, …, k,
E_{j}/E_{j+1} ≥ λ, j = 2, …, k,
E_{0}/E_{2} ≥ λ.

Now take t = (λE_{0}E_{2})^{1/2}. Then, as in Example 5.2, t ≤ E_{0} and, for 2 ≤ j ≤ k,

\frac{t lg(1 + t/μ)}{μ_{j}} ≥ \frac{t^{2}/E_{0}}{CE_{j}} = \frac{λE_{2}}{CE_{j}} ≥ C^{−1}λ^{j−1}.

Corollary 4.3 yields

ℙ(X ≥ μ + (λE_{0}E_{2})^{1/2}) ≤ 2n^{k−1}e^{−c_{1}λ} ≤ e^{−cλ},

which is the upper tail part of Vu’s result.

Similarly, the upper tail part of Theorem 6 in [14] follows from our Corollary 4.4.

Corollaries 4.10–4.12 are inspired by and strongly related to results in Vu [12]; we have not been able to derive Theorem 1.3 in [12] by our method, but the upper tail parts of its corollaries Theorem 1.2 and Theorem 1.4 follow immediately from our Corollaries 4.11 and 4.12, respectively, together with Remark 4.13. Also Remark 3.15 is inspired by Vu [12].

6. Applications to random graphs

We give in this section several applications of the general results above to random graphs. In order to compare our method with the method of Kim and Vu, we mainly consider applications treated by Vu [12, 14, 15], and rederive several of his results. Many other applications from [6, 12, 14, 15] could be handled similarly. See further [5], where also other methods are considered.

Several of the arguments used below are similar to the arguments of Vu, but sometimes there are differences; we invite the reader to compare the details.

We denote the numbers of vertices and edges of a graph G by v(G) and e(G), respectively.

Let G be a fixed graph, and let X_{G} be the number of copies of G in the random graph 𝔾(n, p). As explained in Example 3.5, we have X_{G} = ∑_{I∈[Γ]^{k}} Y_{I}, where k = v(G) and Y_{I} is the number of copies of G in 𝔾(n, p) with vertex set I, so we are in the setting of Section 3. We have (for n ≥ k)

𝔼 X_{G} = \frac{k!}{aut(G)}\binom{n}{k}p^{e(G)} ≍ n^{k}p^{e(G)},

where aut(G) is the number of automorphisms of G and ≍ means that the quotient of the two sides is bounded from above and below by positive constants.

We split the contents of this section into two part according to how large the deviation t is.

Large deviations. Throughout this subsection we write t = εμ; the reader may concentrate on the typical case when ε is a constant, but the results cover also cases when ε depends on n. Corollary 4.3 yields the following estimate.

Theorem 6.1. For any graph G, there exists a constant c > 0 such that, for every ε > 0, n and p,

ℙ(X_{G} ≥ (1 + ε) 𝔼 X_{G})

≤ 2n^{v(G)−1} exp(−c min_{H⊆G:v(H)≥2}(lg(1 + ε)ε 𝔼 X_{H})^{1/(v(H)−1)}).

If further lg(1 + ε)ε 𝔼 X_{H} ≥ C ln^{v(H)−1} n for some large constant C and every H ⊆ G with v(H) ≥ 2, then

ℙ(X_{G} ≥ (1 + ε) 𝔼 X_{G}) ≤ exp(−c min_{H⊆G:v(H)≥2}(lg(1 + ε)ε 𝔼 X_{H})^{1/(v(H)−1)}).

Proof. The first estimate follows directly by Corollary 4.3, since if 1 ≤ j ≤ k = v(G), then

μ_{j} ≍ n^{k−j} max_{H⊆G, v(H)=j} p^{e(G)−e(H)} ≍ max_{H⊆G, v(H)=j} \frac{𝔼 X_{G}}{𝔼 X_{H}} .  (6.1)

The second follows (with a smaller c) since the exponent now is at least k log n. □

Recall that the graph G is said to be balanced if e(H)/v(H) ≤ e(G)/v(G) for every H ⊆ G, see [3].

Corollary 6.2. If G is a balanced graph, there exist constants c, C > 0 such that, for every ε > 0, n and p with min(ε^{2}, ε^{1/(v(G)−1)})(𝔼 X_{G})^{1/(v(G)−1)} ≥ C ln n,

ℙ(X_{G} ≥ (1 + ε) 𝔼 X_{G}) ≤ \begin{cases}exp(−cε^{2}(𝔼 X_{G})^{1/(v(G)−1)}), & ε ≤ 1, \\ exp(−c(ε 𝔼 X_{G})^{1/(v(G)−1)}), & ε ≥ 1. \end{cases}

Proof. Since G is balanced, (𝔼 X_{H})^{1/v(H)} ≍ np^{e(H)/v(H)} ≥ c_{1}(𝔼 X_{G})^{1/v(G)}. It follows a fortiori that (𝔼 X_{H})^{1/(v(H)−1)} ≥ c_{2}(𝔼 X_{G})^{1/(v(G)−1)} when ε ≤ 1 and thus 𝔼 X_{G} > 1, and (ε 𝔼 X_{H})^{1/(v(H)−1)} ≥ c_{2}(ε 𝔼 X_{G})^{1/(v(G)−1)} when ε ≥ 1 and thus ε 𝔼 X_{G} > 1. The result follows from the theorem. □

For balanced graphs (and ε bounded), we have obtained the same bound as Vu [14, Theorem 3], up to the values of the constants.

Moreover, Theorem 6.1 applies also to unbalanced graphs. Note that by the argument in the proof of Corollary 6.2, if ε is constant, it suffices to consider H = G and induced subgraphs H with density e(H)/v(H) > e(G)/v(G) when taking the minimum. Note further that the minimum may be attained for H = G also for an unbalanced G, at least for some ranges of p, so that we obtain the same estimate as for balanced graphs.

Example 6.3. Let G be K_{4} with a pendant edge added; we have v(G) = 5 and e(G) = 7. This graph is not balanced, since the subgraph K_{4} has density 6/4 > 7/5. All other proper induced subgraphs have density at most 1, and thus Theorem 6.1 yields for ε = 1, provided the exponent is at least C ln n,

ℙ(X_{G} ≥ 2 𝔼 X_{G}) ≤ exp(−c min(n^{5/4}p^{7/4}, n^{4/3}p^{2})).

In particular, in the range p ≥ n^{−1/3}, we obtain the same estimate exp(−cμ^{1/(v(G)−1)}) as for balanced graphs.

Vu [14] also gave a lower bound for the probability in Theorem 6.1. Let α^{∗}(G) denote the fractional independence number of G, i.e. the maximum of ∑_{v} a_{v} where a_{v}, v ∈ V (G), are non-negative numbers such that a_{v} + a_{w} ≤ 1 whenever v and w are two adjacent vertices. Vu [14] then showed that, provided μ ≥ 1 and p ≤ 1/2, say,

ℙ(X_{G} ≥ (1 + ε) 𝔼 X_{G}) ≥ exp(−C(ε, G)(𝔼 X_{G})^{1/α^{∗}(G)} ln(1/p)).  (6.2)

The proof of this bound is short and elementary. For instance, when G = K_{4}, when α^{∗}(G) = 2, consider the event that ⌈(24(1 + ε)μ)^{1/4}⌉ + 3 given vertices form a complete subgraph in 𝔾(n, p).

As observed by Vu [14], this lower bound shows that the estimate in Corollary 6.2 is sometimes sharp up to a logarithmic factor in the exponent; at least, this holds if G is a star. In general, however, the exact asymptotics are unknown, even ignoring such logarithmic factors.

Problem 6.4. What are the asymptotics of − ln ℙ(X_{G} ≥ (1 + ε) 𝔼 X_{G})?

When p is large, the bound of Theorem 6.1 is surpassed by a simple application of Corollary 2.8, which immediately yields the following.

Theorem 6.5. For any graph G, there exists a constant c > 0 such that, for every ε > 0, n and p,

ℙ(X_{G} ≥ (1 + ε) 𝔼 X_{G}) ≤ exp(−cε lg(1 + ε)n^{2}p^{e(G)}).  □

It is easily checked that for a constant ε, Corollary 6.2 and Theorem 6.5 both yield estimates exp(−c(ε)n) when p = n^{−1/e(G)}; for p ≫ n^{−1/e(G)} Theorem 6.5 is better than Corollary 6.2, and for p ≪ n^{−1/e(G)} Corollary 6.2 is the better.

We consider some examples, for simplicity taking ε = 1. Any constant ε ≤ 1 would give the same results with, at most, an extra factor ε^{2} in the exponent. In particular, we will see how close our results are to the lower bound (6.2).

Example 6.6. A simple example is G = K_{3}. This graph is balanced, and Corollary 6.2 immediately yields, assuming μ ≍ n^{3}p^{3} ≥ C ln^{2} n,

ℙ(X_{K_{3}} ≥ 2 𝔼 X_{K_{3}}) ≤ exp(−cμ^{1/2}) ≤ exp(−c′n^{3/2}p^{3/2}).  (6.3)

For p ≥ n^{−1/3}, it is better to use Theorem 6.5, which yields

ℙ(X_{K_{3}} ≥ 2 𝔼 X_{K_{3}}) ≤ exp(−cn^{2}p^{3}).

In this simple case, we can also use Theorem 2.4. Note that X_{{i,j}} ≤ Z, where Z is the number of common neighbours of i and j. (More precisely, X_{{i,j}} = Z if there is an edge between i and j, and X_{{i,j}} = 0 otherwise.) Z is a binomial random variable with mean ν := (n − 2)p^{2}, so we can use the Chernoff bound

ℙ(Z ≥ z) ≤ e^{−z}, z ≥ 7ν (6.4)

[3, Corollary 2.4]. Choosing t = μ and r = μ^{1/2} in Theorem 2.4, and applying (6.4) with z = t/6r, we again obtain (6.3).

We can improve this slightly, by using the sharper Chernoff bound

ℙ(Z ≥ z) ≤ exp(−z ln \frac{z}{eν} ),  (6.5)

again see [3, Corollary 2.4]. We choose t = μ, r = (μ ln μ)^{1/2} and z = t/6r = \frac{1}{6}μ^{1/2} ln^{−1/2} μ; then z/eν ≥ c_{1}μ^{1/6} ln^{−1/2} μ and thus ln(z/eν) ≥ c_{2} ln μ (for large n). Consequently, Theorem 2.4 and (6.5) yield, still assuming μ ≍ n^{3}p^{3} ≥ C ln^{2} n,

ℙ(X_{K_{3}} ≥ 2 𝔼 X_{K_{3}}) ≤ exp(−c(μ ln μ)^{1/2}) ≤ exp(−c′n^{3/2}p^{3/2} ln^{1/2}(np)). (6.6)

On the other hand, we have α^{∗}(K_{3}) = 3/2, and thus (6.2) yields, for μ ≥ 1, the lower bound

ℙ(X_{K_{3}} ≥ 2 𝔼 X_{K_{3}}) ≥ exp(−Cμ^{2/3} ln(1/p)) ≥ exp(−Cn^{2}p^{2} ln(1/p)),

which for p → 0 is not approached by any of the upper bounds above.

Example 6.7. Another example is G = K_{4}. This graph is balanced too. If we assume μ ≍ n^{4}p^{6} ≥ C ln^{3} n, Corollary 6.2 yields

ℙ(X_{K_{4}} ≥ 2 𝔼 X_{K_{4}}) ≤ exp(−cμ^{1/3}) ≤ exp(−c′n^{4/3}p^{2}),  (6.7)

while Theorem 6.5 yields

ℙ(X_{K_{4}} ≥ 2 𝔼 X_{K_{4}}) ≤ exp(−cn^{2}p^{6}),

which is better when p > n^{−1/6}.

For some p, we can do substantially better by using Theorem 2.4 and the following argument to estimate the term ℙ(X_{{i,j}} > t/12r).

Fix i and j, and let W be the number of subgraphs of 𝔾(n, p) on 4 vertices, including i and j, that are complete except possibly for the edge ij; such subgraphs are called extensions of type K_{4} with roots i and j. Each such extension thus contains, besides i and j, two other vertices that are common neighbours of i and j, and further are joined by an edge. Clearly, W ≥ X_{{i,j}} (W = X_{{i,j}} if i and j are adjacent, and W = 0 otherwise).

Expose first all edges in 𝔾(n, p) adjacent to i or j. Let, as in Example 6.6, Z ∼ Bi(n − 2, p^{2}) be the number of common vertices of i and j.

Then expose the remaining vertices. Conditioned on Z = z, there are \binom{z}{2} possible edges that would complete an extension of the above type, so W ∼ Bi(\binom{z}{2}, p).

Now, let t = μ and fix a large number a such that

\begin{aligned}a & ≥ 7np^{2}, \\ \frac{t}{12r} & ≥ 7\frac{a^{2}}{2} p. \end{aligned}  (6.8)

Then two applications of the Chernoff bound (6.4) and its analogue for W yield

ℙ(X_{{i,j}} > t/12r) ≤ ℙ(Z > a) + ℙ(W > t/12r, Z ≤ a)

≤ ℙ(Bi(n − 2, p^{2}) > a) + ℙ(Bi(\binom{⌊a⌋}{2}, p) > t/12r)

≤ e^{−a} + e^{−t/12r},

and consequently, by Theorem 2.4,

ℙ(X_{K_{4}} ≥ 2 𝔼 X_{K_{4}}) ≤ e^{−r} + n^{2}(e^{−a} + e^{−t/12r}).  (6.9)

We have to choose r and a so that (6.8) holds. If n^{2}p^{3} ≥ C ln n and np^{2} ≤ 1, we take a = n^{2}p^{3} and r = c_{1}n^{2}p^{3} for some small constant c_{1} > 0, and obtain

ℙ(X_{K_{4}} ≥ 2 𝔼 X_{K_{4}}) ≤ e^{−cn^{2}p^{3}}.  (6.10)

Actually, (6.10) holds for all p ≤ n^{−1/2}; the case n^{2}p^{3} ≤ C ln n and μ ≥ C_{1} follows from Corollary 4.10, cf. Theorem 6.9 below and its proof, and the case μ ≤ C_{1} is trivial by Markov’s inequality; we omit the details.

By Vu’s lower bound (6.2), we have (when 𝔼 X_{K_{4}} ≥ 1 and p ≤ 1/2)

ℙ(X_{K_{4}} ≥ 2 𝔼 X_{K_{4}}) ≥ e^{−c′n^{2}p^{3} ln n}.  (6.11)

Hence, in the case μ ≥ 1 and np^{2} ≤ 1, we have found upper and lower bounds (6.10) and (6.11) that differ only by a logarithmic factor in the exponent.

If p ≤ n^{−1/2−ε}, for some ε > 0, and μ ≥ C ln n, we can improve the upper bound by taking r = n^{2}p^{3} ln^{1/2} n instead and using (6.5) and its analogue for W. Since a/np^{2} = np > n^{1/3} and t/12ra^{2}p > c_{2}n^{ε}, this yields, instead of (6.9),

ℙ(X_{K_{4}} ≥ 2 𝔼 X_{K_{4}}) ≤ e^{−r} + n^{2}(e^{−c_{3}a ln n} + e^{−c_{4}ε(ln n)t/12r})

and thus

ℙ(X_{K_{4}} ≥ 2 𝔼 X_{K_{4}}) ≤ e^{−c(ε)n^{2}p^{3} ln^{1/2} n},  (6.12)

getting even closer to the lower bound (6.2).

If np^{2} ≥ 1, the above choice of a and r is not allowed. Instead we take a = r = c_{1}n^{4/3}p^{5/3} for a small c_{1} > 0 and find from (6.9)

ℙ(X_{K_{4}} ≥ 2 𝔼 X_{K_{4}}) ≤ e^{−cn^{4/3}p^{5/3}},  (6.13)

which improves (6.7). It is still an open problem to find the correct asymptotics in this range of p.

Note that the probabilities of large deviations that we have found for the upper tail when np^{2} ≤ 1 are small but much larger than the corresponding results for the lower tail: for any ε with 0 < ε ≤ 1, ℙ(X_{K_{4}} ≤ (1 − ε) 𝔼 X_{K_{4}}) ≤ e^{−cε^{2}μ}, see [3, Theorems 3.9 and 2.14]. This should not be surprising; a comparatively small number of clustered extra edges can create a large number of copies of K_{4}, see the argument after (6.2), but there is no comparable simple way to get substantially fewer copies than expected.

It is surprising that we are able to find (almost) the precise asymptotics for K_{4}, at least for some range of p, but not for the simpler case K_{3}.

The proof of Theorem 6.1 and Corollary 6.2, is, as the corresponding argument in [14], based on an inductive argument, adding one vertex at a time. (To be precise, the induction is for the more general problem of counting extensions, cf. the proof of Theorem 3.11.) The argument above yielding a better bound for K_{4} suggests that it may for other graphs too be better to use another induction scheme, adding several vertices (or edges) each time according to some kind of “shell decompostion” of the graph, but we leave this possibility for future research.

Note that applying Corollary 4.1 with Γ the set of edges of K_{n} as in Example 3.3, i.e. adding one edge at a time (“edge exposure”), generally gives inferior results, even if we may improve them somewhat by using Corollary 4.5 with, for example, k_{0} = k +1−δ(G), where δ(G) denotes the minimum degree. With this k_{0}, M_{k_{0}} ≤ C since this many edges determine the vertex set, and M_{k_{0}} is just the number of ways the remaining edges may be added to create a copy of G.

Small deviations. For small deviations t, i.e. for small ε, the estimate in Theorem 6.1 is useless because of the factor n^{v(G)−1}. We give some complementary results for small t; for simplicity we treat only some cases where we obtain bounds of the sub-Gaussian type ℙ(X_{G} ≥ μ + t) ≤ exp(−ct^{2}/ Var X_{G}). Note that as soon as ℙ(X_{G} = 0) → 0 and n^{2}(1−p) → ∞, X_{G} is asymptotically normally distributed [9], [3, Theorem 6.5], and thus an estimate of this type holds if t/(Var X_{G})^{1/2} is fixed, and by a continuity argument if this quantity is slowly increasing too; the problem is to find explicit ranges of t where this is true. Therefore, in this subsection, we write σ^{2} := Var X_{G} and, instead of writing t = εμ, we compare t to the standard deviation σ. Theorem 6.8 below slightly extends the upper tail parts of results by Vu [14, Corollary 2], [15, Corollary 6.4].

To avoid trivialities, we assume e(G) > 0 and p ≤ 1/2. We begin by observing that then

σ^{2} = Var X_{G} ≍ max_{H⊆G, v(H)≥2} \frac{(𝔼 X_{G})^{2}}{𝔼 X_{H}} ≍ max_{2≤j≤k} μμ_{j},  (6.14)

see [3, Lemma 3.5] and (6.1). We say that H is a leading overlap if it attains the maximum in (6.14), i.e. if 𝔼 X_{H} is minimal, at least within a constant factor. (Formally this makes sense only if we let n → ∞ and consider some given p = p(n).) See [3, Section 3.2] for further information.

If e(G) ≥ 2 we define

m^{(2)}(G) := max\{\frac{e(H) − 1}{v(H) − 2} : H ⊆ G with v(H) ≥ 3\};

in the trivial case e(G) = 1 we set m^{(2)}(G) := 1/2. Thus, if H ⊆ G with v(H) ≥ 2, then

𝔼 X_{H} ≍ n^{v(H)}p^{e(H)} ≥ n^{2}p(np^{m^{(2)}(G)})^{v(H)−2}.  (6.15)

Note that m^{(2)}(G) ≥ 1/2 for every G with e(G) > 0.

The significance of m^{(2)}(G) comes partly from the fact that if np^{m^{(2)}(G)} ≥ 1, then (6.14) and (6.15) imply that K_{2} is a leading overlap, i.e.

σ^{2} = Var X_{G} ≍ \frac{(𝔼 X_{G})^{2}}{𝔼 X_{K_{2}}} ≍ \frac{(𝔼 X_{G})^{2}}{n^{2}p} .  (6.16)

Theorem 6.8. For any graph G, there exist constants c, C > 0 such that, for every n and p ≤ 1/2 with np^{m^{(2)}(G)} ≥ ln n and for every t with C ≤ t/σ ≤ (np^{m^{(2)}(G)})^{1/2},

ℙ(X_{G} ≥ μ + t) ≤ exp(−ct^{2}/σ^{2}).

Proof. Write ω = np^{m^{(2)}(G)}. Since m^{(2)}(G) ≥ 1/2, we have ω ≤ ω^{2} ≤ n^{2}p, and thus, using (6.16),

t^{2} ≤ ωσ^{2} ≤ n^{2}pσ^{2} ≤ C_{1}μ^{2}.  (6.17)

By (6.1) and (6.15), for 2 ≤ j ≤ k,

μ_{j} ≤ C_{2} \frac{𝔼 X_{G}}{n^{2}p ω^{j−2}}

and thus, by (6.17) and (6.16),

\frac{t lg(1 + t/μ)}{μ_{j}} ≥ c_{1} \frac{t^{2}}{μμ_{j}} ≥ c_{2} \frac{t^{2}n^{2}p ω^{j−2}}{(𝔼 X_{G})^{2}} ≥ c_{3} \frac{t^{2}}{σ^{2}} ω^{j−2}.

By the assumptions, this is at least c_{3}(t^{2}/σ^{2})^{j−1}, and also at least c_{3}(t^{2}/σ^{2}) ln^{j−2} n, and the result follows by Corollary 4.8 with ℓ = 2. □

Theorem 6.8 requires that p is so large that K_{2} is the only leading overlap. Another result by Vu [12, Corollary 5.1] yields a similar bound in the opposite extreme case, viz. when p is small and G itself is the only leading overlap; it is further assumed that G is strictly balanced, i.e. e(H)/v(H) < e(G)/v(G) for every proper subgraph H. We state his result as follows.

Theorem 6.9. Suppose that G is a strictly balanced graph. Then there exists a constant c > 0 such that if μ := 𝔼 X_{G} ≤ ln n and 0 < t ≤ μ, then

ℙ(X_{G} ≥ μ + t) ≤ 2e^{−c_{1}t^{2}/μ} ≤ 2e^{−c_{2}t^{2}/σ^{2}}.

Proof. The assumptions on G and μ imply that for every subgraph H ⊂ G with 1 ≤ v(H) < k = v(G), and some α > 0, we have 𝔼 X_{H} ≥ n^{α} 𝔼 X_{G} (for large n, at least). By (6.1), μ_{j} = O(n^{−α}) for 1 ≤ j ≤ k − 1, while μ_{k} ≤ C for some C, and the first inequality follows by Corollary 4.12 (applied to X_{G}/C). The second follows because σ^{2} ≍ μ by (6.14). (In this case, actually σ^{2} ∼ μ.) □

The lower bound (6.11) shows that the result does not extend to μ ≫ ln^{2} n; we do not know whether μ = O(ln n) is necessary.

We can obtain a similar estimate also in intermediate cases when some other subgraph is the only leading overlap, or when there are several leading overlaps but all have the same number of vertices.

Theorem 6.10. Suppose that G is a graph and that p ≤ 1/2 is such that there exists a subgraph F ⊆ G and a number γ > 0 with 𝔼 X_{H} ≥ n^{γ} 𝔼 X_{F} for every subgraph H ⊆ G with v(H) ≥ 2 and v(H) ≠ v(F). Then there is a constant c = c(G, γ) such that if 0 < t/σ ≤ (ln n)^{1/2} and t ≤ μ, then

ℙ(X_{G} ≥ μ + t) ≤ 2e^{−ct^{2}/σ^{2}}.

Proof. Let f = v(F) and k = v(G). By assumption and (6.1),

μ_{j} ≤ Cn^{−γ}μ_{f},  2 ≤ j ≤ k and j ≠ f.  (6.18)

Moreover, by (6.14), σ^{2} ≍ μμ_{f}.

Let A be a large constant and apply Theorem 3.11 with r_{2} = A^{−k}t/μ_{f}, r_{3}, …, r_{f} = A and r_{f+1}, …, r_{k} = An^{γ/k}. Using (6.18), it is easy to first verify (3.8) and then from (3.9) and (6.14) obtain

\begin{aligned}ℙ(X_{G} ≥ μ + t) & ≤ e^{−c_{1}A^{−k}t^{2}/μμ_{f}} + ∑_{j=2}^{f−1} n^{j}(\frac{Aμ_{f}}{μ_{j}} )^{−cA} + ∑_{j=f}^{k−1} n^{j}2^{−cAn^{γ/k}} \\ & ≤ e^{−c_{2}A^{−k}t^{2}/σ^{2}} + n^{f−cAγ} + n^{k}2^{−cAn^{γ/k}}. \end{aligned}

The result follows by choosing A large enough (depending on γ and k). □

Problem 6.11. Can the range of t in Theorem 6.10 be extended?

If we consider the special case p = n^{−α} for some fixed α, the assumptions of Theorem 6.10 are satisfied (for large n, at least) for all but a finite number of α; the exceptions are when there exist two leading overlaps with different numbers of vertices; cf. [3, Section 3.2]. We obtain the following corollary.

Corollary 6.12. For any graph G and every α > 0 except for a finite number of values (depending on G), there is a constant c = c(G, α) such that if p = n^{−α}, 0 < t/σ ≤ (ln n)^{1/2} and t ≤ μ, then

ℙ(X_{G} ≥ μ + t) ≤ 2e^{−ct^{2}/σ^{2}}.  □

The exceptional case when there are two leading overlaps with different numbers of vertices is more complicated; under suitable hypotheses it is still possible to obtain bounds from (2.4), but they will be weaker than in the theorems above.

Problem 6.13. Does Corollary 6.12 extend to all α?

We give here only a simple counterexample which shows that Theorem 6.9 does not extend to arbitrary balanced graphs.

Example 6.14. Let G consist of a triangle with 3 pendant edges attached to the same vertex of the triangle. (Equivalently, G is a star K_{1,5} with an added edge.) Further, let np tend to ∞ very slowly, for example p = ln ln n/n. For convenience we assume that n is even and large.

We have μ := 𝔼 X_{G} ∼ \frac{1}{12}(np)^{6} and σ^{2} := Var X_{G} ≍ \frac{μ^{2}}{(np)^{3}} ≍ (np)^{9} (K_{3} is a leading overlap). Let t = (np)^{11/2}; thus t/σ ≍ np → ∞ but t ≪ μ.

Expose the edges in two rounds, cf. [3, Section 1.1]: first select red edges with probabilities p_{1} = p(1−(np)^{−3/2}) and then, independently, blue edges with probabilities p_{2} = (p − p_{1})/(1 − p_{1}) > p(np)^{−3/2}; this makes p_{1} + p_{2} − p_{1}p_{2} = p and thus we obtain 𝔾(n, p) by ignoring colours and possible double edges.

Let X′_{G} be the number of red copies of G, and let X′′_{G} be the number of copies with at least one blue edge. We have 𝔼 X′_{G} = (p_{1}/p)^{6}μ = μ + O(σ) and Var X′_{G} ∼ Var X_{G} = σ^{2}. Hence, by Chebyshev’s inequality (or [9]), ℙ(X′_{G} > μ − t) → 1.

Suppose that X′_{G} > μ − t and select a vertex v in some red triangle. Let B be the number of blue edges adjacent to v, not counting those overlapping with a red edge; thus B ∼ Bi(n − 1 − d_{r}(v), p_{2}), where d_{r}(v) is the number of red neighbours of v. If B ≥ b := 3⌈t^{1/3}⌉, then X′′_{G} ≥ \binom{b}{3} > 2t and thus X_{G} = X′_{G} + X′′_{G} > μ + t. We may further suppose that d_{r}(v) < n/2, since otherwise X_{G} ≥ X′_{G} > \binom{n/2−2}{3} ≫ μ + t. Consequently, conditioned on a red graph with X′_{G} > μ − t,

ℙ(X_{G} > μ + t) ≥ ℙ(Bi(n/2, p_{2}) = b) ∼ \frac{1}{b!}(\frac{n}{2}p_{2})^{b} ≥ (\frac{np_{2}}{b} )^{b}
≥ exp(−c_{1}t^{1/3} ln t) = exp(−c_{2}(np)^{11/6} ln(np)).

Hence, unconditionally too, ℙ(X_{G} > μ + t) ≥ exp(−c_{2}(np)^{11/6} ln(np)), which is larger than e^{−ct^{2}/σ^{2}} ≤ e^{−c′(np)^{2}}.

Remark 6.15. The arguments and results in this section apply to counts of induced subgraphs too; note that our method does not require the summands Y_{I} to be increasing functions of the underlying variables ξ_{α}.

7. Appendix: The lower tail

As remarked in the introduction, estimates for the lower tail can be derived by other inequalities. In particular, we give here a new version of Suen’s inequality that applies in the setting of Theorem 2.1. It is a slight extension of [3, Theorem 2.23], where it is assumed that the Y_{α} are indicator random variables (as is usually the case in applications). (Suen’s original inequality [11] deals only with ℙ(X = 0); see also [2, 10] for further related results.)

Note that the inequality in [3, Theorem 2.14] is slightly stronger when applicable (although the difference usually is insignificant), but it applies only under more restrictive assumptions.

Theorem 7.1. Suppose that Y_{α}, α ∈ A, is a finite family of non-negative random variables and that ∼ is a symmetric relation on the index set A such that if A, B are two subsets of A such that α ≁ β for α ∈ A, β ∈ B, then the family {Y_{α} : α ∈ A} is independent of {Y_{β} : β ∈ B}; in other words, the pairs (α, β) with α ∼ β and α ≠ β define the edge set of a strong dependency graph for the variables Y_{α}. Let X := ∑_{α} Y_{α} and μ := 𝔼 X = ∑_{α} 𝔼 Y_{α}. Let further, for α ∈ A, X̃_{α} := ∑_{β∼α} Y_{β} and let Δ̄ := ∑ ∑_{α∼β} 𝔼(Y_{α}Y_{β}) = ∑_{α} 𝔼(X̃_{α}Y_{α}) and δ := max_{α} 𝔼 X̃_{α}. If 0 ≤ t ≤ μ, then

ℙ(X ≤ μ − t) ≤ exp(− min(\frac{t^{2}}{4Δ̄}, \frac{t}{6δ} )).  (7.1)

Proof. The proof in [3, Theorem 2.23] holds with only notational changes (replace I_{i} by Y_{α} and p_{i} by 𝔼 Y_{α}), since, for any X_{A} ≥ 0,

(Y_{α} − 𝔼 Y_{α})(1 − e^{−sX_{A}}) ≤ Y_{α}(1 − e^{−sX_{A}}) ≤ Y_{α}sX_{A}.

We omit the details. □

In the situation studied in Section 3, we derive the following corollary, which in many cases yields a stronger bound for the lower tail than the upper tail estimate in Corollary 4.1. (For t = O(μ), the bound is always at least as strong as (4.1) up to a constant factor in the exponent; typically, it is much stronger.)

Corollary 7.2. Assume (H1). With notation as in Section 3, and c = 2^{−k−2}, for 0 ≤ t ≤ μ,

ℙ(X ≤ μ − t) ≤ exp(−c min( min_{1≤j≤k}(\frac{t^{2}}{μμ_{j}} ), \frac{t}{μ_{1}} )).  (7.2)

Proof. In this case, cf. the proof of Theorem 2.3,

δ = max_{I} 𝔼 ∑_{J∩I≠∅} Y_{J} ≤ max_{I} 𝔼 ∑_{i∈I} X_{{i}} ≤ kμ_{1}.  (7.3)

Moreover, given I, let for every non-empty J ⊆ I, X_{J}^{∗} := ∑_{K∩I=J} Y_{K} ≤ X_{J}. Conditioned on {ξ_{α}, α ∈ A_{J}}, the random variables Y_{I} and X_{J}^{∗} are independent, as a consequence of (H1). Hence, using (3.1),

\begin{aligned}𝔼(Y_{I}X_{J}^{∗} | ξ_{α}, α ∈ A_{J}) & = 𝔼(Y_{I} | ξ_{α}, α ∈ A_{J}) 𝔼(X_{J}^{∗} | ξ_{α}, α ∈ A_{J}) \\ & ≤ 𝔼(Y_{I} | ξ_{α}, α ∈ A_{J})μ_{J}. \end{aligned}  (7.4)

and consequently 𝔼(Y_{I}X_{J}^{∗}) ≤ 𝔼 Y_{I}μ_{J}. Hence,

𝔼(Y_{I} X̃_{I}) = ∑_{∅≠J⊆I} 𝔼(Y_{I}X_{J}^{∗}) ≤ ∑_{∅≠J⊆I} 𝔼 Y_{I}μ_{J} ≤ 𝔼 Y_{I} ∑_{j=1}^{k} \binom{k}{j}μ_{j}

and

Δ̄ = ∑_{I} 𝔼(Y_{I} X̃_{I}) ≤ μ ∑_{j=1}^{k} \binom{k}{j}μ_{j} ≤ 2^{k}μ max_{1≤j≤k} μ_{j}.  (7.5)

The result follows form Theorem 7.1, (7.3) and (7.5). □

Remark 7.3. We have throughout assumed that our summands Y_{I} be nonnegative. In cases where the sign of Y_{I} may change, one may separate the positive and negative parts of Y_{I} and treat them separately, using a result from Section 2 or 3 for one part and Theorem 7.1 or Corollary 7.2 for the other.

Acknowledgement. This research was partly done during visits of the younger author to Uppsala and of both authors to the Department of Computer Science at Lund University; we thank Andrzej Lingas for providing the latter opportunity. We further thank Van Vu for sending us unpublished preprints and drafts.

References

[1] S. Janson, Poisson approximation for large deviations. Random Struct. Alg. 1 (1990), 221–230.

[2] S. Janson, New versions of Suen’s correlation inequality. Random Struct. Alg. 13 (1998), 467–483.

[3] S. Janson, T. Łuczak & A. Ruciński, Random Graphs. Wiley, New York, 2000.

[4] S. Janson & K. Nowicki, The asymptotic distribution of generalized U-statistics with applications to random graphs. Probab. Th. Rel. Fields 90 (1991), 341-375.

[5] S. Janson & A. Ruciński, The infamous upper tail. In preparation.

[6] J.H. Kim & V.H. Vu, Concentration of multivariate polynomials and applications. Combinatorica 20 (2000), 417–434.

[7] V. Rödl & A. Ruciński, Random graphs with monochromatic triangles in every edge coloring. Random Struct. Alg. 5:2 (1994), 253–270.

[8] V. Rödl & A. Ruciński, Threshold functions for Ramsey properties. J. Amer. Math. Soc. 8:4 (1995), 917–942.

[9] A. Ruciński, When are small subgraphs of a random graph normally distributed? Probab. Th. Rel. Fields 78 (1988), 1–10.

[10] J. Spencer, A useful elementary correlation inequality, II. J. Combin. Th. A 84 (1998), 95–98.

[11] W.C.S. Suen, A correlation inequality and a Poisson limit theorem for nonoverlapping balanced subgraphs of a random graph. Random Struct. Alg. 1 (1990), 231–242.

[12] V.H. Vu, On the concentration of multivariate polynomials with small expectation. Random Struct. Alg. 16:4 (2000), 344-363.

[13] V.H. Vu, New bounds on nearly perfect matchings in hypergraphs: higher codegrees do help. Random Struct. Alg. 17:1 (2000), 29-63.

[14] V.H. Vu, A large deviation result on the number of small subgraphs of a random graph. Technical report MSR-TR-99-90. To appear in Combin. Probab. Comput.

[15] V.H. Vu, Concentration of non-Lipschitz functions and applications. Preprint, 2000.

Department of Mathematics, Uppsala University, PO Box 480, S-751 06 Uppsala, Sweden

E-mail address: svante.janson@math.uu.se

Department of Discrete Mathematics, Adam Mickiewicz Universiy, Poznań, Poland

E-mail address: rucinski@amu.edu.pl