The Infamous Upper Tail ^{∗}

Svante Janson Uppsala University Sweden

Andrzej Ruciński^{†} A. Mickiewicz University Poznań, Poland

May 28, 2001; revised November 19, 2001

Abstract

Let Γ be a finite index set and k ≥ 1 a given integer. Let further S ⊆ [Γ]^{≤k} be an arbitrary family of k element subsets of Γ. Consider a (binomial) random subset Γ_{p} of Γ, where p = (p_{i} : i ∈ Γ) and a random variable X counting the elements of S that are contained in this random subset.

In this paper we survey techniques of obtaining upper bounds on the upper tail probabilities ℙ(X ≥ λ + t) for t > 0. Seven techniques, ranging from Azuma’s inequality to the purely combinatorial deletion method, are described, illustrated and compared against each other for a couple of typical applications.

As one application, we obtain essentially optimal bounds for the upper tails for the numbers of subgraphs isomorphic to K_{4} or C_{4} in a random graph G(n, p), for certain ranges of p.

1 Introduction

Let Γ be a finite index set and k ≥ 1 a given number, and let [Γ]^{≤k} be the family of all subsets

A ⊆ Γ with |A| ≤ k. Suppose that I_{A}, A ∈ [Γ]^{≤k}, is a family of non-negative random variables such

that each I_{A} is independent of {I_{B} : B ∩ A = ∅}. Let X := ∑_{A} I_{A} and λ := 𝔼 X = ∑_{A} 𝔼 I_{A}.

In this paper we survey techniques of obtaining upper bounds on the upper tail probabilities

ℙ(X ≥ λ + t) for t > 0. In many instances such inequalities come together with their lower

tail counterparts as a two-sided concentration result. This is the case of celebrated Azuma’s and

Talagrand’s inequalities (see next section). The simplest situation takes place when k = 1. Then

X is a sum of independent summands, and if these happen to be 0–1 random variables, Chernoff’s bounds apply. With ϕ(x) = (1 + x) log(1 + x) − x, x ≥ −1 (and ϕ(x) = ∞ for x < −1), we have, see e.g. [1], [7] and [9, Theorem 2.8]

∗This is a preprint of an article accepted for publication in Random Structure & Algoritms \begin{matrix}c \\ ◯ \end{matrix} 2002 John Wiley & Sons, Inc.

†Supported by KBN grant 2 P03A 032 16

ℙ(X ≥ λ + t) ≤ exp(−λϕ(\frac{t}{λ})) ≤ exp(−\frac{t^{2}}{2(λ + t/3)}),  t ≥ 0;  (1)
ℙ(X ≤ λ − t) ≤ exp(−λϕ(\frac{−t}{λ})) ≤ exp(−\frac{t^{2}}{2λ}),  t ≥ 0.  (2)

There is a little asymmetry between the lower and upper tail, but for t ≤ λ the order of magnitude of the exponents is the same.

For arbitrary k, a special case of our general framework can be described as follows. Suppose that ξ_{i}, i ∈ Γ, is a family of independent 0–1 random variables, and that I_{A} = ∏_{i∈A} ξ_{i} when A ∈ S for a given family S ⊆ [Γ]^{≤k}, while I_{A} = 0 when A ∉ S. In other words, the indicator random variables ξ_{i} describe a (binomial) random subset Γ_{p} of Γ, where p = (p_{i} : i ∈ Γ), p_{i} = ℙ(ξ_{i} = 1) [we write Γ_{p} if p_{i} = p for all i], and X is the number of elements of S that are contained in this random subset. For the lower tail of the distribution of X, the following analogue of the Chernoff bound holds [8], [9, Theorem 2.14].

Theorem 0. Let X = ∑_{A∈S} I_{A} as above, and let λ = 𝔼 X = ∑_{A} 𝔼 I_{A} and Δ̄ = ∑ ∑_{A∩B≠∅} 𝔼(I_{A}I_{B}). Then, with ϕ(x) = (1 + x) log(1 + x) − x, for 0 ≤ t ≤ λ,

ℙ(X ≤ λ − t) ≤ exp (−\frac{ϕ(−t/λ)λ^{2}}{Δ̄} ) ≤ exp (−\frac{t^{2}}{2Δ̄}) .

It follows from the FKG inequality (see for example [9]) that the above bound is tight: if t = λ, Δ̄ − λ = o(λ) and max p_{i} = o(1), then

ℙ(X = 0) = exp{−λ(1 + o(1))}.

However, an upper tail analogue cannot be true in general. One slightly artificial counterexample is presented in [9, Remark 2.17]. A more natural one is the following from [20] (here slightly adapted).

(Counter)Example. Let Γ = [n]^{2}, k = 3, and S be the family of the edge sets of all triangles in K_{n}, the complete graph on [n]. Furthermore, let p_{i} = p = p(n) for all i ∈ [n]^{2}. Then X is simply the number of triangles in the random graph G(n, p). Assuming \frac{log n}{n} ≪ p = o(1), fix three disjoint subsets of vertices, each of order v = (2λ)^{1/3}, where recall λ = 𝔼 X. Then with probability p^{3v^{2}} there is a complete tripartite subgraph on the three sets, yielding v^{3} = 2λ triangles in G(n, p), and thus

− log ℙ(X ≥ 2λ) ≤ 3v^{2} log \frac{1}{p} ≤ 3(2λ)^{2/3} log n ≪ λ

so ℙ(X ≥ 2λ) ≫ e^{−cλ} for every c > 0.

In the next section we present several techniques of obtaining exponential bounds on the upper tail of X. Then, in the last section we illustrate them by a few examples and based on these examples, we compare them against each other. For X being the number of copies of K_{4} in a random graph G(n, p), one of our methods yields in a range of p an optimal bound, that means a bound which up to a logarithmic factor in the exponent matches the lower bound obtained by Vu’s (counter)example. For the number of copies of C_{4}, two of the methods yield an optimal bound for certain ranges of p.

We use c_{k} to denote various positive constants depending on k only.

This paper is meant to be an extension of Section 2.6 of [9]. We hope that the examples treated here can serve as inspiration and suggestions for future applications of the methods.

2 Methods

2.1 Inequalities based on Lipschitz condition

The first method is a version of Azuma’s inequality [7] tailored for combinatorial applications, see e.g. [12], [13] and [9, Remark 2.28].

Theorem 1. Let Z_{1}, …, Z_{M} be independent random variables, with Z_{j} taking values in a set Λ_{j}. Assume that a function f : Λ_{1} × Λ_{2} × ⋯ × Λ_{M} → ℝ satisfies, for some constants b_{j}, j = 1, …, M, the following Lipschitz condition:

(L) If two vectors z, z′ ∈ Λ_{1}×Λ_{2}×⋯×Λ_{M} differ only in the jth coordinate, then |f(z)−f(z′)| ≤ b_{j}.

Then, the random variable X = f(Z_{1}, …, Z_{M}) satisfies, for any t ≥ 0,

ℙ(X ≥ λ + t) ≤ exp{−2t^{2}/ ∑_{1}^{M} b_{j}^{2}},  (3)
ℙ(X ≤ λ − t) ≤ exp{−2t^{2}/ ∑_{1}^{M} b_{j}^{2}}.  (4)

Returning to the random set Γ_{p}, one typically defines the random variables Z_{j} via the random indicators ξ_{i}, i ∈ Γ. Given a partition A_{1}, …, A_{M} of Γ, each Z_{j} is then taken as the random vector (ξ_{i} : i ∈ A_{j}) ∈ {0, 1}^{A_{j}}, and for a given function f : 2^{Γ} → ℝ, the Lipschitz condition (L) in Theorem 1 is equivalent to saying that for any two subsets A, B ⊆ Γ, |f(A) − f(B)| ≤ b_{j} whenever the symmetric difference of the sets A and B is contained in A_{j}.

When Γ = [n]^{2} and so Γ_{p} = G(n, p), there are two common choices of the partition [n]^{2} = A_{1} ∪ ⋯ ∪ A_{M}. The vertex exposure martingale corresponds to the choice M = n and A_{j} = [j]^{2} \ [j − 1]^{2}. The edge exposure martingale is one in which M = \binom{n}{2} and |A_{j}| = 1 for each j. E.g., with b_{j} = 1, edge exposure is applicable provided the random variable X changes by at most 1 if a single edge is added or deleted, while vertex exposure is applicable provided X changes by at most 1 if any number of edges incident to a single vertex are added and/or deleted.

Talagrand [17] found another method that yields similar results. A combinatorial version of the Talagrand inequality requires, besides the Lipschitz condition, one more, quite technical condition, but in return it yields very often stronger bounds than Azuma’s inequality. (For proof, see e.g. [17] or [9, Theorem 2.29].) Theorem 2 (Talagrand). Let Z_{1}, …, Z_{M} be independent random variables, with Z_{j} taking values in a set Λ_{j}. Assume that a function f : Λ_{1} × Λ_{2} × ⋯ × Λ_{M} → ℝ satisfies, for some constants b_{j}, j = 1, …, M, and some function ψ, the following two conditions:

(L) If two vectors z, z′ ∈ Λ_{1}, …, Λ_{M} differ only in the jth coordinate, then |f(z) − f(z′)| ≤ b_{j}.

(C) If z ∈ Λ and r ∈ ℝ with f(z) ≥ r, then there exists a set J ⊆ {1, …, M} with ∑_{j∈J} b_{j}^{2} ≤ ψ(r), such that for all y ∈ Λ with y_{j} = z_{j} when j ∈ J, we have f(y) ≥ r.

