{'fraction_non_alphanumeric': 0.07694574892421355, 'fraction_numerical': 0.022616076867152654, 'mean_word_length': 3.7207123643446804, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 32, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Upper tails for arithmetic progressions in random subsets

We study the upper tail of the number of arithmetic progressions of a given length in a random subset of {1,...,n}, establishing exponential bounds which are best possible up to constant factors in the exponent. The proof also extends to Schur triples, and, more generally, to the number of edges in random induced subhypergraphs of `almost linear' k-uniform hypergraphs.


Introduction
What is the (typical) behaviour of a given function depending on many independent random variables ξ j ? This fundamental concentration-of-measure question is of great interest in various areas of pure and applied mathematics, including functional analysis, statistical mechanics, and theoretical computer science. In applications, concentration inequalities are particularly important: these quantify random fluctuations of X = f (ξ 1 , . . . , ξ n ) by bounding the probability that X deviates significantly from its mean EX. During the last decades a wide variety of different methods for proving such inequalities have been developed (see, e.g., [28,13,6]), including martingale based methods [30,27], Talagrand's methodology [42], combinatorial approaches [24], and information theoretic methods [12,5].
Despite this large body of work, in concrete applications our understanding is often still far from satisfactory -even if we restrict our attention to the important case where X is a sum of (dependent) indicator variables and ξ j ∈ {0, 1}. For example, in probabilistic combinatorics the random variable X often counts objects, for instance the number of certain subgraphs in random graphs. Here Janson's and Suen's inequalities [19,20,26,33] usually give sharp estimates for the lower tail P(X ≤ (1 − ε)EX). In contrast, obtaining tight estimates for P(X ≥ (1 + ε)EX) is more delicate, and this 'upper tail problem' is well-known to be a technical challenge (see, e.g., [23,25]).
In fact, in many such counting problems each indicator variable depends only on a few ξ j , in which case X has a special structure: it is a low-degree polynomial of independent Bernoulli random variables. With this in mind, it is surprising that, despite intensive research of Kim and Vu [27,43] and many others (see, e.g., [24,39,45,28,13,6]), there is no concentration inequality that routinely gives the 'correct' upper tail behaviour in these basic situations. Consequently the investigation of these and related problems is an important issue -not only from an applications point of view, but also as a question in concentration-ofmeasure.
In this context, Janson, Oleszkiewicz and Ruciński [22] developed in 2002 a moment-based method that, for subgraph counts in random graphs, gives estimates for P(X ≥ (1 + ε)EX) which are best possible up to logarithmic factors in the exponent. Subsequently, Janson and Ruciński [25] extended this technique so that it also gives comparable estimates for arithmetic progressions in random subsets. To be more concrete, given k ≥ 3, let X be the number of arithmetic progressions of length k in [n] p , the random subset of [n] = {1, . . . , n} where each element is included independently with probability p. In [25] it was shown that for essentially all p and ε > 0 of interest we have exp −C(ε, k) √ EX log(1/p) ≤ P(X ≥ (1 + ε)EX) ≤ exp −c(ε, k) determining, as in [22], the upper tail up to a factor of O(log(1/p)) in the exponent for constant ε. The problem of closing this logarithmic gap in the approach of Janson et al. [22,25] has remained open for several years, and only very recently have there been some breakthroughs by Chatterjee [7] and DeMarco and Kahn [10,11] for certain subgraph counts. In this paper we solve the upper tail problem for a wide class of random variables, including arithmetic progressions and Schur triples, by establishing upper and lower bounds which match up to constant factors in the exponent. For simplicity, we first consider the special case of arithmetic progressions (in Section 1.1 we turn to the general results). In particular, (2) below shows that log P(X ≥ (1 + ε)EX) = −Θ(min{EX, √ EX log(1/p)}) for constant ε, closing the log(1/p) gap that was present until now.
A weakness of Theorem 1 is that is does not guarantee a similar dependence of c(ε) and C(ε) on ε. Although results of this form (see, e.g., [7,11,10,22]) are the widely accepted standard for the 'infamous' upper tail problem [23], here we go much further. Our next result establishes, over a wide range of the parameters, the dependence of the upper tail on ε, up to constants (that are independent of ε). In the language of large deviations, (3) below determines, for p bounded away from one, the order of magnitude of the large deviation rate function log P(X ≥ (1 + ε)EX) for all ε ≥ n −α of interest.
It is not hard to check that Var X = Θ(µ(1 + np k−1 )) for p bounded away from one (see, e.g., Example 3.2 and Lemma 3.5 in [21]). Note that the condition Φ(ε) ≥ 1 is natural since our focus is on exponentially small probabilities. The function ϕ(x) appears in standard Chernoff bounds; it satisfies ϕ(x) = Θ(x log(1 + x)) for x ≥ 0, so that ϕ(x) = Θ(x 2 ) as x → 0. The proof of Theorem 2 shows that the form of the exponent in (3) is determined by Normal approximation considerations (the ϕ(ε)µ 2 / Var X term) and the interval clustering idea (the √ εµ log(1/p) term). The sharp estimates of Theorem 2 are conceptually quite different from previous work on the upper tail problem. Indeed, somewhat related work for subgraph counts in the binomial random graph G n,p (which aims to determine the precise constants in the exponent as n → ∞, see, e.g., [8,9,29]) focuses on the case where ε is constant and p is large (with p = Θ(1) or p ≥ n −δ ). In fact, for moderately large p, our next result completely resolves the qualitative behaviour of the upper tail.
Finally, as the reader can guess, in Theorem 2 and 3 various conditions (for ε and p) are not best possible. However, for ease of exposition we defer more precise results to the next section, where we state our more general tail estimates (which include Theorems 1-3 as special cases or corollaries). Here we just mention that there is a tradeoff between p and t = εµ in Theorem 2 and 3. Indeed, Theorem 2 works for all 0 < p ≤ 1 − γ, but (3) is restricted to deviations of form ε ≥ n −α (for some fixed α > 0). By contrast, Theorem 3 requires n −1/(k−1)+o(1) ≤ p ≤ 1 − γ, but (4) applies to essentially all exponentially small deviations t > 0 (note that Ψ(t) ≤ 1 for t ≤ √ Var X).

Counting edges of random induced subhypergraphs
In this section we present the main results of this paper, Theorem 4 and 6, which resolve the upper tail problem (up to constant factors in the exponent) for a large class of random variables, including arithmetic progressions and Schur triples. We shall phrase our results in the language of random induced subhypergraphs.
Note that H = H n encoding k-term arithmetic progressions in [n] is of this form (see also Remark 5 below). Under the aforementioned conditions, Janson and Ruciński [25] proved that the upper tail of X = e(H p ) is of type (1), leaving a log(1/p) gap between the upper and lower bounds for constant ε (see Theorem 2.1 in [25] with q = 2). The following theorem rectifies this issue, by closing the gap.
Turning to applications, using Remark 5 it is easy to see that Theorem 4 applies to the number of arithmetic progressions of length k in [n] p , and so implies Theorem 1. The assumptions of Theorem 4 are also satisfied by Schur triples, which are classical objects in Number theory and Ramsey theory (see, e.g., [17,37] and [16,38]): in this case H = H n contains all 3-element subsets {x, y, z} ⊆ [n] satisfying x + y = z. A similar remark applies to the more general notion of ℓ-sums (studied, e.g., in [2,35]), where the 3-element subsets {x, y, z} ⊆ [n] satisfy x + y = ℓz. Finally, the arguments in Section 2.1 of [25] reveal that Theorem 4 also applies to the number of integer solutions of certain homogeneous linear systems of equations with rank k − 2.
In the above assumptions (a)-(c) and (i)-(iii), the use of µ and Λ is convenient for applications (see, e.g., (11) below), while Var X seems more insightful from a conceptual point of view. In particular, since we are interested in exponentially small probabilities, by central limit theorem considerations a natural target assumption is t ≥ √ Var X, say. We now discuss the lower bound (10) of Theorem 6, which tends to have fewer applications. Indeed, for our purposes (10) is mainly important from a concentration-of-measure perspective, since it rigorously proves that our upper bound (9) is sharp in a wide range. In view of (i)+(iii), our lower bound (10) only falls short of the target assumption t ≥ √ Var X for p ∈ n −2/(k+1/3) , n −1/(k−1) , where t ≥ (Var X) 2/3 (log n) 2/3 suffices by (ii). Perhaps surprisingly, these gaps are solely due to lacking lower bounds of sub-Gaussian type (note that the variance undergoes a transition around p 0 = n −1/(k−1) by Remark 7), which until now have been widely ignored in the upper tail literature (see, e.g., [43,47]). Here our current approaches seem not strong enough to work for all relevant p and t. We leave it as an open problem to develop a generic method for obtaining suitable sub-Gaussian type lower bounds (see Section 4.2). Finally, we also conjecture that the upper tail estimates (9)-(10) remain valid for all p ∈ (0, 1 − γ] and t ≥ √ Var X. Turning to the remaining applications stated in the introduction, Theorem 3 for arithmetic progressions follows easily by combining (a)+(iii) of Theorem 6 with Remarks 5, 7 and 8. For Theorem 2 we use that, modulo obvious assumptions, the tail estimates (9)-(10) both apply if t > 0 satisfies, say, (Using (a)+(i) for p ≤ n −2/(k+1/3) , (b)+(ii) for larger p < n −1/(k−1) (log n) 1/(k−1) , and (a)+(iii) otherwise.) As µ ≥ an 2 p k and Λ = µ(1 + np k−1 ), a short calculation reveals that, say, t ≥ µn −1/(5k+1) implies (11) for all n ≥ n 0 (k, a) and p ∈ (0, 1]. Hence, using Remarks 5 and 7, inequality (3) of Theorem 2 follows. The proofs of the upper and lower bounds of Theorem 4 and 6 are based on completely different techniques. For the upper bounds (6) and (9), the most important ingredients are two new concentration inequalities of Chernoff-type, which we prove in Section 2. These allow us to combine and extend the combinatorial and probabilistic ideas used in the 'deletion method' and the 'approximating by a disjoint subfamily' technique of Janson and Ruciński [24] and Spencer [41,23], respectively. The idea of applying the BK-inequality of van den Berg and Kesten [4] and Reimer [32] in the context of the 'infamous' upper tail problem [23] may perhaps also be of independent interest. For the lower bounds (7) and (10), we analyze three different mechanisms that yield deviations of X = e(H p ), and with some care (using, e.g., Harris' inequality [18] and the Paley-Zygmund inequality) we recover the correct dependence of the exponent on t = εµ.
The remainder of this paper is organized as follows. In Section 2 we introduce our new concentration inequalities, and in Section 3 we apply them (together with combinatorial arguments) to prove the upper bounds of Theorem 4 and 6. Finally, in Section 4 we establish the corresponding lower bounds (and also prove Remark 8).

Concentration inequalities
In this section we introduce our main probabilistic tools: two concentration inequalities which essentially state that Chernoff-type upper tail estimates hold whenever X is bounded from above by a sum of random variables with 'well-behaved dependencies'. They develop ideas of Janson and Ruciński [24], Erdős and Tetali [14], and Spencer [41], and seem of independent interest. On first reading of Theorem 9 it might be useful to consider the special case where there are independent random variables (ξ i ) i∈A such that each Y α ∈ {0, 1} with α ∈ I is a function of (ξ i ) i∈α . Then, defining α ∼ β if α ∩ β = ∅, it is immediate that the independence assumption holds (as α ∼ β implies that Y α and Y β depend on disjoint sets of variables ξ i ). Now, consider X = α∈I Y α with µ = EX, J = I and C = max β∈I |{α ∈ I : α ∼ β}|. Then X = Z C , where max β∈J α∈J :α∼β Y α ≤ C intuitively corresponds to a Lipschitz-like condition. With this in mind, part of the power of (12) is that the exponent scales with 1/C (instead of the usual 1/C 2 ), and that the Lipschitz condition need not hold deterministically (it suffices if X ≤ Z C or X ≈ Z C holds off some exceptional event).
Theorem 9. Given a family of non-negative random variables (Y α ) α∈I with α∈I EY α ≤ µ, assume that ∼ is a symmetric relation on I such that each Y α with α ∈ I is independent of {Y β : β ∈ I and β ∼ α}. Let Z C = max α∈J Y α , where the maximum is taken over all J ⊆ I with max β∈J α∈J :α∼β Y α ≤ C. Set ϕ(x) = (1 + x) log(1 + x) − x. Then for all C, t > 0 we have Remark 10. Theorem 9 remains valid after weakening the independence assumption to a form of negative Theorem 9 extends several upper tail inequalities discussed in the survey of Janson and Ruciński [23]. Indeed, consider X = α∈I Y α with µ = EX and J = I. For independent Y α ∈ [0, 1] we have X = Z 1 (note that α ∼ α for non-constant Y α ), so that (12) reduces to the classical Chernoff bound, see, e.g., Theorem 2.1 in [21]. Similarly, for generic Y α ∈ [0, 1] with dependency graph G = G(I), where distinct α, β ∈ I = V (G) form an edge if α ∼ β (cf. Section 2.6 in [23]), we have X = Z ∆1(G)+1 . Hence (12) improves Theorem 5 in [23], which is based on the 'breaking into disjoint matchings' technique of Rödl and Ruciński [34]. Furthermore, using C = t/(2r) it is easy to see that Theorem 9 tightens Theorem 2.1 in [24], i.e., the basic theorem of the 'deletion method' of Janson and Ruciński. In addition, (12) extends Lemma 2 in [23], i.e., the main probabilistic ingredient of Spencer's 'approximating by a disjoint subfamily' technique [41]. Theorem 9 is also related to a concentration inequality of Chatterjee [7]; our assumptions are less technical and subjectively easier to check (e.g., readily implying Proposition 4.1 in [7] via C = 3εℓnp). Remark 10 is useful in the context of the uniform random graph G n,m (and related uniform models). To illustrate this we consider In that case it is well-known (and not hard to check) that the negative correlation condition of Remark 10 holds, demonstrating that Theorem 9 applies to G n,m .
Proof of Theorem 9. The proof is based on a variant of the m-th factorial moment which 'forces independence'. In fact, we closely follow Lemma 2.3 in [24] and Lemma 2.46 in [21], but differ in some important details. Assume that m ∈ N satisfies 1 ≤ m ≤ ⌈(µ + t)/C⌉. For all K ⊆ I and s ∈ N with s ≥ 1 we define where * (α1,...,αs)∈K s denotes the sum over all tuples (α 1 , . . . , α s ) ∈ K s satisfying α i ∼ α j for i = j. The key point is that, by construction, the factors Y αi ≥ 0 in each term of M s (K) are independent. Hence Now assume that Z C ≥ µ+t and Z C = α∈J Y α hold. Note that, by construction, which by induction yields M m (J ) ≥ m−1 j=0 (µ + t − Cj).
Combining the above estimates for M m (I) ≥ M m (J ) and EM m (I) with Markov's inequality, we obtain Set m = ⌈t/C⌉ ≥ 1. If µ = 0, then P(Z C ≥ µ + t) = 0 by (15), and (12) is trivial, so we henceforth assume for x ≥ 0 (see, e.g., the proof of Theorem 2.1 in [21] , which establishes (12). For all integers x ≥ 1, by formally defining xC = µ + t and m = x in the above proof (so that µ + t − Cj = C(x − j) holds), note that inequality (15) and Stirling's formula imply While this estimate is often weaker than (12), for C = 1 it extends, in the upper tail context, the so-called 'disjointness lemma' of Erdős and Tetali [14], see, e.g., Lemma 8.4.1 in [1]. In the proof of Theorem 9, inequality (13) is the only step in which anything is assumed about the Y α , and independence is used in a limited way: E( Y αi ) ≤ E(Y αi ) suffices (in fact, replacing the assumption EY α ≤ µ with λ α ≤ µ and λ α ≥ 0, it suffices if E( Y αi ) ≤ λ αi holds). This suggests that the argument is rather robust, since, e.g., ad-hoc upper bounds for E( Y αi ) are enough to obtain tail inequalities, see the proof of Lemma 4.5 in [44]. Finally, in (14) there is also potential for relaxing max β∈J α∈J :α∼β Y α ≤ C to an accumulative condition (e.g., replacing Cs by t/2).
The following variant of Theorem 9 exploits the BK-inequality [4] to further relax the independence assumption. Clearly, two events E 1 , E 2 depending on disjoint sets of independent random variables are independent. For our purposes it intuitively suffices if, for each possible outcome ω ∈ Ω, we can 'certify' the occurrence of E 1 and E 2 by disjoint sets of variables (which may depend on ω).
[ω] K ⊆ E, then ω| K is called a certificate for the occurrence of the event E (in words, E occurs on all sample points that agree with ω restricted to K). Intuitively speaking, in Theorem 11 the random variable Z counts the maximum number of events that 'occur disjointly', i.e., have disjoint certificates. With this in mind, a key feature of inequalities (12) and (17) is that they are dimension-free: they do not involve the sizes of the certificates (in contrast to 'certificate-based' variants of Talagrand's inequality such as Theorem 2 in [31]). (12) and (17) hold with C = 1 and Z 1 = Z.
Remark 12. Theorem 11 remains valid after weakening the product space assumption: restricting to increasing events E α ⊆ Ω = {0, 1} M , it suffices if P satisfies the BK-inequality (18) for increasing events (in this case is associative, so we may replace Z by the maximum of |J | over all J ⊆ I for which α∈J E α holds).
The proof of Theorem 11 is based on the BK-inequality, which is a partial converse to Harris' inequality [18]. Intuitively, A B means that the events A and B have disjoint certificates. Formally, we define which need not be associative. The general BK-inequality of Reimer [32] states that for any product space Ω = Ω 1 × · · · × Ω M , with finite Ω i , the following holds: for any two events A, B ⊆ Ω we have Proof of Theorem 11. The proof uses a -based variant of the m-th moment (inspired by Theorem 9). For Using the BK-inequality (18) inductively, we obtain P(D(α 1 , . . . , α m )) ≤ i∈[m] P(E αi ). So, analogous to (13), Let Z 1 = Z and C = 1. With y = µ + t, the proof of Theorem 9 carries over unchanged from (15) onwards, and (12) follows. Similarly, with y = x, m = x and µ + t = x, (15) establishes (17).
The sufficient condition of Remark 12 has recently been established in [3] for P assigning equal probability to all ω ∈ {0, 1} M with exactly k ones. Hence Theorem 11 applies to G n,m and related uniform models.

Upper bounds
In this section we establish the upper bounds (6) and (9) of Theorem 4 and 6. The executive summary of our proof strategy is as follows: using combinatorial arguments we shall approximate X = e(H p ) using several 'well-behaved' auxiliary random variables, which we in turn estimate by the concentration inequalities of Section 2. Of course, the actual details are much more involved, and our arguments in fact develop combinatorial and probabilistic ideas of the 'deletion method' [24] and the 'approximating by a disjoint subfamily' technique [41,23]. We have added a substantial amount of informal discussion and motivation to the remainder of this section, in an attempt to make the underlying ideas and techniques more accessible (the actual proofs could be recorded in a much shorter way). For example, in order to milden some of the technical difficulties, we shall not only informally discuss the intriguing log(e/p) factors in the exponent, but also prove (6) using a simplified version our arguments (instead of proving (6) and (9) in a unified way).
The remainder of this section is organized as follows. In Section 3.1 we motivate parts of our proof strategy, and illustrate how logarithmic terms arise in our tail estimates. In Section 3.2 we then present our basic proof framework, and establish the upper bound of Theorem 4. Finally, in Section 3.3 we refine the aforementioned framework, and prove the more involved upper bound of Theorem 6.

Warming up
The upper bounds of Theorem 4 and 6 involve exponentially small probabilities, so error probabilities of form o(1) are too crude for our purposes (and the proofs require more care). In fact, the exponents in (6) and (9) are fairly involved, and both contain somewhat unusual log(e/p) terms. With these non-standard features in mind, the goals of this informal section are two-fold: (i) to motivate some details of our upcoming proof strategy, and (ii) to illustrate the way in which we eventually obtain the log(e/p) factors.

Motivation and preliminaries
Let us start with a basic estimate for the number of induced edges X = e(H p ). For brevity we set Clearly, for all r > 0 we have A similar decomposition forms the basis of the inductive 'deletion method' of Janson and Ruciński [24], see, e.g., Theorem 2.5 and Section 3 in [24]. The inductive approach of Kim and Vu [27] is also based on a related idea, see, e.g., Section 3.2 in [43]. One bottleneck of the above approach (19) is that it relies on a uniform upper bound on the degree of all vertices. We shall rectify this issue via the following sparsification strategy (which allows for some vertices with larger degrees): we first decrease the maximum degree of H p by removing some carefully chosen edges, and then estimate the number of remaining edges via the Chernoff-type tail inequality Theorem 9. In other words, our plan is to first apply further combinatorial arguments to H p , before using any probabilistic tail estimates or induction. An embryonic version of this idea is contained in the 'approximating by a disjoint subfamily' technique of Spencer [41,23], but Janson and Ruciński argued in their upper tail survey [23] that this technique is 'never better' than the 'deletion method' [24] (see Remark 2 in Section 2.3.4 and Example 7 in Section 3.2 of [23]). In Sections 3.2-3.3 we shall, in some sense, crossbred ideas of both approaches to go one step further.

Extra logarithmic factors in tail estimates?
Let us illustrate how extra logarithmic factors can arise in our upper tail estimates. To this end we shall now have, in the context of Theorem 4, a heuristic look at the exponential decay of the degrees |Γ v (H)|. Here the key observation is that the dependencies among the edges in where we used |Γ v (H)| ≤ |V (H)| · ∆ 2 (H) = O(n) for the last inequality. As expected, the decay of |Γ v (H p )| turns out to be very similar to (20). Indeed, ignoring a number of technicalities, we later approximately show (see (37) in the proof of Lemma 17) that for a certain range of x we have With this in mind, the basic idea for 'extra' logarithmic terms is simple: if x ≫ ynp k−1 holds, then (21) suggests significantly, then we should win a logarithmic factor in the exponent. In Sections 3.2-3.3 we shall exploit the aforementioned 'overshooting' phenomenon for a range of different degrees (to intuitively show that there are not too many vertices with high degrees). Of course, using this approach we shall eventually need to check a number of technical conditions such as np k−1 /x = O p Θ(1) : these are key for obtaining the log(e/p) factors missing in previous work of Janson and Ruciński [25].

Basic proof framework
In this section we introduce our basic proof framework (for arbitrary hypergraphs H), which seems of independent interest. In the combinatorial part we implement the sparsification idea mentioned in Section 3.1.1, and essentially show the number of induced edges X = e(H p ) can be estimated via two carefully defined auxiliary random variables X r = X r (H p ) and M r = M r (H p ). In the probabilistic part we systematically obtain upper tail estimates for X r and M r , by exploiting the Chernoff-type concentration inequalities of Section 2. Finally, we demonstrate the applicability of this framework by proving the upper bound of Theorem 4.
Recall that our strategy is to decrease the maximum degree of H p by removing edges. To estimate the upper tail of the remaining edges, we now introduce the following 'smooth approximation' of X = e(H p ): In words, X r = X r (H p ) denotes the maximum number of edges in any subhypergraph G ⊆ H p with maximum degree at most r. Via Theorem 9 this 'bounded degree' property eventually yields (23), i.e, a general upper tail estimate for X r . For ε = Θ(1) and k = Θ(1), note that (23) yields P(X r ≥ (1 + ε/2)µ) ≤ exp(−Θ(µ/r)).
Then, for all p ∈ [0, 1] and r, t > 0 we have The main observation required to deduce Lemma 13 from Theorem 9 is that every edge f ∈ G ⊆ H is incident to at most k∆ 1 (G) other edges of G. This allows us to bring the Lipschitz-like condition of Theorem 9 into play (with C = kr).

Proof of Lemma 13. Defining
Hence, by the discussion preceding Theorem 9, the independence assumption of Theorem 9 holds (here the Hence, for C = kr we deduce X r ≤ Z C , where Z C is defined as in Theorem 9 with I = H. So, using (12), and it remains to rewrite this estimate. Since (16) implies (by distinguishing the cases x ≥ 1 and x ≤ 1) that we see that (23) follows if ϕ(t/(2µ)) ≥ ϕ(t/µ)/4. To sum up, it suffices to prove that for Our sparsification strategy intuitively focuses on high-degree vertices (with degree at least r). To quantify the number of removed edges, we shall introduce the auxiliary variable M r = M r (H p ), which essentially counts high-degree vertices with 'disjoint certificates' (in the sense of Section 2). More precisely, we call S = (v, W ) an r-star in G if W = {f 1 , . . . , f ⌈r⌉ } ⊆ Γ v (G) and |W | = ⌈r⌉. We write V (S) = 1≤i≤⌈r⌉ f i , which contains all vertices of the r-star S. Note that V (S) ⊆ V p (H) implies |Γ v (H p )| ≥ ⌈r⌉, i.e., that vertex v has degree at least ⌈r⌉. Writing T r (G) for the collection of all r-stars S = (v, W ) in G, we define In words, M r (H p ) denotes the size of the largest vertex disjoint collection of r-stars in H p , i.e., r-star matching.
(As indicated earlier, it might be useful to think of M r (H p ) as the maximum number of degree ≥ r vertices that 'occur disjointly'.) For future reference we note the following basic relation between ∆ 1 (H p ) and M r (H p ).
The following combinatorial lemma is at the heart of our basic sparsification strategy: it intuitively relates X = e(H p ) with the auxiliary random variables X r and M r (H p ). In fact, inequality (27) below is inspired by the main deterministic ingredient of the 'approximating by a disjoint subfamily' technique (see, e.g., Lemma 3 in [23], which is used to count vertices in an auxiliary graph with V (G) = H p ). While Spencer's technique hinges on the fact that disjoint edges are nearly independent (see also [41,14]), here one important conceptual difference is that we allow for dependencies, i.e., overlaps of the edges (via r ≥ 2 in X r ). For our applications the crux of (27) is that X r < (1 + ε/2)µ and k⌈r⌉M r (H p )∆ 1 (H p ) < εµ/2 together imply X < (1 + ε)µ.
Lemma 15. Suppose that H satisfies max f ∈H |f | ≤ k. Then, for all p ∈ [0, 1] and r > 0 we have The proof idea is simple: if M ⊆ T r (H p ) attains the maximum in the definition of M r (H p ), then after removing all edges incident to some star S = (v, W ) ∈ M we obtain a hypergraph G with maximum degree at most ⌈r⌉ − 1 ≤ r (otherwise we could add another r-star to the vertex disjoint collection M), so e(G) ≤ X r . Inequality (27) combines this observation with trivial estimates for the number of removed edges.
Proof of Lemma 15. The lower bound X = e(H p ) ≥ X r is immediate. For the upper bound, note that X = X r whenever ∆ 1 (H p ) ≤ r, so we may henceforth assume ∆ 1 (H p ) > r. We fix some M ⊆ T ⌈r⌉ (H p ) which attains the maximum in (26), so M r (H p ) = |M|. We remove all edges from H p which contain at least one vertex from (the edges of) some r-star S = (v, {f 1 , . . . , f ⌈r⌉ }) ∈ M, and denote the remaining hypergraph by G. As every edge contains at most max f ∈H |f | ≤ k vertices, we removed at most e(H p )−e(G) ≤ |M| · ⌈r⌉k · ∆ 1 (H p ) edges from H p . Clearly ∆ 1 (G) ≤ ⌈r⌉ − 1 ≤ r, because otherwise we could add another r-star to M (contradicting maximality). Hence G contains at most e(G) ≤ X r edges, and (27) follows.
Next, we shall exploit the disjoint-like structure of M r (H p ) via the BK-inequality based Theorem 11. This leads to (28), a generic upper tail estimate for the size of the largest r-star matching M r (H p ). Note that P( In this paper we mainly have very unlikely degrees in mind, where Φ r ≤ Q −r for some Q > 1. Then the probability that at least y of such high-degree vertices (with degree at least r) 'occur disjointly' is roughly at most Q −ry by (28) below.

Lemma 16.
Given H, for all p ∈ [0, 1] and y, r > 0 we have The main idea is very intuitive: if M ⊆ T r (H p ) attains the maximum in the definition of M r (H p ), then H p contains |M| vertex disjoint stars S v = (v, W ) ∈ M, each of which 'certifies' that the corresponding vertex v has degree at least ⌈r⌉ in H p (in the sense of Section 2). Hence M r (H p ) = |M| events of form E v = {|Γ v (H p )| ≥ ⌈r⌉} 'occur disjointly', which allows us to bring (17) of Theorem 11 into play (with C = 1).
Proof of Lemma 16. We claim that M r (H p ) ≤ Z for Z = Z 1 as defined in Theorem 11 with I = V (H), where E v denotes the event that |Γ v (H p )| ≥ ⌈r⌉. This claim implies P(M r (H p ) ≥ y) ≤ P(Z ≥ y) ≤ P(Z ≥ ⌈y⌉), and we then deduce (28) by applying (17) with C = 1.
To establish M r (H p ) ≤ Z, we pick any M ⊆ T r (H p ) which attains the maximum in (26), so that In other words, the presence of the vertices V (S v ) ⊆ V p (H) constitutes a certificate for the event E v (using the notation of Section 2, we have [ω] V (Sv ) ⊆ E v ). By definition of M r (H p ) these certificates V (S v ) Sv∈M are all disjoint, so Z ≥ |M| = M r (H p ), as claimed.
To summarize our proof framework: Lemmas 13-16 apply to arbitrary hypergraphs H with max f ∈H |f | ≤ k, and they basically reduce the upper tail problem for X = e(H p ) to the upper tail problem for the degrees of H p , i.e., to Φ x = v P(|Γ v (H p )| ≥ ⌈x⌉); see also (29) below. (These ideas are developed further in [46].) In general, by noting P(|Γ v (H p )| ≥ ⌈x⌉) ≤ P(|Γ v (H p )| ≥ ⌈x⌉ | v ∈ V p (H)) there is room for induction (on the number of vertices per edge), analogous to [24,27]. However, for the purposes of Theorem 4 and 6 it seems easier to exploit the codegree condition ∆ 2 (H) = O(1) more directly (see the proof of Lemma 17).

Sketch of the upper bound of Theorem 4
In this section we sketch the proof of upper bound of Theorem 4, illustrating the discussed proof framework. As we shall see, the desired 'overshooting' phenomenon (which yields the extra log(e/p) factor in the exponent) arises naturally. First, using Lemma 15, for all r, y, z > 0 satisfying ½ {y>1} k⌈r⌉yz ≤ εµ/2 we obtain (To clarify: for the indicator ½ {y>1} we exploited that M r (H p ) < 1 implies M r (H p ) = 0, which in turn entails ∆ 1 (H p ) < r.) Turning to further estimates of the right-hand side of (29), for ε = Θ(1) Lemma 13 yields This suggests that, in order to 'match' the exponent of our target bound (6), we should pick It later turns out, see (45), that this natural choice satisfies np k−1 /r = o(p 1/4 ) for k ≥ 3 (this fails for k = 2). In view of (21), we thus expect to obtain an extra log(e/p) factor in the exponent for x ≥ r: By Lemma 16 it thus seems plausible that for x ≥ r we have Combining our heuristic findings with Lemma 14, for ε = Θ(1) and z ≥ r we thus expect that P(X ≥ (1 + ε)µ) ≤ exp −Θ µ/r + exp −Θ ry log(e/p) + ½ {y>1} exp −Θ z log(e/p) .
To 'match' the exponent of our target bound (6), in view of (30) it seems natural to set y = z/r and z = εµ/(4k), say. In fact, these choices also satisfy two further technical conditions used above. Namely, that k⌈r⌉yz ≤ 2kryz = 2kz 2 ≤ εµ/2 holds, and that y > 1 implies z ≥ r. Hence, if r is chosen as in (30), then for ε = Θ(1) and µ ≥ 1 we expect that which 'matches' the target bound (6) of Theorem 4. With hindsight, the freedom that via M r (H p ) we can pick z ≫ r in (29) seems key for going beyond the more basic decomposition (19).

Proof of the upper bound of Theorem 4
In this section we follow our heuristic proof sketch, and establish the upper bound of Theorem 4. We start with the size of the largest r-star matching M r (H p ), and make the upper tail estimate (32) rigorous via Lemma 17 below (its statement is formulated with an eye on on the upcoming proof of Theorem 6, where the n 2 (max{y, 1}) 3/2 ≥ 1 term facilitates union bound arguments). The technical assumption (35) intuitively ensures that vertices with degree at least r are sufficiently concentrated (recall that the expected degree should be O(np k−1 ), see the discussion in Section 3.1.2). For example, r = C(1 + np k−1 ) satisfies (35) when np k−1 ≥ log n or np k−1 ≤ n −γ for C = C(γ, B, k, D) sufficiently large, but for np k−1 ≈ 1 a somewhat larger choice of r seems necessary (unless we impose additional constraints on y in (36) below). By the heuristics of Section 3.2.1, for r as defined in (30) we expect that np k−1 /x ≤ p 1/4 holds in inequality (36), i.e., as in (32) we should gain an extra logarithmic factor in the exponent of the upper tail by 'overshooting'.
Lemma 17. Given k ≥ 2, a > 0 and D ≥ 1, let H = H n be a k-uniform hypergraph satisfying v(H) ≤ Dn and ∆ 2 (H) ≤ D. Then there are B, n 0 ≥ 1 (depending on k, D), such that for all n ≥ n 0 , p ∈ [0, 1], r > 0 satisfying Bnp k−1 /r r ≤ n −8kD (35) the following holds. For all x ≥ r and y > 0 we have Our plan is to deduce Lemma 17 from inequality (28) (20)- (21). This line of reasoning can easily be made rigorous via Theorem 9, but below we take a more direct combinatorial route (which suffices for our purposes).
Proof of Lemma 17. It suffices to prove that for all x ≥ r and n ≥ n 0 (D) we have Indeed, since y > 0 implies ⌈y⌉ ≥ max{y, 1}, by applying (28) of Lemma 16 it then follows that In the remainder we verify inequality (37), by focusing on combinatorial implications of the degree event |Γ v (H p )| ≥ ⌈x⌉. To this end we pick a subset W ⊆ Γ v (H p ) of the edges which is size maximal subject to the restriction that all edges of W are vertex disjoint outside of the centre vertex v, i.e., that all distinct edges f i , f j ∈ W satisfy (f i ∩ f j ) \ {v} = ∅. Note that for every edge e ∈ Γ v (H p ) there are a total of (including e itself) at most k∆ 2 (H) ≤ kD = C edges f ∈ Γ v (H p ) with (f ∩ e) \ {v} = ∅ (because all such edges f contain v and at least one vertex from e \ {v}). Hence, Since the union of all edges in W contains exactly | f ∈W f | = 1 + (k − 1)|W | vertices, it follows that Defining B = e 3 D 4 C 2 , using C = kD, x ≥ r, and the assumption (35) it follows that .
For the interested reader we remark that from the above proof idea it, e.g., also directly follows that which can alternatively be used to derive (36). We find our general BK-inequality based approach more informative and flexible (e.g., with respect to possible extensions and generalizations, see [46]).
We are now ready to prove the upper bound of Theorem 4. Below we shall first pick r as in (30), and then closely mimic the heuristic considerations (33)-(34) of Section 3.2.1. Only afterwards we verify np k−1 /r = O(p 1/4 ), the technical condition (35), and the heuristic tail inequality (32).
In the remainder we verify the claimed estimate (42). Our below proof is based on Lemma 17, which requires us to check the technical condition (35). Calculus shows that Using r ≥ A √ µ/2, µ = e(H)p k ≥ an 2 p k , and k ≥ 3 (this is the only time k ≥ 2 is not enough), we obtain which also implies r ≥ eBnp k−1−γ . Observe that p ≥ n −1/(2k) implies r ≥ n 1/2 , say, and that p ≤ n −1/(2k) implies p γ ≤ n −γ/(2k) . Using r ≥ A, for n ≥ n 0 (k, D) we thus infer

Some refinements (proof of the upper bound of Theorem 6)
In this section we refine our basic proof framework, and establish the more precise upper bound (9) of Theorem 6. Recall that the exponent of (9) is essentially either of sub-Gaussian type exp −ct 2 / Var X or clustered type exp −c √ t log(1/p) ; see also (8). Heuristically speaking, the corresponding phase transition near (Var X) 2/3 causes some technical difficulties for the approach taken in Section 3.2 (for p ≥ n −1/(k−1)+o (1) it turns out that sharp tail estimates are easier when t is far away from (Var X) 2/3 ). Here one bottleneck is Lemma 15, which on an intuitive level only distinguishes between two ranges of the degrees: smaller and larger than r. In this section we shall rectify this issue, by distinguishing between a wide range of different degrees.
More concretely, our refined sparsification strategy is to iteratively decrease the maximum degree of H p , until we are able to bound the number of remaining edges by X r as defined in (22). Using the convention N = {0, 1, . . .}, we shall eventually implement this strategy via T (β, γ, r, t), which is the event that where we tacitly used the following convenient parametrization: (The intricate form of (46)-(47) is hard to digest on first sight; both events are based on a delicate interplay between the combinatorial and probabilistic estimates in the upcoming proofs of Lemma 18 and 19.) The following combinatorial lemma intuitively states that X ≈ X r whenever T (β, γ, r, t) holds.
The idea is to iterate the proof of Lemma 15: using the resulting hypergraph sequence H p = G J ⊇ · · · ⊇ G 0 we shall estimate X = e(H p ) in terms of the step-wise differences: The definition of T (β, γ, r, t) then ensures that 0≤j<J [e(G j+1 ) − e(G j )] ≤ t/2 and e(G 0 ) ≤ X r hold.
Proof of Lemma 18. The lower bound X = e(H p ) ≥ X r is trivial, so we henceforth focus on the upper bound. Let J be the smallest integer J ≥ 0 with r J ≥ √ t. We now construct the sequence (G j ) 0≤j≤J with G J = H p and ∆ 1 (G j ) ≤ ⌊r j ⌋. For G J = H p , observe that (47) Given G j+1 with 0 ≤ j < J, we fix some M ⊆ T ⌈rj ⌉ (G j+1 ) which attains the maximum in (26), so that |M| = M rj (G j+1 ) ≤ M rj (G J ) = M rj (H p ) by monotonicity. We remove all edges from G j+1 which contain at least one vertex from some r j -star S ∈ M, and denote the resulting hypergraph by G j . Hence ∆ 1 (G j ) ≤ ⌈r j ⌉ − 1 ≤ ⌊r j ⌋, because otherwise we could add another r j -star to M (contradicting the maximality of |M|).
Next we estimate X = e(H p ) in terms of the hypergraph sequence (G j ) 0≤j≤J . Since each r j -star consists of ⌈r j ⌉ edges, for 0 ≤ j < J it follows by construction and monotonicity (using M rj (G j+1 ) ≤ M rj (H p ), ⌈r j ⌉ ≤ r j + 1 ≤ 2r j and ∆ 1 (G j+1 ) ≤ r j+1 = 2r j ) that Hence, using H p = G J , (46)- (47) and max 0≤j<J r j ≤ √ t we readily obtain For any z > 0, in view of r j = 2 j r it is easy to see that j∈N:rj ≤z Thus, noting that ∆ 1 (G 0 ) ≤ ⌊r 0 ⌋ ≤ r implies e(G 0 ) ≤ X r , using β ≤ 1/(32k) it follows that X ≤ e(G 0 ) + 16βkt ≤ X r + t/2, completing the proof.
In view of Lemma 13 and 18, we now focus on the probability of the event ¬T (β, γ, r, t). Ignoring some technical assumptions (which are similar to those of Lemma 17), the following result essentially states that P(¬T (β, γ, r, t)) is negligible for our purposes (the 1/n prefactor in (50) is ad-hoc, and eventually becomes the usually irrelevant n −1 term in (9) of Theorem 6).
We are now ready to prove the upper bound of Theorem 6, and our main remaining task is to pick a suitable parameter r. Here the technical condition (35) prevents the natural choice r = CΛ/µ = Θ(1+np k−1 ) when np k−1 ≈ 1, which explains the more involved form of r in the next proof (this complication is only needed in the pedestrian case (iii) below).

Lower bounds
In this section we establish the lower bounds (7) and (10) of Theorem 4 and 6. The proofs are based on three different 'configurations' of the vertices in V p (H), which each yield a distinct lower bound for the upper tail of X = e(H p ). The heuristic idea is that one of them should hopefully always approximate the most likely way to obtain X ≈ (1 + ε)µ or X ≈ µ + t, respectively. In brief, we shall use configurations where many edges cluster on few vertices (Section 4.1), where many edges arise disjointly (Section 4.2), or where there are overall too many vertices (Section 4.3). Here one main novelty is on a conceptual level: in contrast to previous work we obtain, in a wide range, the correct dependence on t = εµ.

Configurations with clustering
The first lower bound is based on property X(H, D, x) defined in (5), which intuitively states that many edges can cluster on comparatively few vertices. In other words, enforcing W ⊆ V p (H) for a reasonably small set of vertices W is enough to guarantee that the number of induced edges X = e(H p ) = e(H[V p (H)]) is fairly large. A related approach was taken in [25] and [22] for arithmetic progressions and subgraphs, respectively.
Using a new 'local' variant of the above argument we now improve the √ µ + t in the exponent of (65) to √ t, which is crucial when t = o(µ). The basic idea is to 'create' at least µ + t edges as follows: (i) first we use the above clustering construction to 'locally' enforce, say, 2t edges, and (ii) then we use correlation inequalities and a one-sided version of Chebyshev's inequality to show that typically at least µ − t of the remaining r = e(H) − 2t edges are present in H p . (The crux is that the expected number of remaining edges is at least rp k = µ − 2tp k .) This approach seems of independent interest, and a similar reasoning can, e.g., be used to refine the lower bounds for subgraph counts obtained by Janson, Oleszkiewicz and Ruciński [22]. Var X, √ Λ} satisfying X(H, D, min{λt, µ + t}) and µ + t ≥ 1 we have We remark that the form of the somewhat strange-looking assumption t ≥ ½ {µ≥1/2} min{ √ Var X, √ Λ} will be convenient later on. Before giving the proof of Theorem 21, let us informally discuss the structure of the argument. The clustering construction intuitively 'marks' a set of 2t edges in H. Let Z denote the number of 'unmarked' edges that occur in H p , so EZ = (e(H) − 2t)p k = µ − 2tp k . The punchline is that the clustering construction (which enforces the 2t 'marked' edges) allows us to shift our focus from the unlikely event X ≥ EX + t to the 'typical' event Z ≥ EZ − t/2. Indeed, it turns out that, using Harris' inequality [18] and µ = EZ + 2tp k , for suitable W ⊆ V (H) with |W | = O( √ t) and e(H[W ]) ≥ 2t we eventually arrive at It seems plausible that Var Z = O(Var X) holds. A folklore variant of the Paley-Zygmund inequality states that, given any random variable Y ≥ 0, for all 0 ≤ t < EY we have So, assuming p ≤ 1/2 (which implies 2p k ≤ 1/2 for k ≥ 2), for t ≥ √ Var X we should intuitively obtain The proof below makes this reasoning rigorous, but there are a number of subtle issues (which make the details somewhat cumbersome). For example, the parameter t may be very small, so we can not, as usual, ignore rounding issues. Furthermore, to allow for p ≤ 1 − α we need to plant λt copies (instead of just 2t copies) for carefully chosen λ = λ(α, k) > 0. In addition, the W ⊆ V p (H) based construction does not work if λt is larger than the total number of edges e(H), so we shall only enforce min{λt, µ + t} copies.
Proof of Theorem 21. We defer the elementary proof of the fact that there is λ = λ(α, k) > 0 satisfying In the case µ ≤ βt we have µ + t ≤ y, so that P(X ≥ µ + t) ≥ P(X ≥ y) ≥ P(Y ≥ y) and (69) establish inequality (66) for any constant c satisfying c ≥ D √ λ (we defer the precise choice of c). Henceforth we focus on the more interesting case µ > βt. Define Z = X − Y . Since Y ≥ (β + 1)t and Z ≥ µ − βt are both increasing events, using X = Y + Z, Harris' inequality [18], and (69) we infer We defer the proof of the conceptually straightforward (but slightly tedious) claim that where C = C(k, a, D, λ) ≥ 1. Using EZ − t = EX − EY − t ≥ µ − βt and the Paley-Zygmund inequality (67), for d = log 1−α (1/(C + 1)) > 0 it follows (exploiting 1 − α ≥ p and 1 ≤ λt) that Inserting (73) Observing Λ ≥ µ and t ≥ 1 − µ, using the assumed lower bound for t (and λ ≥ 4) it follows that establishing the claimed inequality (68). Recall that we only need to prove (71)-(72) whenever µ > βt. In this case ⌈y⌉ = (β + 1)t holds by choice of β, so that (1 − α) k = 1 − 4/λ and β + 1 ≥ λ/2 imply establishing the claimed inequality (71). To get a handle on Var Z in (72), note that Z is a restriction of X to a subset of the edges of H. So, with (74) and E(Y e Y f ) − EY e EY f ≥ 0 in mind, it is not difficult to see that Var Z ≤ Var X holds. By Remark 7 there is a constant A = A(k, a, D) > 0 such that Recalling µ ≥ an 2 p k , it is easy to see that µ < 1/2 implies p = O(n −2/k ) and Var X ≤ B = B(A, k, a, D) > 0. Using (75) and the assumed lower bound for t in case of µ ≥ 1/2, it follows (exploiting 1 ≤ λt) that completing the proof.
Using a variant of the above proof, it alternatively suffices to assume t ≥ max{ √ p Var X, 1}, say. Furthermore, for p = o(1) and t = O(µ) with t = ω(1) we can easily improve the constant c by planting only (1 + o(1))t edges (in some cases, this approach presumably yields the 'optimal' form of the exponent).

Configurations with many disjoint edges
The second lower bound is based on the heuristic that, for small p, most edges of H p should arise disjointly. Exploiting the implied 'approximate independence' of the edges, we obtain the following Chernoff-like lower bound. In fact, (76) is of sub-Gaussian type since EX = (1 + o(1)) Var X for the p under consideration.
Theorem 22. Given k ≥ 3, a > 0 and D ≥ 1, let H = H n be a k-uniform hypergraph satisfying v(H) ≤ Dn, e(H) ≥ an 2 and ∆ 2 (H) ≤ D. Set X = e(H p ), µ = EX and ϕ(x) = (1 + x) log(1 + x) − x. There are n 0 , c, d > 0 (depending only on k, a, D) such that for all n ≥ n 0 , 0 < p ≤ n −2/(k+1/3) and t ≥ 0 satisfying 1 ≤ µ + t ≤ 9 max{µ, n 1/(2k) } we have We have not tried to optimize p ≤ n −2/(k+1/3) , but conjecture that this condition can be relaxed to p = O(n −1/(k−1) ). In fact, it would be interesting to have a general method which yields such Poisson-type lower bounds for the upper tail when Var X = (1 + o(1))EX holds (for the lower tail this was very recently settled by Janson and Warnke [26]). In the proof of Theorem 22 we shall use the idea that, for small p, most edges f ∈ H should appear disjointly (and thus nearly independently) in H p . The next lemma makes this more precise: it relates P(X = m) with P(Bin(e(H), p k ) = m) over a convenient (but ad-hoc) range of m. such that for all n ≥ n 0 , 0 < p ≤ n −2/(k+1/3) and integers 0 ≤ m ≤ 99 max{µ, n 1/(2k) } we have With Lemma 23 in hand, the proof of Theorem 22 essentially reduces to folklore lower bounds for the binomial distribution (based on Stirling's formula); we include the details in Appendix A for completeness (some minor care is needed when t is small). A similar analysis can be used to tighten related results in the theory of random graphs due to DeMarco and Kahn [11] andŠileikis [40].
Let us informally discuss the strategy used in the proof of Lemma 23. For (77) the basic plan is to consider the event that H p consists of exactly m vertex disjoint edges. It turns out that, for small m, there are roughly e(H) m ways to select such edge collections, and with probability p km their m disjoint edges are all present. Of course, we also need to take into account that all of the remaining e(H) − m edges are not present (to avoid overcounting). If these were independent events, then this would yield another factor of (1 − p k ) e(H)−m , and for small p we expect that this is usually close to the truth. The proof below follows the discussed outline, dropping the (de facto redundant) disjointness condition. However, we need to deal with one subtle technicality that we ignored so far: given a collection of edges {f 1 , . . . , f m } ⊆ H, it can happen that the union of their vertex sets i∈[m] f i induces additional 'extra' edges from H (even if all the f i are vertex disjoint). In particular, for our construction this means that the second part is impossible: in this 'bad' case at least one of the remaining e(H) − m edges must occur. Luckily, such bad edge collections are rare for small m, so we can simply ignore them in our proof (see the definition of S m below).
It remains to estimate |S m | and P(I = H p | I ⊆ H p ) from below. We defer the routine proof of the auxiliary claim that there is λ = λ(k, a, D) > 0 such that for n ≥ n 0 (k, a, D) we have k 3 D 3 nm 2 /e(H) ≤ 1/2 and max nm 3 /e(H), m 2 p, nmp k−1 ≤ λ.

Configurations with too many vertices
Our third lower bound is based on the following heuristic: if V p (H) contains 'too many vertices' (more than expected), then it seems likely that the induced subgraph H p = H[V p (H)] also contains 'too many edges' (more than the average number). For moderately large p, this approach eventually yields the following lower bound of sub-Gaussian type (by Remark 7 we have Λ = Θ(Var X), since p is bounded away from one).
The key observation is that µ 2 /Λ = Θ(np) for the relevant range of p. With this in mind, the proof of Theorem 24 is based on the following two ideas: (i) since V p (H) ∼ Bin(v(H), p) and v(H) = Θ(n), with probability at least exp(−Θ(ε 2 np)) = exp(−Θ((εµ) 2 /Λ)) we have |V p (H)| ≥ (1 + ε)E|V p (H)|, and (ii) conditioning on |V p (H)| ≥ (1+ε)E|V p (H)| intuitively increases the expected number e(H p ) = e(H[V p (H)]) of induced edges, effectively turning the unlikely event X ≥ µ + t into a 'typical' one; see also (83) below. For the number of copies of H in the binomial random graph G n,p an analogous reasoning (based on a deviation of the number of edges) applies for p = Ω(n −1/m2(H) ), where m 2 (H) is the so-called 2-density of H; for the lower tail this idea was used by Janson and Warnke [26].

Proof of the lower bounds of Theorem 4 and 6 (and Remark 8)
In this section we combine the previous estimates, and prove the lower bounds of Theorem 4 and 6 (as well as Remark 8). This is in principle straightforward but, at least as written here, requires several case distinctions (that are not very illuminating). Some complications are due to the fact that the results of Sections 4.1-4.3 are only valid in some range of the parameters (they need to be merged seamlessly), whereas others stem from the fact that our estimates are uniform (e.g., our n 0 does not depend on ε or γ), from the fact that our assumptions are very weak (e.g., p > 0 instead of p ≥ n −2/k ), or from the fact that the exponents are more involved than usual (e.g., (10) yields up to five different asymptotic expressions).