Then, the random variable X = f(Z_{1}, …, Z_{M}) satisfies, for any r ∈ ℝ and t ≥ 0,

ℙ(X ≤ r − t) ℙ(X ≥ r) ≤ e^{−t^{2}/4ψ(r)}.  (5)

In particular, if m is a median of X, then for every t ≥ 0,

ℙ(X ≤ m − t) ≤ 2e^{−t^{2}/4ψ(m)}  (6)

and

ℙ(X ≥ m + t) ≤ 2e^{−t^{2}/4ψ(m+t)}.  (7)

Remark 1. A recent inequality of Boucheron, Lugosi and Massart [2] is sometimes an interesting alternative to Talagrand’s inequality; in several applications it yields essentially the same result (with better constants). We do not, however, see any way to use their inequality in the set-up treated here.

2.2 Kim–Vu concentration via average smoothness

Inequalities from the previous section become weaker when the Lipschitz coefficient are large. Kim and Vu in [11] developed a method yielding concentration bounds which depend only on the “average” Lipschitz coefficients, typically much smaller than the “worst-case” ones. Very recently Vu wrote an excellent expository paper on that method [21].

Their setup is less general than that of Azuma’s and Talagrand [though, still more general than that of Theorem 0]. Let X = X(ξ_{i} : i ∈ Γ = [N]) be a polynomial of degree k, where again ξ_{i} are independent random 0–1 variables. For a nonempty set A ∈ Γ^{[k]} let ∂_{A}X be the partial derivative of X with respect to the variables in A and define, for j = 0, …, k, 𝔼_{j}(X) = max_{|A|≥j} 𝔼(∂_{A}X). (Thus 𝔼_{0}(X) = 𝔼(X) = λ.)

We begin with the Main Theorem of [11], the first main theorem proved by this method.

Theorem 3A (Kim and Vu). For any ℓ ≥ 1, if λ ≥ 𝔼_{1}(X), then

ℙ (|X − λ| ≥ c_{k}ℓ^{k}\sqrt{λ 𝔼_{1}(X)}) ≤ exp\{−ℓ + (k − 1) log N\}.  (8)

The above theorem is derived from a more general, but more technical, concentration result, also proved in [11]. Let, for each i = 1, …, M,

E_{i} = | 𝔼(X|ξ_{1}, …, ξ_{i−1}, ξ_{i} = 1) − 𝔼(X|ξ_{1}, …, ξ_{i−1}, ξ_{i} = 0)|.

[Note that, as a conditional expectation, E_{i} is a random variable which is a function of (ξ_{1}, …, ξ_{i−1}).] Let further M = max_{i} E_{i}, W = ∑_{i} p_{i}E_{i} and V = ∑_{i} p_{i}q_{i}E_{i}^{2}.

Theorem 3B (Kim and Vu). Let a, v, ℓ be positive numbers such that 0 < ℓ < v/a^{2}. Then

ℙ (|X − λ| > \sqrt{ℓv}) < 2 exp\{−ℓ/4\} + ℙ(M > a or V > v)

≤ 2 exp{−ℓ/4} + ∑_{i} ℙ(E_{i} > a) + ℙ(W > v/a). (9)

These results have been developed further and successfully applied to a variety of problems by Kim and Vu, see for example [11, 18, 19, 20] and the survey [21], where also further references are given. In particular, Vu [21, Corollary 3.4] has proved the following general and widely applicable result, using Theorem 3B and induction. For further similar results see [18, 21]. It is easily seen that Theorem 3C always yields at least as strong bounds as Theorem 3A; this is illustrated by the examples in Section 3.

Theorem 3C (Vu). Let E_{0} > E_{1} > ⋯ > E_{k} and ℓ be positive numbers such that E_{j} ≥ 𝔼_{j}(X), 0 ≤ j ≤ k, and E_{j}/E_{j+1} ≥ ℓ + j log n, 0 ≤ j ≤ k − 1. Then

ℙ (|X − λ| ≥ \sqrt{ℓE_{0}E_{1}}) ≤ C_{k} exp\{−c_{k}ℓ\}.  (10)

2.3 Combinatorial techniques

In this subsection we collect techniques that require only an elementary, combinatorial argument. We will be assuming throughout that all elements of S have the same size k, and that for all i, p_{i} = p for some 0 < p ≤ 1. Thus λ = 𝔼 X = |S|p^{k}. For convenience, the deviation parameter t will be expressed here in the form t = ρ 𝔼 X = ρλ, though ρ, in general, is not necessarily a constant, and we will for simplicity only consider the case 0 < ρ ≤ 1. Finally, set |Γ| = N.

2.3.1 Converting to the lower tail

Here we aim to convert an upper tail probability into a lower tail and then to apply Theorem 0. This approach works mainly for dense families S.

Theorem 4. Let k ≥ 1 be an integer, and assume that S ⊆ [Γ]^{k}, |S| = η\binom{N}{k}, 0 < η ≤ 1, 0 < p < 1 and 0 < ρ ≤ 1. Then there exists a constant c_{k} > 0, depending on k only, such that

ℙ(X ≥ (1 + ρ)λ) ≤ 2e^{−c_{k}ρ^{2}η^{2}Np}.

Proof. Set Z = |Γ_{p}|, S̄ = [Γ]^{k} \ S, and

X̄ = ∑_{A∈S̄} I_{A} = \binom{Z}{k} − X,

and choose δ = ρη/3k. Then, by Chernoff’s bound (1),

\begin{matrix}ℙ(X ≥ (1 + ρ)λ) = ℙ (X̄ ≤ \binom{Z}{k} − (1 + ρ)λ) \\ ≤ ℙ (X̄ ≤ \binom{(1 + δ)Np}{k} − (1 + ρ)λ) + e^{−δ^{2}Np/3}, \end{matrix}

Now, kδ ≤ 1/3 and thus

(1 + δ)^{k} < e^{kδ} < 1 + e^{1/3}kδ < 1 + \frac{1}{2}ρη.  (11)

Moreover, we may assume that (1 + ρ)λ ≤ |S|, since otherwise the probability in question is 0. Hence (1 + ρ)p^{k} ≤ 1, which in combination with (11) yields (1 + δ)^{k}p^{k} < 1, or (1 + δ)p < 1, and thus \binom{(1+δ)Np}{k} < (1 + δ)^{k}\binom{N}{k}p^{k}. Consequently, using (11) again,

\begin{matrix}ℙ (X̄ ≤ \binom{(1 + δ)Np}{k} − (1 + ρ)λ) ≤ ℙ (X̄ ≤ [(1 + δ)^{k} − η(1 + ρ)]\binom{N}{k}p^{k}) \\ ≤ ℙ (X̄ ≤ (1 − η − \frac{1}{2}ρη)\binom{N}{k}p^{k}) = ℙ (X̄ ≤ 𝔼 X̄ − \frac{1}{2}ρη\binom{N}{k}p^{k}) . \end{matrix}

In order to apply Theorem 0 to X̄, assume that Np ≥ 1 (otherwise the inequality is trivial if c_{k} ≤ log 2) and note that then the quantity Δ̄ corresponding to the family S̄ is smaller than kN^{2k−1}p^{2k−1}. Hence, by Theorem 0,

ℙ (X̄ ≤ 𝔼 X̄ − \frac{1}{2}ρη\binom{N}{k}p^{k}) ≤ exp (−\frac{(ρη\binom{N}{k}p^{k})^{2}}{8Δ̄} ) ≤ e^{−c′_{k}ρ^{2}η^{2}Np},

for some c′_{k}. The theorem follows with c_{k} = min(1/27k^{2}, c′_{k}).

2.3.2 Breaking into disjoint matchings

The underlying idea is to break the family S into disjoint subfamilies of disjoint sets, and apply Chernoff’s bound to one subfamily. Set L = L(S) for the standard dependency graph of the family of indicators {I_{A} : A ∈ S}, where an edge joins A and B if and only if A ∩ B ≠ ∅. Note that the maximum degree Δ(L) can be as large as |S| − 1. The following result has appeared in a slightly more complicated form in [14].

Theorem 5. Let t = λρ, where ρ > 0. Then

ℙ(X ≥ λ + t) ≤ (Δ(L) + 1) exp (−\frac{ρ^{2}λ}{4(Δ(L) + 1)(1 + ρ/3)}) .

Proof. A matching in S is a subfamily M ⊆ S consisting of pairwise disjoint sets.

By the well known Hajnal–Szemerédi Theorem [6], the vertex set of the graph L can be partitioned into Δ(L) + 1 independent sets, each of size equal to either ⌈|S|/(Δ(L) + 1)⌉ or ⌊|S|/(Δ(L) + 1)⌋. These sets correspond to matchings M_{i}, i = 1, …, Δ(L) + 1, in S. Note that for each i, |M_{i}| > |S|/2(Δ(L) + 1). If X ≥ λ + t, then, by simple averaging, there exists a matching M_{i} such that |[Γ_{p}]^{k} ∩ M_{i}| ≥ p^{k}|M_{i}| + t|M_{i}|/|S|. Since |[Γ_{p}]^{k} ∩ M_{i}| is a random variable with the binomial distribution Bi(|M_{i}|, p^{k}), we conclude by (1) that

ℙ(X ≥ λ + t) ≤ ∑_{i=1}^{Δ(L)+1} exp (−\frac{t^{2}|M_{i}|}{2|S|(λ + t/3)})

≤ (Δ(L) + 1) exp (−\frac{t^{2}}{4(Δ(L) + 1)(λ + t/3)}) .

As our later examples show, Theorem 5 can be applied to quite sparse families S.

2.3.3 The deletion method

The next idea for establishing a bound on the upper tail of X resembles the tactic of sweeping under the rug. We delete some elements of Γ_{p} and claim the concentration of X in the remainder. Originally, this approach was used in the context of partition properties of random graphs [15]. Recently, it was developed further in [10], where it is shown to often yield essentially the same results as the method of Section 2.2.

Lemma 1. Let S ⊆ [Γ]^{k} and 0 < p < 1. Then, for every pair of positive real numbers r and t, with probability at least 1 − exp (−\frac{rt}{k(λ+t)}), there exists a set E_{0} ⊂ Γ_{p} of size r such that Γ_{p} \ E_{0} contains fewer than λ + t sets from S.

Proof. Given r and t, let A be the event that for each set E ⊂ Γ_{p} of size r, Γ_{p} \ E contains at least λ+t sets from S. Let Z be the number of κ = ⌈r/k⌉-element sequences of disjoint sets from S in Γ_{p}. If the event A holds, then Z ≥ (λ + t)^{κ}, since we may choose κ elements sequentially with at least λ + t choices each time. On the other hand, 𝔼(Z) ≤ |S|^{κ}p^{kκ} = λ^{κ} and thus, by Markov’s inequality,

ℙ(A) ≤ ℙ(Z ≥ (λ + t)^{κ}) ≤ \frac{𝔼(Z)}{(λ + t)^{κ}} ≤ (\frac{λ}{λ + t})^{r/k} ≤ exp(−\frac{rt}{k(λ + t)}).

In subsection 3.3 we show a direct application of Lemma 1. Now we derive from it a genuine bound on the upper tail of X in terms of the maximum degree in the subhypergraph S_{p} = S ∩ [Γ_{p}]^{k}. Let, for I ⊂ Γ, Y_{I} := ∑_{J⊇I} X_{J} and

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

Clearly, Y_{1}^{∗} = Δ(S_{p}) and there are at most rY_{1}^{∗} elements of S_{p} which could have been destroyed by removing r elements from Γ_{p}. Theorem 6A. Let t = ρλ, 0 < ρ ≤ 1. Then, for every real r > 0,

ℙ(X ≥ λ + t) ≤ exp{−ρr/3k} + ℙ(Y_{1}^{∗} > t/2r).

Proof. If X ≥ λ + t and Y_{1}^{∗} ≤ t/2r then for every set E ⊂ Γ_{p} with |E| ≤ r, Γ_{p} \ E contains at least

X − rY_{1}^{∗} ≥ λ + t/2

sets from S. By Lemma 1 the probability of the latter event is at most

exp (−\frac{rt/2}{k(λ + t/2)}) ≤ exp\{−ρr/3k\}.

The probability ℙ(Y_{1}^{∗} > t/2r) can be annihilated by choosing r = \frac{t}{2Δ(S)}. This gives as a corollary a bound in terms of maximum degree in S. Theorem 6B. Let t = ρλ, 0 < ρ ≤ 1. Then

ℙ(X ≥ λ + t) ≤ exp{−ρ^{2}λ/(6kΔ(S))}.

Since Δ(S) − 1 ≤ Δ(L(S)) ≤ kΔ(S), this theorem yields almost the same bound as Theorem 5.

Alternatively, one can bound ℙ(Y_{1}^{∗} > t/2r) ≤ ∑ ℙ(Y_{{i}} > t/2r) in Theorem 6A and hope for the best. For k = 2, Y_{{i}} is the number of surviving neighbors of vertex i, which is a sum of independent random variables, so Chernoff’s inequality can be applied. For k > 2 each Y_{{i}} is a sum of dependent random variables but of the same type as X, which gives room for induction. One way of doing it leads to the following result, the proof of which is presented in [10] (cf. Corollary 4.1 there). Let Δ_{j} = Δ_{j}(S) be the maximum number of elements of S containing a given j-element set, j = 0, …, k. Theorem 6C. Let λ_{j}^{∗} = Δ_{j}p^{k−j} [thus λ_{0}^{∗} = λ]. Then, with c_{k} = 1/12k, and for all 0 < ρ ≤ 1,

ℙ(X ≥ (1 + ρ)λ) ≤ 2N^{k−1} exp \{−c_{k} min_{1≤j≤k} (\frac{ρ^{2}λ}{λ_{j}^{∗}})^{1/j}\} .

2.3.4 Approximating by a disjoint subfamily

Our last method originates in Spencer [16] (cf. Example 1, below). Let X_{0} be the largest number of disjoint sets of S which are present in Γ_{p}. Clearly, X ≥ X_{0}, but sometimes X is not much larger than X_{0}. Intuitively, X_{0} should have a distribution similar to that of a sum of independent random variables, and thus a Chernoff-type bound could be true. Our next lemma makes it precise.

Lemma 2. If t ≥ 0, then, with ϕ(x) = (1 + x) log(1 + x) − x and λ = 𝔼 X,

ℙ(X_{0} ≥ λ + t) ≤ exp (−λϕ(\frac{t}{λ})) ≤ exp (−\frac{t^{2}}{2(λ + t/3)}) .

For the proof of Lemma 2, which is similar to the proof of Lemma 1, see [9, Lemma 2.46].

In order to relate X to X_{0} we invoke a simple graph theoretic fact. For an arbitrary graph G set α(G) for its independence number, β(G) for the size of the largest induced matching in G, and Δ_{e}(G) for the maximum of |N_{G}(v) ∪ N_{G}(v′)| over all pairs (v, v′) of adjacent vertices of G. Note that Δ_{e}(G) ≤ 2Δ(G).

Lemma 3. For every graph G, we have |V (G)| ≤ α(G) + β(G)Δ_{e}(G).

Proof. Let M be the set of edges in a maximal induced matching of G. The vertices outside M can be divided into two groups: those adjacent to M [at most β(G)(Δ_{e}(G)−2) of them] and those which are not. The latter group of vertices form an independent set in G and the lemma follows.

Consider the intersection graph L_{p} = L(S_{p}) of S_{p} = S ∩ [Γ_{p}]^{k}, in which every vertex represents one set of S_{p}, and the edges join pairs of vertices representing pairs of intersecting sets. (Note that L_{p} is an induced subgraph of L defined above.) Then X is the number of vertices and X_{0} is the independence number of L_{p}. Thus Lemma 3 implies that

X ≤ X_{0} + β(L_{p})Δ_{e}(L_{p}) ≤ X_{0} + 2β(L_{p})Δ(L_{p}).  (12)

We have already estimated the probability that X_{0} is large; hence estimates of β(L_{p}) and Δ(L_{p}) yield bounds on the upper tail of X. This leads to the following result. Recall that Δ_{j} = Δ_{j}(S) is the maximum number of elements of S containing a given j-element set, j = 0, …, k.

Theorem 7. Define R = λ max_{1≤j≤k−1} \binom{k}{j}Δ′_{j}p^{k−j}, where Δ′_{j} = Δ_{j} − 1. Then, for every t > 0 and r ≥ R,

ℙ(X ≥ λ + t) ≤ exp (−\frac{t^{2}}{8λ + 2t}) + (k − 1) exp\{−r\} + ℙ (Y_{1}^{∗} > \frac{t}{12k(k − 1)r} ) .  (13)

Remark 2. Very often the third term can be bounded (e.g. by a Chernoff inequality, see the examples in Section 3) by exp (−Θ(t/r)). Then, if, in addition, t = Θ(λ) → ∞, the first term is smaller than the sum of the other two (either r or t/r is not greater than \sqrt{t}), and therefore can be ignored. Also, note that for fixed ρ, if we ignore the first term, we are up to constants in the exponents left with the same bound as Theorem 6A, although now only for r ≥ R. Hence the above bound then is never better (up to constants in the exponent) than that from Theorem 6A, and it yields essentially the same result when the optimal r for Theorem 6A satisfies r ≥ R.

Proof. By (12), for any ℓ > 0,

ℙ(X ≥ λ + t) ≤ ℙ(X_{0} ≥ λ + t/2) + ℙ(β(L_{p}) > ℓ) + ℙ(Δ(L_{p}) > t/(4ℓ)).

By Lemma 2, the first term is smaller than exp (−\frac{t^{2}/4}{2(λ+t/6)}) ≤ exp (−\frac{t^{2}}{8λ+2t}). For the third term observe that Δ(L_{p}) ≤ kΔ(S_{p}) = kY_{1}^{∗}, so ℙ(Δ(L_{p}) > t/4ℓ) ≤ ℙ(Y_{1}^{∗} > t/(4kℓ)).

It remains to estimate ℙ(β(L_{p}) > ℓ). First note that an induced matching in L_{p} with m edges corresponds to 2m distinct sets A_{i}, B_{i} ∈ S_{p}, 1 ≤ i ≤ m, such that A_{i} ∩ B_{i} ≠ ∅, but A_{i} ∩ A_{j} = A_{i} ∩ B_{j} = B_{i} ∩ B_{j} = ∅, i ≠ j. Consequently, if S̃ = {A ∪ B : A, B ∈ S, A ≠ B, A ∩ B ≠ ∅}, then β(L_{p}) is the maximum size of a disjoint subfamily of S̃_{p}, i.e. β(L_{p}) = α(L(S̃_{p})). Thus, β(L_{p}) is a random variable of the same type as X_{0}, except that S̃ is not a uniform hypergraph. To overcome this mild difficulty, we write S̃ = ⋃_{j=1}^{k−1} S̃^{j}, where S̃^{j} = {A ∪ B : A, B ∈ S, |A ∩ B| = j}, and thus have, with Y_{0}^{j} = α(L(S̃_{p}^{j})),

β(L_{p}) = α (L ( ⋃_{j=1}^{k−1} S̃_{p}^{j})) ≤ ∑_{j=1}^{k−1} Y_{0}^{j}.

Hence,

ℙ(β(L_{p}) > ℓ) ≤ ∑_{j=1}^{k−1} ℙ(Y_{0}^{j} > ℓ/(k − 1)).

In order to apply Lemma 2 to Y_{0}^{j}, we need to estimate the expected size of S̃_{p}^{j}. For each A ∈ S there are at most \binom{k}{j}Δ′_{j} choices of B ∈ S with |A ∩ B| = j. Hence, setting Y^{j} = |S̃_{p}^{j}|,

𝔼 Y^{j} ≤ \binom{k}{j}Δ′_{j}|S|p^{2k−j} = \binom{k}{j}Δ′_{j}p^{k−j}λ ≤ R ≤ r

and, by Lemma 2, with ℓ = 3(k − 1)r,

ℙ(Y_{0}^{j} > ℓ/(k − 1)) = ℙ(Y_{0}^{j} > 3r) ≤ ℙ(Y_{0}^{j} > 𝔼 Y^{j} + 2r) ≤ e^{−r}.

Sometimes, β(L_{p}) and Δ(L_{p}) (or Δ_{e}(L_{p})) can be estimated with more ease. This is the case of the next example from [16] where this technique originated.

Example 1. Let X^{(v)} be the number of triangles of G(n, p) containing a given vertex v, where p = (ω log n)^{1/3}n^{−2/3} and ω → ∞ with ω ≤ log n, say. The problem is to estimate min_{v} X^{(v)} and max_{v} X^{(v)}. Set X = X^{(1)}. A standard application of Chebyshev’s inequality yields that X/λ →^{p} 1, and for example 0.9λ < X < 1.1λ with probability 1−O(1/λ), where λ = Θ(ω log n). This, however, is not enough to claim that such a concentration of the number of triangles holds for every vertex of G(n, p). For this to be true, we need to decrease the error probability down to o(1/n). Of course, there is no problem with the lower tail. By Theorem 0, ℙ(X ≤ 0.9λ) ≤ exp{−Ω(λ)} = o(1/n).

It turns out that with probability 1 − o(1/n), we have X ≤ X_{0} + 12. This follows quite easily by the first inequality in (12). Indeed, with that probability β(L_{p}) ≤ 3 and Δ_{e}(L_{p}) ≤ 4. [The right hand side of (12) gives only X ≤ X_{0} + 18, as, with probability 1 − o(1/n), we may only bound Δ(L_{p}) ≤ 3.] Hence, for large enough n, by Lemma 2,

ℙ(X ≥ 1.1λ) ≤ ℙ(X_{0} ≥ 1.1λ−12)+o(1/n) ≤ ℙ(X_{0} ≥ 1.05λ)+o(1/n) ≤ exp{−cλ}+o(1/n) = o(1/n).

3 Applications

In this section we illustrate all methods introduced earlier by a couple of pivotal applications and compare the results. We will refer to the methods via the following numbers and/or nicknames:

1) Azuma (Theorem 1), 2) Talagrand (Theorem 2), 3A,B,C) Kim–Vu (Theorems 3A, 3B, 3C), 4) Complement (Theorem 4), 5) Break-up (Theorem 5), 6A,B,C) Deletion (Theorems 6A, 6B, 6C), 7) Approximation (Theorem 7).

We always express t = ρλ, 0 < ρ ≤ 1, and always compare bounds on ℙ(X > λ + t) (except for Method 2 where we have the median m in place of λ), ignoring insignificant constants. We denote insignificant constants (that may be made explicit) by c; the value of c may depend on k and other parameters, and may change from one occurence to the next.

3.1 Random induced subhypergraphs

The following problem about a random subgraph obtained by a random deletion of vertices of a given graph was studied in [14]. Here we state it for k-uniform hypergraphs.

Let H = (V, E) be a k-uniform hypergraph with |V | = N and |E| = η\binom{N}{k}, 0 < η ≤ 1, and let V_{p} be a binomial random subset of the vertex set V, 0 < p < 1. Here every vertex i is associated with a 0–1 random variable ξ_{i}, where ℙ(ξ_{i} = 1) = p. Thus, Y = |V_{p}| has the binomial distribution Bi(N, p), and S is the family of all hyperedges of H. We let Δ_{H} denote the maximum degree of H, i.e. the maximum number of hyperedges containing a given vertex. Note that |E| ≤ NΔ_{H}/k. Moreover, Δ_{j} = Δ_{j}(H) is the maximum number of hyperedges of H containing a given j-element set, j = 0, …, k; thus Δ_{1} = Δ_{H}.

We want to show that with probability very close to 1, the random variable X = |[V_{p}]^{k} ∩ E| is, say, not larger than 2η\binom{Np}{k}, i.e., that the density of the random subgraph is not much larger than the density of the initial hypergraph. Note that λ = 𝔼 X = η\binom{N}{k}p^{k} ∼ η\binom{Np}{k}, and so this problem falls into our general framework of estimating upper tails. In fact, this is precisely the setup of our combinatorial methods 4–7 described in general terms in Section 2. Below, we study asymptotics as N → ∞, where η, p and ρ may depend on N, with ρ ≤ 1, while k ≥ 2 is fixed. Throughout we assume that Np → ∞, and in particular Np ≥ 1.

We will try all seven methods in two basic cases. In the general case, where no assumption is made on H, we will use the trivial bounds Δ_{j}(H) ≤ N^{k−j}, j = 1, …, k. In the highly regular case (and presumably sparse, meaning η → 0) we will be assuming that Δ_{j} = Θ(ηN^{k−j}), j = 1, …, k − 1. (The unspecified constants c below may depend on the constants implicit in this Θ.) Note that Δ_{0} = |E| = Θ(ηN^{k}) by definition, while Δ_{k} = 1 unless H is empty.

As a warm-up consider first the special case in which H is the complete k-uniform hypergraph K_{N}^{k}, i.e. η = 1. Then X = \binom{Y}{k} < Y^{k}/k!, and λ = (Np)^{k}(1/k! + o(1/Np)). Hence, assuming ρNp is large enough,

ℙ (X > (1 + ρ)λ) ≤ ℙ (Y^{k} > (1 + ρ/2)(Np)^{k}) = ℙ (Y > (1 + ρ/2)^{1/k}Np) ≤ ℙ (Y > (1 + \frac{ρ}{3k} ) Np) ,

and by Chernoff’s bound (1), we obtain

ℙ (X > (1 + ρ)λ) ≤ exp{−cρ^{2}Np}.  (14)

This bound is essentially sharp and we will use it to measure the accuracy of all our methods applied to the general case.

1) Azuma. Adding/deleting a vertex may change the value of X by at most the degree of that vertex. Thus, applying Theorem 1 with b_{i} = deg_{H}(i) we obtain the bound

exp \{−c\frac{ρ^{2}η^{2}N^{2k−1}p^{2k}}{Δ_{H}^{2}} \} .

2) Talagrand. Here again the Lipschitz condition is satisfied with b_{i} = deg_{H}(i). However, the obvious choice ψ(r) = NΔ_{H}^{2} yields only the same bound as Azuma, with an inferior constant. To get a better estimate we have to modify X by a sort of truncation. Let

X′ = max{|[V′]^{k} ∩ E| : V′ ⊆ V_{p}, |V′| ≤ 2Np}.

Clearly, X′ satisfies condition (L) with the same constants b_{i} as X does, and condition (C) with ψ(r) = 2NpΔ_{H}^{2}. By Chernoff’s bound (1),

ℙ(X ≠ X′) ≤ ℙ(|V_{p}| > 2Np) ≤ e^{−cNp}.

This and (7) yield the bound

exp \{−c\frac{ρ^{2}η^{2}N^{2k−1}p^{2k−1}}{Δ_{H}^{2}} \} + e^{−cNp} < 2 exp \{−c\frac{ρ^{2}η^{2}N^{2k−1}p^{2k−1}}{Δ_{H}^{2}} \} .

3A) Kim–Vu A. We can write

X = ∑_{A∈S} ∏_{i∈A} ξ_{i}.

Thus,

∂_{A}X = ∑_{A⊆B∈S} ∏_{i∈B\A} ξ_{i},

and,

𝔼_{1}(X) = max_{1≤j≤k} Δ_{j}(H)p^{k−j} ≤ max_{1≤j≤k}(Np)^{k−j} = (Np)^{k−1}.  (15)

Hence, (8) with l = c_{k}^{−1/k}ρ^{1/k}λ^{1/2k}(𝔼_{1}(X))^{−1/2k}implies (the case 𝔼_{1}(X) > λ is trivial here, since then ℓ is bounded)

ℙ (|X − λ| ≥ ρλ) ≤ N^{k−1} exp{−cρ^{1/k}(ηNp)^{1/2k}}.  (16)

In the highly regular case, 𝔼_{1}(X) = Θ(max[1, η(Np)^{k−1}]) and the exponent in (16) is improved to −cρ^{1/k}(Np)^{1/2k} if η(Np)^{k−1} ≥ 1 and −cρ^{1/k}η^{1/2k}(Np)^{1/2} otherwise.

3B) Kim–Vu B. Observe that

E_{i} = ∑_{j=0}^{k−1} ∑_{i∈A∈E, |A\[i]|=j} p^{j} ∏_{l∈A∩[i−1]} ξ_{l}.

This is a polynomial of degree k − 1, so in principle one could apply induction here. However, as this approach seems to be quite complicated, we refer instead to Theorem 3C, see below, where the work with the induction already has been done, in a general setting, by Vu [21].

We here thus focus on the case k = 2, i.e. the case of graphs, because only then E_{i} becomes a sum of independent variables (j = 0) and a constant term (j = 1). Indeed, for k = 2,

E_{i} = ∑_{\begin{matrix}j<i \\ \{i,j\}∈E \end{matrix}} ξ_{j} + ∑_{\begin{matrix}j>i \\ \{i,j\}∈E \end{matrix}} p ≤ Z + pΔ_{H},

where Z ∈ Bi(Δ_{H}, p). Also,

W = p ∑_{i} E_{i} ≤ pΔ_{H}Y + p^{2}|E|.

By Chernoff’s bound (1), ℙ(Y ≥ 3Np) < e^{−Np}, and so, with probability at least 1 − e^{−Np}, we have W < 4Δ_{H}Np^{2}. Now, choose a = bpΔ_{H}, where b ≥ 9, and v = 4aΔ_{H}Np^{2}. By (1), with 𝔼 Z = Δ_{H}p,

ℙ(E_{i} > a) ≤ ℙ(Z ≥ (b − 1) 𝔼 Z) = ℙ(Z − 𝔼 Z ≥ (b − 2) 𝔼 Z) ≤ exp(−ϕ(b − 2) 𝔼 Z),

where ϕ(b−2) = (b−1) log(b−1)−b+2 ≥ b, because log(b−1) > 2. Hence, by Theorem 3B, setting ℓ = ρ^{2}λ^{2}/v and checking that ℓ < v/a^{2} (this follows from λ < NΔ_{H}p^{2}), we obtain the estimate

ℙ(X ≥ (1 + ρ)λ) ≤ 2e^{−ℓ/4} + Ne^{−bpΔ_{H}} + e^{−Np}.  (17)

We have to choose b optimally. We would like ℓ/4 = bpΔ_{H}, i.e. b = \frac{1}{8}ρη(N − 1)N^{1/2}Δ_{H}^{−3/2}, but also b ≥ 9. Thus, choosing b = max(\frac{1}{8}ρη(N/Δ_{H})^{3/2}, 9) in (17) we find, since then ℓ/4 < v/(4a^{2}) = Np/b < Np,

ℙ(X ≥ (1 + ρ)λ) ≤ (N + 3)e^{−ℓ/4} ≤ \begin{cases}2N exp \{−c\frac{ρηN^{3/2}p}{Δ_{H}^{1/2}}\} & if ρη(N/Δ_{H})^{3/2} ≥ 72, \\ 2N exp \{−c\frac{ρ^{2}η^{2}N^{3}p}{Δ_{H}^{2}}\} & otherwise. \end{cases}

3C) (Kim–)Vu C. We have, generalizing (15),

𝔼_{j}(X) = max_{i≥j} Δ_{i}(X)p^{k−i}.

We thus need to find ℓ and E_{0}, …, E_{k} such that \sqrt{ℓE_{0}E_{1}} ≤ ρλ, E_{j} ≥ Δ_{j}(H)p^{k−j}, 0 ≤ j ≤ k, and E_{j}/E_{j+1} ≥ ℓ + j log N, 0 ≤ j ≤ k − 1.

It is easily checked that if Np ≥ 2k log N, then these conditions are satisfied with E_{0} = λ = Θ(η(Np)^{k}), E_{j} = (Np)^{k−j}, 1 ≤ j ≤ k, and ℓ = ρ^{2}λ^{2}/E_{0}E_{1} = ρ^{2}λ/E_{1} = Θ(ρ^{2}ηNp). (It is also easily checked that these choices are essentially optimal without further assumptions.) Hence,

ℙ(X ≥ (1 + ρ)λ) ≤ C exp(−cℓ) ≤ C exp (−cρ^{2}ηNp), Np ≥ 2k log N.

As a trivial consequence, for any N and p,

ℙ(X ≥ (1 + ρ)λ) ≤ N exp (−cρ^{2}ηNp).

In the highly regular case, we instead choose E_{j} = C max((2ℓ)^{k−j}, η(Np)^{k−j}), 0 ≤ j ≤ k, and ℓ = c min(ρ^{2/k}η^{1/k}Np, ρ^{2}Np); it is easily checked that the conditions then are satisfied, provided C is large, c is small and ℓ ≥ k log N. Consequently, in the highly regular case,

ℙ(X ≥ (1 + ρ)λ) ≤ N exp(−c min(ρ^{2/k}η^{1/k}Np, ρ^{2}Np)).

4) Complement. By Theorem 4,

ℙ(X ≥ (1 + ρ)λ) ≤ 2e^{−cρ^{2}η^{2}Np}.

5) Break-up. By Theorem 5, with Δ(L) < kΔ_{H},

ℙ(X ≥ (1 + ρ)λ) ≤ kΔ_{H} exp \{−\frac{ρ^{2}λ}{4kΔ_{H}(1 + ρ/3)}\} .

6A) Deletion A. As for Theorem 3B, we consider only the case k = 2; for larger k one can use induction, but we refer instead to Theorem 6C, where the induction already is done. If k = 2, Theorem 6A yields

ℙ(X ≥ (1 + ρ)λ) ≤ e^{−ρr/6} + ∑_{i} ℙ(Y_{{i}} > t/2r),

where Y_{{i}} = ξ_{i}Z_{i} with Z_{i} ∈ Bi(deg_{H}(i), p). Hence, if t/2r ≥ 7, (1) implies ℙ(Y_{{i}} > t/2r) ≤ exp(−t/2r), see [9, Corollary 2.4], and thus

ℙ(X ≥ (1 + ρ)λ) ≤ e^{−ρr/6} + Ne^{−ρλ/2r}.

Choosing the optimal (ignoring polynomial factors) r = min(\sqrt{3λ}, t/14Δ_{H}p), we find

ℙ(X ≥ (1 + ρ)λ) ≤ (N + 1)e^{−ρr/6} ≤ exp(−c min(ρ\sqrt{λ}, \frac{ρ^{2}λ}{Δ_{H}p})).

6B) Deletion B. By Theorem 6B,

ℙ(X ≥ (1 + ρ)λ) ≤ exp \{−\frac{ρ^{2}λ}{6kΔ_{H}} \} .

This is essentially the same bound as the one given by Method 5.

6C) Deletion C. It follows from Theorem 6C, using Δ_{j} ≤ N^{k−j}, that

ℙ(X ≥ (1 + ρ)λ) ≤ 2N^{k−1} exp{−cηρ^{2}Np}.

In the highly regular case we obtain the (sometimes) better

ℙ(X ≥ (1 + ρ)λ) ≤ 2N^{k−1} exp{−c min(ρ^{2}, ρ^{2/k}η^{1/k})Np}.

7) Approximation. This method is useless for dense hypergraphs H. Indeed, for it to be successful one needs that the ratio t/r should be at least of the order of 𝔼 Y_{1}^{∗} = Θ((Np)^{k−1}). However, if η is constant, we have r ≥ R = Θ((Np)^{2k−1}) while only t = Θ((Np)^{k}). Hence, the estimate (13) does not tend to 0.

Yet, the method can still yield good bounds for sparse and highly regular H. To avoid dependence in Y_{1}^{∗}, we consider only the special case of graphs, i.e. k = 2, and assume for simplicity that ρ is constant. Let us assume that Δ_{1} = Δ_{H} = Θ(ηN). Then R = Θ(η^{2}(Np)^{3}), 𝔼 Y_{1}^{∗} = Θ(ηNp), and via the Chernoff bound (1), the three terms on the right hand side of (13) are exp(−Θ(η(Np)^{2})), (k − 1) exp(−r) and exp(−Θ(t/r)), where we need r ≥ R and t/r ≥ CηNp. A perfect choice would be r = \sqrt{t} = Θ(\sqrt{η}Np) which satisfies the above constraints provided η ≤ c(Np)^{−4/3}. Then

ℙ(X ≥ (1 + ρ)λ) ≤ 3 exp\{−c\sqrt{η}Np\}.

For larger η, the best choice is r = R = Θ(η^{2}(Np)^{3}), which yields the bound e^{−c/(ηNp)} which is meaningful if ηNp < 1. In conclusion we find, for fixed ρ and with c = c(ρ),

ℙ(X ≥ (1 + ρ)λ) ≤ 3 exp{−c min(η^{1/2}Np, (ηNp)^{−1})}.

Summary of subsection 3.1.

fixed η  η → 0  η → 0, H highly regular
1) Azuma  ρ^{2}Np^{2k}  ρ^{2}η^{2}Np^{2k}  ρ^{2}Np^{2k}
2) Talagrand  ρ^{2}Np^{2k−1}  ρ^{2}η^{2}Np^{2k−1}  ρ^{2}Np^{2k−1}
3A) Kim–Vu A  ρ^{1/k}(Np)^{1/2k} ρ^{1/k}η^{1/2k}(Np)^{1/2k} ρ^{1/k} min((Np)^{1/2k}, η^{1/2k}(Np)^{1/2})
3B) Kim–Vu B, k = 2  ρ^{2}Np  ρ^{2}η^{2}Np  min(ρ^{2}, ρ\sqrt{η})Np
3C) (Kim–)Vu C  ρ^{2}Np  ρ^{2}ηNp  min(ρ^{2}, ρ^{2/k}η^{1/k})Np
4) Complement  ρ^{2}Np  ρ^{2}η^{2}Np  ρ^{2}η^{2}Np
5) Break-up  ρ^{2}Np^{k}  ρ^{2}ηNp^{k}  ρ^{2}Np^{k}
6A) Deletion A, k = 2  ρ^{2}Np  ρ^{2}ηNp  min(ρ^{2}, ρ\sqrt{η})Np
6B) Deletion B  ρ^{2}Np^{k}  ρ^{2}ηNp^{k}  ρ^{2}Np^{k}
6C) Deletion C  ρ^{2}Np  ρ^{2}ηNp  min(ρ^{2}, ρ^{2/k}η^{1/k})Np
7) Approximation, k = 2  —  —  c(ρ) min(\sqrt{η}Np, (ηNp)^{−1})

Table 1: Exponents for upper tail bounds in the subhypergraph problem

We first summarize the obtained results in Table 1. An entry F means a bound O(N^{c_{1}}) exp(−c_{2}F) for some positive constants c_{1} and c_{2} (c_{1} might be 0). Hence the larger F, the better, i.e. (asymptotically) smaller, bound.

Consider first the case in which both ρ and η are constants. In this case Δ_{H} = Θ(N^{k−1}), and we see that Methods 3C (Vu), 4 (Complement), and 6C (Deletion) all yield the optimal value of Np. For k = 2, Methods 3B and 6A too yield this value; as indicated above, with induction and more effort, they yield estimates of the same order in the exponent for higher k too. Note that the truncated Talagrand (Np^{2k−1}) is better than Azuma (Np^{2k}), and, most interestingly, Break-up (Np^{k}) is better than both of them.

Now allow η → 0 with ρ constant. Then, in the worst case Δ_{H} = Θ(N^{k−1}), Methods 3B and 4 give only an exponent of order η^{2}Np, while Methods 3C and 6C (and 6A for k = 2) are now the best with ηNp.

Finally, assume that H is highly regular, still keeping ρ constant. If η ≫ p^{k(k−1)}, then Methods 3C and 6C, and for k = 2 at least, 3B, 6A and 7 too, tie up with the exponent Θ(λ^{1/k}) = Θ(η^{1/k}Np) (Method 7 only in a restricted range of η). Method 4 is unaffected by the improvement in Δ_{H}. On the other hand, if η ≪ p^{k(k−1)}, then Methods 5 (Break-up) and 6B (Deletion) are the best with Np^{k}.

If also ρ → 0, we see that most methods give a factor ρ^{2} in the exponent, except for Methods 3A (with only ρ^{1/k}, but here the main term is very weak and the exponent is never better than the one given by 3C), 7 (not investigated), and, in the highly regular case, 3B, 3C, 6A and 6C (with ρ for k = 2, as long as ρ ≥ η^{1/2}). A detailed analysis of this case, with η fixed or decaying to 0, is left to the eager reader.

3.2 Small subgraphs of random graphs

Let 𝔾(n, p) be a binomial random graph. It can be viewed as a random subset of the set [n]^{2} of all pairs formed by the set \{1, …, n\}. Thus, N = \binom{n}{2}. 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 G(n, p). Let k = v(G) and assume n ≥ k. Then

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

where Aut(G) is the set of automorphisms of G and ≍ means that the quotient of the two sides is bounded from above and below by positive constants. The subgraph counts X_{G} have received a lot of attention from the pioneering paper by Erdős and Rényi [3] to the present day. Bounds for the upper tail (in the more general context of extensions) were considered by Spencer [16], but the break-through with general exponential bounds came with Vu [20].

In this subsection we try our techniques on estimates of the upper tail of X_{G} for three small subgraphs: G = K_{3}, G = K_{4} and G = C_{4}. Throughout we for simplicity assume that ρ = 1, i.e. t = λ, and leave the case ρ → 0 to the reader. As a test of how good these results are, we compare them with the exponential lower bound on ℙ(X_{G} ≥ (1 + ρ)λ) obtained by Vu [20], see Section 1 for the case K_{3} (see also [10, (6.2)]). For our three cases, G = K_{3}, G = K_{4} and G = C_{4}, Vu’s lower bound has the exponent −cn^{2}p^{2} log n, −cn^{2}p^{3} log n and −cn^{2}p^{2} log n, resp.

1) Azuma. Having a choice between vertex- and edge-exposure, we realize that the latter is better. Indeed, although the martingale is longer, the Lipschitz constants tend to be smaller, as fixing one edge leaves less freedom for creating a copy of a given graph than when fixing just a single vertex. Ignoring constants, for G = K_{3}, G = K_{4}, and G = C_{4}, we have b_{i} = n, b_{i} = n^{2} and again b_{i} = n^{2}, resp. Thus, the exponents in the estimates are of the order n^{2}p^{6}, n^{2}p^{12}, and n^{2}p^{8}, resp.

2) Talagrand. A truncation similar to that in 3.1.2, restricting the number of edges to, say, n^{2}p, plus a Chernoff inequality, allows us to apply (7) with b_{i} as for Azuma and ψ(r) = n^{2}p(max b_{i})^{2}. This provides the exponents n^{2}p^{5}, n^{2}p^{11} and n^{2}p^{7}, resp., thus, by one power of p better than Method 1.

In the case G = K_{3}, for p ≫ n^{−1/3}, a direct application of the Talagrand inequality, with the certificate being the set of all edges of 𝔾(n, p) (they all a.a.s. belong to the copies of K_{3}), yields only the exponent n^{2}p^{6}. For K_{4} and C_{4} too, a similar direct approach yields the same exponents as Method 1.

3A) Kim–Vu A. For G = K_{3}, we have k = 3 and 𝔼_{1}(X) = max{np^{2}, 1}. Hence, by Theorem 3A

ℙ(X_{K_{3}} ≥ 2λ) ≤ n^{4} \begin{cases}exp \{−cn^{1/3}p^{1/6}\} & if p ≥ n^{−1/2} \\ exp \{−cn^{1/2}p^{1/2}\} & otherwise. \end{cases}

Similarly, with k = 6 and 𝔼_{1}(X) = max{n^{2}p^{5}, 1},

ℙ(X_{K_{4}} ≥ 2λ) ≤ n^{10} \begin{cases}exp \{−cn^{1/6}p^{1/12}\} & if p ≥ n^{−2/5} \\ exp \{−cn^{1/3}p^{1/2}\} & otherwise. \end{cases}

and, with k = 4 and 𝔼_{1}(X) = max{n^{2}p^{3}, 1},

ℙ(X_{C_{4}} ≥ 2λ) ≤ n^{6} \begin{cases}exp \{−cn^{1/4}p^{1/8}\} & if p ≥ n^{−2/3} \\ exp \{−cn^{1/2}p^{1/2}\} & otherwise. \end{cases}

3B, C) Kim–Vu. To apply Theorem 3B even to X_{K_{3}} we have to use induction. As we already know, one induction scheme leads to Theorem 3C. It is easily verified that for our three examples, and more generally for any balanced graph G, Theorem 3C applies with k = e(G), ℓ = λ^{1/k} and E_{j} = (Cλ)^{1−j/k}, provided λ^{1/k} ≥ log n, which leads to

ℙ(X_{G} ≥ 2λ) ≤ n exp {−cλ^{1/e(G)}} = n exp {−cn^{v(G)/e(G)}p} .

For K_{3}, K_{4} and C_{4} this yields the exponents np, n^{2/3}p and np, resp.

The induction used to prove Theorem 3C means in this case adding one edge at a time to G. However, there are better induction schemes. Vu [20, Theorem 3] has shown, using Theorem 3B and an induction adding vertices one by one, the better estimate

ℙ(X_{G} ≥ 2λ) ≤ n exp {−cλ^{1/(v(G)−1)}} .

for every balanced G. (The induction hypothesis is actually stated more generally for extension counts, see [20] for details.) In our three cases, this yields the exponents n^{3/2}p^{3/2}, n^{4/3}p^{2} and n^{4/3}p^{4/3}, resp.

4) Complement. This method works well for dense families S, which is not the case here. There are Θ(n^{6}) 3-element subsets of [n]^{2} and only Θ(n^{3}) triangles. Thus, η = Θ(n^{−3}) and so, the exponent in Theorem 4 is η^{2}Np = O(p/n) = o(1). Things get only worse for G = K_{4} and G = C_{4}.

5) Break-up. By Theorem 5, with Δ(L) ≤ e(G)Δ_{H} and Δ_{H} equal to the Lipschitz constants from 3.2.1 (Azuma), we obtain exponents n^{2}p^{3}, n^{2}p^{6} and n^{2}p^{4}, resp.

6) Deletion. First, note that (ignoring constants in the exponent) Theorem 6B gives the same bounds as Theorem 5, and that Theorem 6C gives the same bounds as Theorem 3C. For K_{3}, K_{4} and C_{4} this yields the exponents n^{2}p^{3}, n^{2}p^{6} and n^{2}p^{4}, resp., for 6B and np, n^{2/3}p and np, resp., for 6C.

Recall that Theorem 6C is based on Theorem 6A and induction; in this case the induction is over the number of edges in the graph G. Just as for the Kim–Vu method, there are better induction schemes, and an induction over the number of vertices in G yields the better estimate

ℙ(X_{G} ≥ 2λ) ≤ n exp {−cλ^{1/(v(G)−1)}}

for every balanced G, exactly as for Method 3. (Again the induction hypothesis is more general. See [10] for details and a general theorem.) In our three cases, this yields the exponents n^{3/2}p^{3/2}, n^{4/3}p^{2} and n^{4/3}p^{4/3}, resp.

There are even more efficient ways to use Theorem 6A, although they so far require more effort and ad hoc arguments. First, Theorem 6A can be used directly for K_{3}. In this case Y_{{i}} = ξ_{i}Z_{i}, where Z_{i} ∈ Bi(n − 1, p^{2}) is the number of paths of length 2 between the endpoints of edge i. The Chernoff bound (1) thus yields, see [9, Corollary 2.4], that if λ/2r ≥ 7np^{2}, then

ℙ(Y_{{i}} > λ/2r) ≤ ℙ(Z_{i} > λ/2r) ≤ exp {−λ/2r} .

Consequently Theorem 6A yields, for any r such that λ/2r ≥ 7np^{2},

ℙ(X_{K_{3}} ≥ 2λ) ≤ exp{−r/9} + N exp{−λ/2r}.

Choosing r = c\sqrt{λ}, we obtain

ℙ(X_{K_{3}} ≥ 2λ) ≤ n^{2} exp {−cn^{3/2}p^{3/2}} ,

as obtained above from [10]. This can be slightly improved by choosing instead r = c\sqrt{λ log n}, and using (1) more carefully, leading to

ℙ(X_{K_{3}} ≥ 2λ) ≤ n^{2} exp \{−cn^{3/2}p^{3/2}\sqrt{log n}\};

for details see [10]. Note also that choosing r = λ/2n in Theorem 6A leads to Theorem 6B, and thus the exponent n^{2}p^{3}, which is better when p ≫ n^{−1/3}.

For G = K_{4}, as shown in detail in [10], the term ℙ(Y_{{i}} > λ/2r) can be estimated using a two-fold application of the Chernoff bound (1), which results in the estimates

ℙ(X_{K_{4}} ≥ 2λ) ≤ \begin{cases}n^{2} exp \{−cn^{2}p^{3}\} & if np^{2} ≤ 1, \\ n^{2} exp \{−cn^{4/3}p^{5/3}\} & otherwise. \end{cases}

(Actually, for p ≤ n^{−1/2−ε}, the exponent can be improved to cn^{2}p^{3}\sqrt{log n} [10].) For p ≤ n^{−1/2}, the exponent here differs by only a logarithmic factor from the exponent n^{2}p^{3} log n in Vu’s lower bound, so this estimate is essentially optimal. Here the advantage of the direct Chernoff application over induction is striking.

The case G = C_{4} was not treated in [10], but a two-fold application of the Chernoff bound (1) as for K_{4} yields an essentially optimal bound here too for a certain range of p. In this case Y_{{i}} = ξ_{i}Z_{i}, where Z_{i} is the number of paths of length 3 between the endpoints of edge i. Note that each such path is determined by the middle edge and its orientation in the path. Thus, if U is the set of vertices adjacent to at least one of the endpoints of i, and W is the number of edges with both endpoints in U, then Y_{{i}} ≤ 2W, and thus, for any a > 0,

ℙ(Y_{\{i\}} > \frac{λ}{2r} ) ≤ ℙ(W > \frac{λ}{4r} ) ≤ ℙ(|U| > a) + ℙ(Bi(\binom{⌈a⌉}{2}, p) > \frac{λ}{4r} ),

where |U| ∈ Bi(n − 2, 2p − p^{2}).

If we choose r and a such that a ≥ 14np > 7 𝔼 |U| and λ/4r > 7\frac{a^{2}}{2} p, then by (1), see [9, Corollary 2.4], this yields

ℙ(Y_{{i}} > λ/2r) ≤ exp(−a) + exp(−λ/4r)

and hence Theorem 6A yields

ℙ(X_{C_{4}} ≥ 2λ) ≤ e^{−cr} + \binom{n}{2}(e^{−a} + e^{−λ/4r}).

If p ≥ n^{−2/3}, we choose (for a small c) a = r = cn^{4/3}p and obtain

ℙ(X_{C_{4}} ≥ 2λ) ≤ n^{2} exp {−cn^{4/3}p} , p ≥ n^{−2/3}.

For p ≤ n^{−2/3}, we choose a = cnp^{1/2} and r = cn^{2}p^{2}, and obtain

ℙ(X_{C_{4}} ≥ 2λ) ≤ n^{2} exp {−cn^{2}p^{2}} , p ≤ n^{−2/3}.

Just as for K_{4}, for small p (here p ≤ n^{−2/3}), the obtained exponent matches Vu’s lower bound up to a logarithmic factor.

7) Approximation. As we already know, Theorem 7 is never better than Theorem 6A (for ρ constant as here, at least), see Remark 2. Here they actually sometimes yield the same result. Indeed, for K_{3} we have R = λ · 3Δ′_{1}p^{2} = Θ(n^{4}p^{5}), since Δ_{1} = n − 2 and Δ_{2} = 1, and thus Δ′_{2} = 0. We apply the Chernoff bound (1) to Y_{1}^{∗} as for Method 6A. Since we now need r ≥ R, we see that the essentially optimal choice r = c\sqrt{λ} = Θ(n^{3/2}p^{3/2}) used above for Method 6A now is allowed if p ≤ cn^{−5/7}; otherwise, we must be content with the choice r = R. This yields the following estimates.

ℙ(X_{K_{3}} ≥ 2λ) ≤ \begin{cases}2 exp \{−cn^{3/2}p^{3/2}\} & if p ≤ n^{−5/7}, \\ exp \{−c/(np^{2})\} & otherwise. \end{cases}

For G = K_{4}, Method 7 fares worse. Since Δ_{3} = n − 3, we have R ≥ npλ ≫ λ, provided λ ≥ 1 to avoid trivialities, and thus r ≥ R implies λ/r → 0 and we do not get any meaningful bound.

For G = C_{4} we have, assuming λ ≥ 1 and thus np ≥ 1, R = Θ(λn^{2}p^{3}) = Θ(n^{6}p^{7}). If p ≤ n^{−4/5}, this allows the essentially optimal choice r = cn^{2}p^{2} used for Method 6A above, and the same double application of the Chernoff bound yields again the optimal bound

ℙ(X_{C_{4}} ≥ 2λ) ≤ n^{2} exp {−cn^{2}p^{2}} , p ≤ n^{−4/5},

although now for a smaller range of p only. For n^{−4/5} ≤ p ≤ cn^{−2/3} we have to take r = R, and can estimate the tail of Y_{{i}} as for Method 6A, now using a = c/np^{2}. We obtain

ℙ(X_{C_{4}} ≥ 2λ) ≤ n^{2} exp {−c/n^{2}p^{3}} , p ≥ n^{−4/5},

which is meaningful for p ≪ n^{−2/3}.

Summary of subsection 3.2. The results of this subsection are summarized in Table 2 and in Figures 1–3. A point (x, y) in the figures signifies a bound of the type c_{1} exp(−c_{2}n^{y}) when p = n^{−x}; in other words, the figures plot the asymptotic value of log | log(bound)|/ log n as a function of | log p|/ log n. Thus, the bigger y, the better bound. Note that along the x-axis, p decreases from constant values at the left end down to 1/n at the right end. The dotted line shows Vu’s lower bound.

K_{3}  K_{4}  C_{4}
1) Azuma  n^{2}p^{6}  n^{2}p^{12}  n^{2}p^{8}
2) Talagrand  n^{2}p^{5}  n^{2}p^{11}  n^{2}p^{7}
3A) Kim–Vu A  min(n^{1/3}p^{1/6}, n^{1/2}p^{1/2}) min(n^{1/6}p^{1/12}, n^{1/3}p^{1/2}) min(n^{1/4}p^{1/8}, n^{1/2}p^{1/2})
3B) Kim–Vu B [20]  n^{3/2}p^{3/2}  n^{4/3}p^{2}  n^{4/3}p^{4/3}
3C) (Kim–)Vu C  np  n^{2/3}p  np

4) Complement — —

—

5) Break-up  n^{2}p^{3}  n^{2}p^{6}  n^{2}p^{4}
6A) Deletion A [10] max(n^{3/2}p^{3/2}, n^{2}p^{3})  min(n^{2}p^{3}, n^{4/3}p^{5/3})  min(n^{2}p^{2}, n^{4/3}p)
6B) Deletion B  n^{2}p^{3}  n^{2}p^{6}  n^{2}p^{4}
6C) Deletion C  np  n^{2/3}p  np

7) Approximation min(n^{3/2}p^{3/2}, 1/(np^{2}))

—

min(n^{2}p^{2}, 1/n^{2}p^{3})
Vu’s lower bound  n^{2}p^{2}  n^{2}p^{3}  n^{2}p^{2}

Table 2: Exponents for upper tails in the small subgraphs problem, ignoring logarithmic factors.

[figure: 1; 1; 2; 1; 2; 3A; 3B,6A; 3C,6C; 5,6B; 7; 3B,6A,7]

Figure 1: K_{3}

[figure: 2/3; 1; 2; 1; 2; 3A; 3B; 3C,; 6C; 5,6B; 6A]

Figure 2: K_{4}

[figure: 1; 1; 2; 1; 2; 3A; 3B; 3C,; 6C; 5,6B; 6A; 7; 6A,7]

Figure 3: C_{4}

We leave the direct comparison of the results obtained by various methods to the anxious reader. Instead, we check how close these estimates get to the lower bound mentioned earlier. For G = K_{3}, none of them achieves it. The nearest are the bounds obtained by Methods 5 and 6 for rather dense graphs and Methods 3, 6 and 7 for sparser graphs. In the cases G = K_{4} and G = C_{4}, quite surprisingly, Methods 6 and 7, together with the double Chernoff argument used above, both achieve the lower bound in some range of p = p(n). (This can also be achieved by Method 3 [Vu, personal communication].)

Note also that the simple combinatorial Method 5 (Break-up) again beats both Azuma and Talagrand, and together with 6B is the best for rather dense graphs.

3.3 How many pairs support tepees?

Our last example is very special, but still worth mentioning. It shows the strength of Lemma 1 which gave rise to the Deletion Method 6, but so far has not been illustrated by any direct application. In the following problem we would like to obtain an upper bound on the upper tail of X_{C_{4}} for p = Θ(n^{−1/2}), which is of the order exp(−Θ(n)), just as Vu’s lower bound (ignore the logarithm, again). However, none of the Methods 1–7 gives that, and we do not know whether such a bound holds or not. Nevertheless, it turns out that if we apply Lemma 1 directly, and instead of proving a genuine bound on the tail allow ourselves to discard some edges, we will achieve our task.

The problem itself arose in the study of the width of the threshold for a Ramsey property of random graphs [4]. The solution, however, has originated in [15], where the Deletion Method traces back its roots.

Let G be a graph. The base of G, denoted by Base(G), is the set of all pairs of vertices of G with a common neighbor in G. Thus, Base(G) is a graph with the vertex set V (G), but typically not a subgraph of G. It is a subgraph of G^{2}, though.

In [4] the following lemma is needed.

Lemma 4. For every c > 0 and a > 0 there exists a′ such that a.a.s. for any (spanning) subgraph F of the random graph 𝔾(n, cn^{−1/2}) with |E(F)| > acn^{3/2}, the graph Base(F) contains at least a′n^{3} triangles.

In the proof which we only outline here (for details see [5]), an application of a sparse regularity lemma (see [9, Lemma 8.19, page 216]) to F yields, for a suitably chosen ρ > 0, the existence of a pair of disjoint subsets of vertices, U and V with an/2 ≤ |U| ≤ an, |V | = n/k, where k ≤ K = K(ρ, a), such that for every W ⊂ V, |W | = ρ|V |, all but at most ρ|U| vertices of U have each at least

(1 − ρ′)ap|W |/2 = (1 − ρ′)acρ\sqrt{n}/2k  (18)

neighbors in W, where ρ′ = ρ′(ρ, a) > ρ.

The next and last step is to show that a.a.s. every such W induces a subgraph B_{W} of Base(F)[V] with at least a′′\binom{|W |}{2} edges, where a′′ = min\{a^{3}c^{2}/20, a^{4}/400\} does not depend on ρ. This will easily imply (see [15, Lemma 2]) that Base(F)[V] itself contains at least a′′′|V |^{3} triangles, which proves Lemma 4 with a′ = a′′′/K^{3}. The same Lemma 2 of [15] determines ρ = ρ(a′′).

We will underestimate the edges of B_{W} by counting only pairs of vertices of W with a common neighbor in U. So, let H = F [U, W], i.e. H is the bipartite subgraph of F with the bipartition sets U and W and all the edges of F with one endpoint in U and the other in W. Then B_{W} ⊇ Base(H)[W].

How to count the edges of Base(H)[W]? Let us number the pairs of vertices in W by 1, …, \binom{|W |}{2} and denote by x_{i} the number of paths of length two in H connecting the vertices of the i-th pair (such paths are called in [4] tepees). Set L for the number of those i ∈ \{1, …, \binom{|W |}{2}\} for which x_{i} > 0, i.e. for the sought number of pairs of vertices of W with a common neighbor in U. Assume that x_{1}, …, x_{L} > 0.

Observe that, denoting by d_{u} the degree of vertex u ∈ U in H,

∑_{i=1}^{L} x_{i} = ∑_{u∈U} \binom{d_{u}}{2} and ∑_{i=1}^{L} \binom{x_{i}}{2} = X_{C_{4}}(H),

where X_{C_{4}}(H) is the number of copies of C_{4} in H.

If L ≥ ∑_{i=1}^{L} x_{i}/2, then by (18) (for ρ small)

L ≥ \frac{1}{2} ∑_{u∈U} \binom{d_{u}}{2} ≥ \frac{1}{33}(1 − ρ′)^{3}a^{3}c^{2}ρ^{2}(n/k)^{2} ≥ \frac{1}{20}a^{3}c^{2}\binom{|W |}{2}.

Otherwise, by the Cauchy–Schwarz inequality,

∑_{i} \binom{x_{i}}{2} ≥ L\binom{∑_{i} x_{i}/L}{2} ≥ \frac{(∑_{i} x_{i})^{2}}{4L} ,

and a decent upper bound on X_{C_{4}}(H) will give a lower bound on L and thus on the number of edges of Base(H)[W].

To get back to the genuine random graph not affected by a malicious choice of the subgraph H, we may bound X_{C_{4}}(H) by X_{C_{4}}(U, W) – the number of copies of C_{4} contained in the bipartite subgraph 𝔾(n, p)[U, W] of 𝔾(n, p) spanned by U and W. Obviously, the expectation of X_{C_{4}}(U, W) is equal to \binom{|U|}{2}\binom{|W |}{2}p^{4} = Θ(n^{4}p^{4}) = Θ(n^{2}).

To accommodate the number of choices of the sets U and W, which is bounded by 4^{n}, we would need an upper tail estimate on X_{C_{4}}(U, W) which is close to the lower bound established by Vu. None of our methods provides such a bound. Fortunately, we may use Lemma 1.

Define a random variable Y_{−k}(U, W) = min_{E_{0}⊂E(𝔾(n,p)), |E_{0}|≤k} X_{−E_{0}}(U, W), where X_{−E_{0}}(U, W) is the number of copies of C_{4} in the subgraph G(n, p)[U, W] − E_{0}. It follows quickly from Lemma 1 that a.a.s. for all U and W we have

Y_{−n log n}(U, W) < 2 𝔼 X_{C_{4}}(U, W) = 2\binom{|U|}{2}\binom{|W |}{2}p^{4} < \frac{a^{2}ρ^{2}c^{4}n^{2}}{2k^{2}} .

The bottom line of this argument is that even after deleting the edges of E_{0} = E_{0}(U, W), still all but, say, at most 2ρ|U| vertices of U have each at least (1 − 2ρ′)ap|W |/2 = (1 − 2ρ′)acρ\sqrt{n}/2k neighbors in W. Indeed, as |E_{0}| = n log n, at most, say, n^{2/3} vertices of U may have each more than n^{1/3} log n edges of E_{0} incident to them.

Let d_{u}^{0} be the degree of u in H − E_{0}, u ∈ U, and similarly, let x_{i}^{0} and L^{0} be modifications of the previously introduced quantities. Note that |E(Base(H)[W])| ≥ L^{0} and consider two cases. If L^{0} ≥ ∑_{i=1}^{L^{0}} x_{i}^{0}/2, then, as before, (for ρ small)

L^{0} ≥ \frac{1}{2} ∑_{u∈U} \binom{d_{u}^{0}}{2} ≥ \frac{1}{20}a^{3}c^{2}\binom{|W |}{2}.

If, on the other hand, L^{0} ≤ ∑_{i=1}^{L^{0}} x_{i}^{0}/2, then

∑_{i} \binom{x_{i}^{0}}{2} ≥ L^{0}\binom{∑_{i} x_{i}^{0}/L^{0}}{2} ≥ \frac{(∑_{i} x_{i}^{0})^{2}}{4L^{0}}

and, so

L^{0} ≥ \frac{\frac{1}{400}a^{6}c^{4}ρ^{4}(n/k)^{4}}{2a^{2}c^{4}ρ^{2}(n/k)^{2}} ≥ \frac{a^{4}}{400}\binom{|W |}{2},

as required.

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, and Edyta Szymańska for providing her desk and her whiteboard. We further thank Van Vu for sending us unpublished preprints and drafts.

References

[1] G. Bennett, Probability inequalities for the sum of independent random variables. J. Amer. Statist. Assoc. 57 (1962), 33–45.

[2] S. Boucheron, G. Lugosi & P. Massart, A sharp concentration inequality with applications. Random Struct. Alg. 16 (2000), 277–292.

[3] P. Erdős & A. Rényi, On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17–61.

[4] E. Friedgut, V. Rödl, A. Ruciński & P. Tetali, Sharp thresholds for Ramsey properties. In preparation.

[5] E. Friedgut, Y. Kohayakawa, V. Rödl, A. Ruciński & P. Tetali, Ramsey games against onearmed bandit. In preparation.

[6] A. Hajnal & E. Szemerédi, Proof of a conjecture of Erdős. Combinatorial Theory and its Applications, Vol. II, Editors P. Erdős, A. Rényi & V.T. Sós, Colloq. Math. Soc. János Bolyai 4, North-Holland, Amsterdam, (1970), 601–623.

[7] W. Hoeffding, Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 (1963), 13–30.

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

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

[10] S. Janson & A. Ruciński, The deletion method for upper tail estimates, Technical report U.U.D.M. 2000:28, Uppsala.

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

[12] C. McDiarmid, On the method of bounded differences. Surveys in Combinatorics (Proceedings, Norwich 1989), London Math. Soc. Lecture Note Ser. 141, Cambridge Univ. Press, Cambridge 1989, pp. 148–188.

[13] C. McDiarmid, Concentration. Probabilistic Methods for Algorithmic Discrete Mathematics, eds. M. Habib, C. McDiarmid, J. Ramirez and B. Reed, Springer-Verlag, Berlin, 1998, pp. 195–248.

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

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

[16] J. Spencer, Counting Extensions. J. Combin. Th. A 55 (1990), 247–255.

[17] M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. 81 (1995), 73–205.

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

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

[20] 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.

[21] V.H. Vu, Concentration of non-Lipschitz functions and applications. To appear in Random Struct. Alg.