Embedding graphs with bounded degree in sparse pseudorandom graphs^{∗}

Y. Kohayakawa^{†}  V. Rödl^{‡}  P. Sissokho^{§}

May 31, 2002

Abstract

In this paper, we show the equivalence of some quasi-random properties for sparse graphs, that is, graphs G with edge density p = |E(G)|/\binom{n}{2} = o(1), where o(1) → 0 as n = |V (G)| → ∞. In particular, we prove the following embedding result. For a graph J, write N_{J}(x) for the neighborhood of the vertex x in J, and let δ(J) and Δ(J) be the minimum and the maximum degree in J. Let H be a triangle-free graph and set d_{H} = max{δ(J): J ⊂ H}. Moreover, put D_{H} = min{2d_{H}, Δ(H)}. Let C > 1 be a fixed constant and suppose p = p(n) ≫ n^{−1/D_{H}}. We show that if G is such that

(i) deg_{G}(x) ≤ Cpn for all x ∈ V (G), (ii) for all 2 ≤ r ≤ D_{H} and for all distinct vertices x_{1}, …, x_{r} ∈ V (G),

|N_{G}(x_{1}) ∩ ⋯ ∩ N_{G}(x_{r})| ≤ Cnp^{r},

(iii) for all but at most o(n^{2}) pairs {x_{1}, x_{2}} ⊂ V (G),

||N_{G}(x_{1}) ∩ N_{G}(x_{2})| − np^{2}| = o(np^{2}),

then G contains H as a subgraph. We discuss a setting under which an arbitrary graph H (not necessarily triangle-free) can be embedded in G. We also present an embedding result for directed graphs.

Contents

1 Introduction 2 1.1 The constant density case . . . . . . . . . . . . . . . . . . . . . . 3 1.2 The vanishing density case . . . . . . . . . . . . . . . . . . . . . . 6 2 Statements of the main results 8

∗Research supported by a CNPq/NSF cooperative grant.

†Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508–090 São Paulo, SP, Brazil. E-mail: yoshi@ime.usp.br. Partially supported by MCT/CNPq through ProNEx Programme (Proc. CNPq 664107/1997–4) and by CNPq (Proc. 300334/93–1 and 468516/2000–0)

‡Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA. E-mail: rodl@mathcs.emory.edu. Partially supported by NSF Grant 0071261.

§Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA. E-mail: psissok@emory.edu. Supported by NSF grant CCR–9820931

2.1 The undirected case . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 The directed case . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3 Proofs of the main results 12 3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Proof of Theorems 16 and 18 . . . . . . . . . . . . . . . . . . . . 13

3.2.1 Degenerate orderings . . . . . . . . . . . . . . . . . . . . . 16 3.2.2 The extension lemma and a corollary . . . . . . . . . . . . 17 3.2.3 Proof of Lemma 30 . . . . . . . . . . . . . . . . . . . . . . 20 3.2.4 Proof of Theorem 16 . . . . . . . . . . . . . . . . . . . . . 24

3.3 Proof of Theorem 23 . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4 Remarks about Theorem 25 (the directed case) . . . . . . . . . . 29

4 Auxiliary facts and related work 32 4.1 General facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2 Proof of Proposition 6 . . . . . . . . . . . . . . . . . . . . . . . . 33

4.2.1 Construction of Alon’s graph . . . . . . . . . . . . . . . . 33 4.3 Connection to random graphs . . . . . . . . . . . . . . . . . . . . 37

4.3.1 Theorem 1 for subgraphs of random graphs . . . . . . . . 37 4.3.2 Turán’s problem for subgraphs of random graphs . . . . . 38

5 Concluding remarks 39

1 Introduction

Let H be a fixed graph with k vertices and e edges. In what follows, o(1) terms denote functions of n such that o(1) → 0 as n → ∞. It is well known that, for any constant p, asymptotically almost surely the random graph G(n, p) contains (1 + o(1))n^{k}p^{e} labeled (not necessarily induced) copies of H. Throughout this paper, we think of a labeled copy of a graph H in a graph G as an injective function from V (H) to V (G) that preserves edges.

Let k ≥ 4 be a fixed integer and p ∈ (0, 1). Suppose we have a sequence of graphs \{G_{n}\}_{n=1}^{∞}, where G_{n} has n vertices and (1 + o(1))p\binom{n}{2} edges. We say that {G_{n}}_{n=1}^{∞} is (k, p)-quasi-random, or simply quasi-random for short, if G_{n} contains (1 + o(1))n^{k}p^{e} labeled (not necessarily induced) copies of H for any graph H with k vertices, where e is the number of edges in H. It turns out that, for constant p, this notion of quasi-randomness can be equivalently described in terms of some other properties involving parameters other than the number of subgraphs (see [8, 20] and also [5, Chapter 9]). When p = o(1) (i.e., p → 0 as n → ∞), some of these properties fail to describe quasi-randomness in the above sense.

In this paper, we investigate quasi-random sparse graphs. We consider both directed and undirected graphs. In Section 1, we outline some well-known results about quasi-random graphs, when p is constant, as well as a few new results when p = o(1). In Sections 2 and 3, we state and prove our main results. We present the proofs of our results for undirected graphs in Sections 3.2 and 3.3 and sketch the proof of our result for directed graphs in Section 3.4. In Section 4, we present some auxiliary facts and related work. In the last section, Section 5, we summarize a few open questions.

Terminology and notation. Our terminology and notation are fairly standard. Our o(1) terms refer to functions that tend to 0 as n → ∞. More generally, o(f(n)) denotes a function g(n) such that g(n)/f(n) → 0 as n → ∞. We also write g(n) ≪ f(n) if g(n) = o(f(n)). Moreover, for A, B, and δ > 0, we write A ∼_{δ} B to mean (1 − δ)B < A < (1 + δ)B. Similarly, we write A ≁_{δ} B if A ≤ (1 − δ)B, or A ≥ (1 + δ)B. Also, if f(n) and g(n) are functions, we write f(n) ∼ g(n) if lim_{n→∞} f(n)/g(n) = 1.

For any integer n, let [n] = {1, …, n}. For any set X, we denote the set of all r-elements subsets of X by [X]^{r} and we denote the set of all ordered r-tuples of X by X^{r} = X ×⋯×X. The cardinality of X will be denoted by |X|. We use the following non-standard notation. If U = (u_{1}, …, u_{k}) is an ordered k-tuple, we let U^{set} = {u_{1}, …, u_{k}} be the set of the elements occurring in the vector U.

Let G = (V, E) be a graph with vertex set V = V (G) and edge set E = E(G). We write N(x) = N_{G}(x) for the neighborhood of a vertex x in G, and if X ⊂ V, we let N(X) = N_{G}(X) be the joint, or common, neighborhood

⋂_{x∈X} N(x)

of the vertices in X. We denote the degree of x ∈ V by deg(x) = deg_{G}(x) = |N(x)|. We denote the number of edges in G by e(G). If X ⊂ V, we sometimes write e(X) = e_{G}(X) for the number of edges induced by X in G. The maximum and the minimum degree in G are denoted by Δ(G) and δ(G). For X ⊂ V, we let G[X] be the graph induced by X in G. Usually, G_{n} denotes a graph on n vertices. Finally, we call a subset U ⊂ V stable (or independent) if there is no edge induced in U.

1.1 The constant density case

The subject of quasi-random graphs was introduced in the eighties by Thomason [20] and Chung, Graham and Wilson [8]. They realized the surprising fact that several important properties shared by almost all graphs are asymptotically equivalent in a deterministic sense. See also [1, 3, 10, 17] for related initial work in this area and [19] for a recent development.

These equivalent properties are satisfied almost surely by a random graph in which every edge is chosen independently with probability p = 1/2. In general one may consider a random graph G(n, p) on n vertices in which every edge is chosen independently with a constant probability p ∈ (0, 1). Then one can show that the following properties hold for G_{n} ∈ G(n, p) asymptotically almost surely, that is, with probability tending to 1 as n → ∞.

NSUB(k): For any graph H on k vertices, the number of labeled (not necessarily induced) copies of H in G_{n} is

N(H, G_{n}) = (1 + o(1))n^{k}p^{e},

where e is the number of edges in H.

DISC: For all X, Y ⊂ V (G_{n}) with X ∩ Y = ∅, if e(X, Y) denotes the number of edges between X and Y then

|e(X, Y) − p|X||Y || = o(pn^{2}).

EIG: Let A = (a_{x,y})_{x,y∈V (G_{n})} denote the 0–1 adjacency matrix of G_{n}, with 1 denoting edges. Let λ_{i} (1 ≤ i ≤ n) be the eigenvalues of A and adjust the notation so that λ_{1} ≥ |λ_{2}| ≥ ⋯ ≥ |λ_{n}|. Then

λ_{1} = (1 + o(1))pn and |λ_{2}| = o(pn).

CYCLE(4): If C_{4} denotes the 4-cycle, i.e., the cycle of length 4, then

N(C_{4}, G_{n}) = (1 + o(1))(pn)^{4}.

TUPLE(s): For all r ∈ [s] = {1, …, s}, we have

||N(x_{1}) ∩ ⋯ ∩ N(x_{r})| − np^{r}| = o(p^{r}n),

for all but at most o(n^{r}) r-element sets {x_{1}, …, x_{r}} ⊂ V (G_{n}).

Above, s and k are arbitrary fixed constants. The following theorem holds (see [8] and [20]).

Theorem 1. Let k ≥ 4 be a fixed integer. Let G_{n} be a graph on n vertices and (1 + o(1))p\binom{n}{2} edges for some fixed p ∈ (0, 1). If G_{n} satisfies any of the properties NSUB(k), DISC, EIG, CYCLE(4), and TUPLE(2), then it satisfies all of them.

Remark 2. Note that the property NSUB(k) depends on a parameter k. It is not hard to show that, for any k, property NSUB(k + 1) implies property NSUB(k) (see Fact 45). Perhaps quite surprisingly, it follows from Theorem 1 that property NSUB(k) implies property NSUB(k + 1) as well, as long as k ≥ 4.

To make our assertions more precise, we may substitute the o(1) terms that appear in the definitions of NSUB(k), DISC, EIG, CYCLE(4), and TUPLE(s) by a parameter ε > 0. We then obtain the properties for n-vertex graphs G_{n} given below. In what follows, unless explicitly stated otherwise, we let

p = p(n) = |E(G_{n})|\binom{n}{2}^{−1}.

NSUB_{ε}(k): For any graph H on k vertices, the number of labeled (not necessarily induced) copies of H in G_{n} satisfies

(1 − ε)n^{k}p^{e} < N(H, G_{n}) < (1 + ε)n^{k}p^{e},

where e is the number of edges in H.

DISC_{ε}: For all X, Y ⊂ V (G_{n}) with X ∩ Y = ∅, if e(X, Y) denotes the number of edges between X and Y then

|e(X, Y) − p|X||Y || ≤ εpn^{2}.

EIG_{ε}: Let A = (a_{x,y})_{x,y∈V (G_{n})} denote the 0–1 adjacency matrix of G_{n}, with 1 denoting edges. Let λ_{i} (1 ≤ i ≤ n) be the eigenvalues of A and adjust the notation so that λ_{1} ≥ |λ_{2}| ≥ ⋯ ≥ |λ_{n}|. Then

(1 − ε)pn < λ_{1} < (1 + ε)pn and |λ_{2}| ≤ εpn.

CYCLE_{ε}(4): We have

(1 − ε)(pn)^{4} < N(C_{4}, G_{n}) < (1 + ε)(pn)^{4}.

TUPLE_{ε}(s): For all r ∈ [s] = {1, …, s}, we have

||N(x_{1}) ∩ ⋯ ∩ N(x_{r})| − np^{r}| < εp^{r}n,

for all but at most ε\binom{n}{r} r-element sets \{x_{1}, …, x_{r}\} ⊂ V (G_{n}).

Remark 3.

(a) The equivalence between two properties in Theorem 1, say P and Q, should be understood in the following way. Property P implies property Q for a sequence of graphs {G_{n}}_{n=1}^{∞} (we write P ⇒ Q for {G_{n}}_{n=1}^{∞}) if the following holds:

(*) For all ε > 0, there exist δ > 0 and n_{0} such that any graph G_{n} with n ≥ n_{0} vertices satisfying P_{δ} satisfies Q_{ε} as well. Here, P_{δ} and Q_{ε} stand for P and Q with o(1) replaced by δ and ε respectively.

(b) We will write “P ⇒ Q” to mean “P ⇒ Q for {G_{n}}_{n=1}^{∞}” when the implicit reference to {G_{n}}_{n=1}^{∞} is clear from the context.

(c) Suppose we have a sequence of graphs {G_{n}}_{n=1}^{∞}. We may then define the ‘density function’ p = p(n) of this sequence by putting p = p(n) = |E(G_{n})|\binom{n}{2}^{−1} for all n. On the other hand, sometimes we prefer to think that we have a given function p = p(n), and that our graph sequence {G_{n}}_{n=1}^{∞} is such that

|E(G_{n})| = (1 + o(1))p\binom{n}{2}.

Although the relationship between {G_{n}}_{n=1}^{∞} and p = p(n) in these two approaches are different, we may clearly ignore this small difference when considering implications of the form P ⇒ Q with P and Q as above.

The investigation of quasi-randomness, for constant p ∈ (0, 1), turned out to be a fruitful area with several applications in questions regarding random graphs and algorithms (see, e.g., [4], [9], [13], [15], [18], and [21]). Some of the open questions in this area deal with the problem of generalizing Theorem 1 to the case in which p = o(1).

Before we proceed, we mention that in 1985 Thomason [20, 21] already considered the case in which p = o(1). Our approach in this paper is different from the one taken by Thomason, who investigated pseudorandom properties with error terms that vanish together with p. Our approach is closer in spirit to the one in the recent paper by Chung and Graham [6].

1.2 The vanishing density case

In this section, we turn our attention to the study of quasi-randomness when p = o(1). The first efforts towards this direction suggest that a generalization of Theorem 1 (which is valid when p ∈ (0, 1) is constant) will not be straightforward. Indeed the quasi-random properties listed above are no longer equivalent when p = o(1). For instance, property TUPLE(2) does not imply property NSUB(3), as we shall see in Proposition 6 below. However, some of these quasi-random properties are equivalent under more restrictive conditions.

Let TFSUB(k) be the property NSUB(k) restricted to triangle-free graphs H, that is, under TFSUB(k) we require the number of occurrences of triangle-free graphs H to be ‘correct’ in G_{n} (see Definition 12). For suitable values of p (see Theorems 10 and 18), the following diagram holds for “special families of graphs” such as the family BDD(C, t) and the family CG(C, t) (see Definitions 4 and 8).

TFSUB(k)  ⟹ CYCLE(4)
⇕ Theorem 18  ⇓ Chung–Graham
TUPLE(2)  ⟹  DISC ⟺^{Chung–Graham} EIG

Note that the “missing” link in the above diagram is the implication DISC ⇒ TUPLE(2). Although this implication does not hold in general (see [6] and [13]), it is possible that it holds under some natural conditions (such as BDD(C, t) and CG(C, t)). If this implication does hold under some special conditions, then the properties CYCLE(4), DISC, EIG, TFSUB(k) and TUPLE(2) would all be equivalent for sequences of graphs satisfying these conditions and BDD (we make this precise in Remark 21 below). For p = o(1), the only known counterexamples to the implication DISC ⇒ TUPLE(2) are graphs in which the joint neighborhood of a few vertices is very large, that is, graphs for which the property BDD(C, t) defined below fails.

Definition 4. Let constants C > 1 and t ≥ 1 be given. We define BDD(C, t) to be the family of all graphs G such that, if we let n = |V (G)| and p = |E(G)|/\binom{n}{2}, then

(i) deg_{G}(x) ≤ Cpn for all x ∈ V (G),

(ii) for all 2 ≤ r ≤ t and for all distinct vertices x_{1}, …, x_{r} ∈ V (G),

|N_{G}(x_{1}) ∩ ⋯ ∩ N_{G}(x_{r})| ≤ Cnp^{r}.

Remark 5. Note that BDD(C, t + 1) ⊂ BDD(C, t).

Since the property TFSUB(k) is restricted to the counting of triangle-free graphs only, it is natural to ask whether this counting extends to graphs with triangles. The following proposition, Proposition 6, shows that there is no hope for such an extension for graphs out of the family BDD when p = o(1) and even for graphs in BDD when p = p(n) is of order n^{−1/3}.

Proposition 6.

(A) For any p = p(n) = o(1), there exists a graph sequence {G_{i}}_{i=1}^{∞}, with |V (G_{i})| = n_{i} → ∞ as i → ∞ and |E(G_{i})| ≥ p(n_{i})\binom{n_{i}}{2} for all i, for which the following holds:

(i) G_{i} is triangle-free for all i ≥ 1,

(ii) {G_{i}}_{i=1}^{∞} satisfies properties DISC, EIG, and TUPLE(2).

(B) There exists a graph sequence {G_{i}}_{i=1}^{∞}, with |V (G_{i})| = n_{i} → ∞ as i → ∞ and |E(G_{i})| = (1/8 + o(1))n_{i}^{5/3}, for which (i) and (ii) above hold and, furthermore,

(iii) G_{i} ∈ BDD(128, 2) for all i ≥ 1.

The proof of Proposition 6 will be discussed in Section 4.2.

Remark 7. It would be interesting to know if one can extend Proposition 6 to the existence of graphs G_{i} with |V (G_{i})| = n_{i} → ∞ and p(n_{i}) = |E(G_{i})|/\binom{n_{i}}{2} ≫ n_{i}^{−1/3} such that G_{i} satisfies (i) and (ii) in Proposition 6 and G_{i} ∈ BDD(C, 2) for all i for some fixed constant C.

Among other problems, the question of the equivalence of the properties EIG, DISC, and CYCLE(4), in the sparse setting, was considered in [6] by Chung and Graham. Before we discuss their results, we introduce some terminology.

For any integer t and any two vertices u and v in a graph G, let e_{t}(u, v) denote the number of paths of length t between u and v. Thus, we always have e_{1}(u, v) ≤ 1 and e_{2}(u, v) = |N(u) ∩ N(v)|.

Definition 8. Let t ≥ 2 be an integer and let C > 1 be a fixed constant. Let CG(C, t) denote the family of graphs G such that, putting n = |V (G)| and p = |E(G)|/\binom{n}{2}, we have

(i) deg_{G}(u) ≤ Cpn for all u ∈ V (G),

(ii) e_{t}(u, v) ≤ Cp^{t}n^{t−1} for all u, v ∈ V (G).

Remark 9. One can observe that

CG(C, t) ⊂ CG(C^{2}, t + 1) and CG(C, 2) = BDD(C, 2).

The next theorem follows from the results of Chung and Graham [6].

Theorem 10. The implications

CYCLE(4) ⇒ EIG ⇒ DISC  (1)

hold for any sequence \{G_{n}\}_{n=1}^{∞} with |V (G_{n})| = n and |E(G_{n})| = (1+o(1))p\binom{n}{2}, as long as p = p(n) ≫ n^{−1/2}.

Remark 11. Chung and Graham have in fact proved that the implication

DISC ⇒ EIG

holds even for fast decreasing functions p = p(n), but assuming an extra hypothesis that can be expressed in terms of the classes CG(C, t). We refer the interested reader to [6]. In the case in which p is constant, all the three properties in (1) are equivalent (see also Conjecture 20).

The study of quasi-random properties in a random setting was considered in [13]. We will discuss this approach in Section 4.3.

2 Statements of the main results

Now we turn our attention to the main goal of this paper. Complementing the work of Chung and Graham [6, 7], we will address the question as to how the property NSUB(k) relates to the properties CYCLE(4), DISC, EIG, and TUPLE(2) in the sparse setting. We shall consider both undirected and directed graphs.

For the digraph case, we focus on the embedding of triangle-free digraphs into sparse pseudorandom digraphs satisfying certain extra conditions. We will only present the proofs of our main results in the undirected case, as they can be naturally extended to the directed case.

2.1 The undirected case

By Proposition 6 the implication “TUPLE(2) ⇒ NSUB(k)” fails to be true for sequences of graphs with vanishing density. Thus, additional conditions are needed in order to obtain any new relation between NSUB(k) and the other properties. One such condition is to restrict the family of graphs G for which such a relation could exist. Another possibility is to weaken property NSUB(k). This leads us to the following two adjustments:

(i) As in the work of Chung and Graham [6] (see Theorem 10 and Remark 11 above), we restrict the domain to a special family of graphs G, namely, the family BDD(C, t) introduced in Definition 4.

(ii) We will also weaken the property NSUB(k) and focus on counting the triangle-free subgraphs only.

Definition 12. Fix an integer k ≥ 4. We say that a sequence of graphs {G_{n}}_{n=1}^{∞} with |V (G_{n})| = n has the property TFSUB(k) if it satisfies the following condition: (‡) For any triangle-free graph H on k vertices, the number of labeled (not necessarily induced) copies of H in G_{n} is

N(H, G) = (1 + o(1))n^{k}p^{e},

where e is the number of edges in H, and p = e(G_{n})\binom{n}{2}^{−1}.

Note that the only difference between the properties TFSUB(k) and NSUB(k) is the triangle-freeness condition. We need the following definitions before we may state our first main theorem.

Definition 13. For any graph H, we let

d_{H} = max{δ(J): J ⊂ H}.

Remark 14. If a k-vertex graph H is triangle-free, then d_{H} ≤ k/2.

Definition 15. For any graph H, we let

D_{H} = min{2d_{H}, Δ(H)}.

We may now state our key result.

Theorem 16 (Embedding Lemma). Suppose H is a triangle-free graph on k vertices and e edges. Let {G_{n}}_{n=1}^{∞} be a sequence of graphs with |V (G_{n})| = n for all n and with p = p(n) = |E(G_{n})|\binom{n}{2}^{−1} satisfying p ≫ n^{−1/D_{H}}. Let C > 1 be a fixed constant and suppose that G_{n} ∈ BDD(C, D_{H}) and G_{n} satisfies TUPLE(2) for all n. More explicitly, for all n, we have

(i) deg_{G_{n}}(x) ≤ Cpn for all x ∈ V (G_{n}),

(ii) for all 2 ≤ r ≤ D_{H} and for all distinct vertices x_{1}, …, x_{r} ∈ V (G_{n}),

|N_{G_{n}}(x_{1}) ∩ ⋯ ∩ N_{G_{n}}(x_{r})| ≤ Cnp^{r},

(iii) for all but at most o(n^{2}) pairs {x_{1}, x_{2}} ⊂ V (G_{n}),

||N_{G_{n}}(x_{1}) ∩ N_{G_{n}}(x_{2})| − np^{2}| = o(np^{2}).

Then G_{n} contains (1 + o(1))n^{k}p^{e} labeled copies of H.

Theorem 16 follows from Lemmas 29 and 30 (see Section 3). Roughly speaking, Theorem 16 states that property TUPLE(2) implies property TFSUB(k) as long as we restrict ourselves to graphs G in an appropriate class BDD(C, s), and the density of G is large enough. We propose the following conjecture.

Conjecture 17. The parameter D_{H} occurring in Theorem 16 may be replaced by d_{H}.

With Theorem 16 in hand, we may deduce the equivalence of some of the properties introduced in Section 1.1 for sparse graphs. For convenience, from now on {G_{n}}_{n=1}^{∞} denotes a sequence of graphs with |V (G_{n})| = n.

Theorem 18. Let a real number C > 1 and an integer k ≥ 4 be fixed. Let p = p(n) be a function of n with

np^{⌊2k/3⌋} ≫ 1.  (2)

Then properties TFSUB(k), CYCLE(4), and TUPLE(2) are equivalent for any sequence of graphs {G_{n}}_{n=1}^{∞} with

G_{n} ∈ BDD(C, ⌊2k/3⌋)  (3)

for all n and |E(G_{n})| = (1 + o(1))p\binom{n}{2}.

The parameter ⌊2k/3⌋ in conditions (2) and (3) in Theorem 18 comes from the fact that if we let

D(k) = max_{H} D_{H},  (4)

where the maximum is taken over all triangle-free graphs on k vertices, then (as proved in Fact 31) we have D(k) = ⌊2k/3⌋ for all k ≥ 4.

Remark 19. Note that if Conjecture 17 holds then the condition np^{⌊2k/3⌋} ≫ 1 in Theorem 18 may be replaced by the weaker condition np^{⌊k/2⌋} ≫ 1.

We also propose the following conjecture.

Conjecture 20. Let C > 1 be an arbitrary constant, and let p = p(n) ≫ n^{−1/2} be a function of n. Then the implication

DISC ⇒ TUPLE(2)

holds for any sequence of graphs \{G_{n}\}_{n=1}^{∞} with |E(G_{n})| = (1+o(1))p\binom{n}{2} as long as G_{n} ∈ BDD(C, 2) for all large enough n.

Remark 21. If Conjecture 20 holds, then we may add properties DISC and EIG to the collection of equivalent properties in Theorem 18. Indeed, this follows from the result of Chung and Graham, Theorem 10, stated above.

To embed general graphs (i.e., graphs that are not necessarily triangle-free) we need a stronger property, INDTUP(s) (s ≥ 1), defined as follows.

INDTUP(s): For all 1 ≤ r ≤ s and all 0 ≤ t ≤ \binom{r}{2},

|{X ∈ [V (G_{n})]^{r}: e(X) = t, |N(X)| ≁ np^{r}}| = o(n^{r}p^{t}).

Remark 22. In the definition of INDTUP above, the expression o(n^{r}p^{t}) that appears on the right-hand side of the equation would perhaps more appropriately be o(n^{r}p^{t}(1 − p)^{\binom{r}{2}−t}). However, since we are interested in the case in which p = o(1) and s = O(1), we may drop the (1 − p)^{\binom{r}{2}−t} factor, which is roughly equal to 1 for such values of p and s.

We may now state our result concerning the embedding of general, not necessarily triangle-free graphs.

Theorem 23. Let k ≥ 3 be an integer and let C > 1 be a fixed constant. Let p = p(n) ≫ n^{−1/(k−1)} be a function of n. Then, for any sequence of graphs \{G_{n}\}_{n=1}^{∞} with G_{n} ∈ BDD(C, k−1) for all n and |E(G_{n})| = (1+o(1))p\binom{n}{2}, we have

(i) NSUB(k + 1) ⇒ INDTUP(k − 1),

(ii) INDTUP(k − 1) ⇒ NSUB(k).

Perhaps Theorem 23 may be strengthened to the following.

Conjecture 24. Let k ≥ 3 be an integer and let C > 1 be a fixed constant. Let p = p(n) ≫ n^{−1/(k−1)} be a function of n. Then the properties NSUB(k) and INDTUP(k − 1) are equivalent for any sequence of graphs {G_{n}}_{n=1}^{∞} with G_{n} ∈ BDD(C, k − 1) for all n and |E(G_{n})| = (1 + o(1))p\binom{n}{2}.

2.2 The directed case

In this section, we state our main result for directed graphs, Theorem 25. The proof of this result is discussed in Section 3.4. Let G⃗ be a directed graph with set of vertices V and set of arcs E⃗. Thus G⃗ = (V, E⃗), where E⃗ ⊂ V ×V \{(v, v): v ∈ V }, and if (u, v) ∈ E⃗, then (v, u) ∉ E⃗. We denote the out-degree (resp. indegree) of a vertex u ∈ V by d^{+}(u) (resp. d^{−}(u)). We define

d^{++}(u, v) = {w ∈ V : (u, w) ∈ E⃗ and (v, w) ∈ E⃗},

and

NG⃗(u) = {v ∈ V : (u, v) ∈ E⃗ or (v, u) ∈ E⃗}.

For any directed graph G⃗ we let G be the undirected graph obtained from G⃗ by transforming its arcs to “edges” (ignoring their orientation). With this convention, clearly NG⃗(u) = N_{G}(u).

We let \overrightarrow{BDD}(C, t) be the family of all directed graphs G⃗ such that G ∈ BDD(C, t). Moreover, below, given a digraph H⃗, we shall consider the parameters d_{H} and D_{H} of the associated undirected graph H.

Let G⃗ = (V, E⃗) be as above. We introduce the property \overrightarrow{TUPLE(2)} which is analogous to the property TUPLE(2) for undirected graphs.

\overrightarrow{TUPLE(2)}: G⃗ satisfies the property \overrightarrow{TUPLE(2)} if the following holds

(a) for all but o(n) vertices u ∈ V,

d^{+}(u) = \frac{1}{2}pn(1 + o(1)),

(b)

∑_{(u,v)∈V ×V} (d^{++}(u, v))^{2} = n^{2} (\frac{p^{2}n}{4})^{2} (1 + o(1)).

Our embedding result for directed graphs is as follows.

Theorem 25. Suppose that H⃗ is a directed graph on k vertices and e arcs with H triangle-free. Let {G⃗_{n}}_{n=1}^{∞} be a sequence of directed graphs with |V (G⃗_{n})| = n for all n and with p = p(n) = |E(G⃗_{n})|\binom{n}{2}^{−1} satisfying p ≫

n^{−1/D_{H}}. Suppose G⃗_{n} ∈ \overrightarrow{BDD}(C, D_{H}) and G⃗_{n} satisfies \overrightarrow{TUPLE(2)} for all n. Then G⃗_{n} contains

N(H⃗, G⃗) = \frac{1}{2^{e}} n^{k}p^{e}(1 + o(1))

labeled copies of H⃗.

3 Proofs of the main results

3.1 Preliminaries

The following well-known result will be used often.

Lemma 26. For all η > 0, there exists ε_{0} = ε_{0}(η) > 0 such that, for any family of real numbers {a_{i} ≥ 0: 1 ≤ i ≤ n} satisfying the conditions

(i) ∑_{i=1}^{n} a_{i} ≥ (1 − ε_{0})na,

(ii) ∑_{i=1}^{n} a_{i}^{2} ≤ (1 + ε_{0})na^{2},

we have

|{i: a_{i} ∼_{η} a}| > (1 − η)n.

Proof. Let η > 0 be given. We claim that ε_{0} = η^{3}/3 will do. Let a_{i} (1 ≤ i ≤ n) be as in the statement of our lemma. Set B = {i: |a_{i} − a| ≥ ηa}. To prove the lemma, we have to show that |B| < ηn.

From the definition of B, it follows that

∑_{i=1}^{n}(a_{i} − a)^{2} > |B|(ηa)^{2}.  (5)

By hypothesis,

∑_{i=1}^{n}(a_{i} − a)^{2} = ∑_{i=1}^{n} a_{i}^{2} − 2a ∑_{i=1}^{n} a_{i} + ∑_{i=1}^{n} a^{2}

≤ (1 + ε_{0})na^{2} − 2a(1 − ε_{0})na + na^{2} = 3ε_{0}na^{2}. (6)

Combining (5) and (6), we obtain |B|(ηa)^{2} < 3ε_{0}na^{2}, which implies that |B| < (3ε_{0}/η^{2})n = ηn, and our lemma is proved.

3.2 Proof of Theorems 16 and 18

In this section, we shall prove Theorems 16 and 18. The proof of Theorem 18 is broken down into a few steps, and two of these steps will basically form the proof of Theorem 16 (see Section 3.2.4).

The proof of Theorem 18 involves the following components. Let k ≥ 4 and C > 1 be given. Suppose

np^{d(k)} ≫ 1,  (7)

where

d(k) = max_{H} d_{H},

and the maximum is taken over all triangle-free graphs H on k vertices. It is easy to see that, in fact, d(k) = ⌊k/2⌋. However, in what follows, we often prefer to write d(k) instead of its explicit value.

Suppose G_{n} ∈ BDD(C, D(k)) for all n, where D(k) is as defined in (4). Recall that D(k) = ⌊2k/3⌋.

Remark 27. The reader may have noticed that our hypothesis on p = p(n) above, namely (7), is weaker than the hypothesis in Theorem 18. It turns out that (7) is the natural hypothesis for the proof we shall present. However, as a simple argument shows, the condition that BDD(C, D(k)) should hold for G_{n} implies that, in fact, we have pn^{D(k)} = pn^{⌊2k/3⌋} ≫ 1 (see (2)).

The proof of Theorem 18 is broken down as follows.

(a) Let NSUB(C_{4}) be the property NSUB(k) applied to H = C_{4}. Note that

CYCLE(4) = NSUB(C_{4}).

Since C_{4} is a triangle-free graph and TFSUB(k) ⇒ TFSUB(k − 1) (see Fact 46), the implication

TFSUB(k) ⇒ NSUB(C_{4}) = CYCLE(4)

is immediate for any any sequence of graphs {G_{n}}_{n=1}^{∞} (recall k ≥ 4).

(b) Fact 28 below, which may be proved by standard arguments, asserts that

CYCLE(4) = NSUB(C_{4}) ⇒ TUPLE(2),

for any sequence of dense enough graphs {G_{n}}_{n=1}^{∞}.

(c) Lemma 29 (see below) tells us that

TUPLE(2) ⇒ TUPLE(d(k)).

(d) The major piece in the proof of Theorem 18 is the implication

TUPLE(d(k)) ⇒ TFSUB(k).

This implication is stated in an equivalent form in Lemma 30 and its proof constitutes the main task of this paper (Section 3.2.3).

(e) Finally the fact that D(k) = ⌊2k/3⌋ is proved in Fact 31.

Steps (c) and (d) above basically constitute the proof of Theorem 16 (see Section 3.2.4).

Fact 28. Let C > 1 be a constant and suppose p = p(n) is such that np^{2} ≫ 1. Then the implication

CYCLE(4) ⇒ TUPLE(2)

holds for any sequence of graphs \{G_{n}\}_{n=1}^{∞} with |E(G_{n})| = (1 + o(1))p\binom{n}{2}.

Proof. Let {G_{n}}_{n=1}^{∞} be as in the statement of our result and suppose CYCLE(4) holds. We have

∑_{\{x,y\}⊂V, x≠y} |N_{G_{n}}(x) ∩ N_{G_{n}}(y)| = ∑_{v∈V} \binom{deg(v)}{2}

≥ n\binom{n^{−1} ∑_{v∈V} deg(v)}{2} = n\binom{(1 + o(1))pn}{2}

= (1 + o(1))\binom{n}{2}p^{2}n. (8)

Observe that the number of labeled (not necessarily induced) copies of C_{4} in G_{n} is

N(C_{4}, G_{n}) = 4 ∑_{\{x,y\}⊂V, x≠y} \binom{|N_{G_{n}}(x) ∩ N_{G_{n}}(y)|}{2}.  (9)

Since {G_{n}}_{n=1}^{∞} satisfies property CYCLE(4), we have

∑_{\{x,y\}⊂V, x≠y} \binom{|N_{G_{n}}(x) ∩ N_{G_{n}}(y)|}{2} = \frac{1}{4}N(C_{4}, G_{n}) = \frac{1}{4}(1 + o(1))(pn)^{4}. (10)

We now observe that the Cauchy–Schwarz inequality tells that

∑_{\{x,y\}⊂V, x≠y} |N_{G_{n}}(x) ∩ N_{G_{n}}(y)|^{2} ≥ \binom{n}{2}^{−1}\{ ∑_{\{x,y\}⊂V, x≠y} |N_{G_{n}}(x) ∩ N_{G_{n}}(y)|\}^{2}

≫ ∑_{{x,y}⊂V, x≠y} |N_{G_{n}}(x) ∩ N_{G_{n}}(y)|, (11)

where in the last inequality we used (8) and the fact that p^{2}n → ∞ as n → ∞. Now from (10) and (11), we obtain that

∑_{\{x,y\}⊂V, x≠y} |N_{G_{n}}(x) ∩ N_{G_{n}}(y)|^{2} = \frac{1}{2}(1 + o(1))(pn)^{4}.  (12)

Now Lemma 26 together with (8) and (12) imply that

|N_{G_{n}}(x) ∩ N_{G_{n}}(y)| = (1 + o(1))p^{2}n,

for all but at most o(n^{2}) pairs {x, y} ⊂ V.

We will sketch the proof of Lemma 29 (stated below) in Section 3.4, by deriving it as a corollary of Lemma 43. However, we mention that Lemma 29 was first proved in Łuczak et al. [16]; the proof of Lemma 43 is a simple extension of the proof in [16] to the directed case.

Lemma 29. Let t ≥ 2 and C > 1 be fixed and suppose p = p(n) satisfies np^{r} ≫ 1. Let {G_{n}}_{n=1}^{∞} be a sequence of graphs with G_{n} ∈ BDD(C, 2) for all n and |E(G_{n})| = (1 + o(1))p\binom{n}{2}. Then the implication

TUPLE(2) ⇒ TUPLE(r)

holds for {G_{n}}_{n=1}^{∞}.

To complete the proof of Theorem 18, we need to prove Lemma 30 and Fact 31 below.

Let H be an arbitrary triangle-free graph on k vertices and e edges. Recall

d_{H} = max_{J⊂H} δ(J)

and

D_{H} = min{2d_{H}, Δ(H)}

(see Definitions 13 and 15).

Lemma 30. Let δ > 0, C > 1, and k ≥ 4 be fixed. Let H be as above and let p = p(n) = o(1) be a function of n satisfying np^{D_{H}} ≫ 1. Then there exist ε > 0 and an integer n_{2} for which the following holds. If a sequence of graphs {G_{n}}_{n=1}^{∞} with |V (G_{n})| = n is such that, for all n,

(i) G_{n} ∈ BDD(C, D_{H}),

(ii) p = p(n) = e(G_{n})\binom{n}{2}^{−1} ,

(iii) TUPLE_{ε}(d_{H}) holds for G_{n},

then

N(H, G_{n}) ∼_{δ} n^{k}p^{e}

holds for all n ≥ n_{2}.

The proof of Lemma 30 is somewhat involved and is delayed until Section 3.2.3. We finish this section with the statement of Fact 31.

Fact 31. Let an integer k ≥ 1 be given and let D(k) = max_{H} D_{H}, where the maximum is taken over all triangle-free graphs H on k vertices. Then

D(k) = ⌊\frac{2k}{3} ⌋ .

Fact 31 is proved in Section 3.2.1 below.

3.2.1 Degenerate orderings

The following simple definition will be important.

Definition 32. Let H be a graph. We say that H is d-degenerate if there is an ordering v_{1}, …, v_{k} of the vertices of H such that deg_{H_{i}}(v_{i}) ≤ d for all 1 ≤ i ≤ k, where H_{i} = H[{v_{1}, …, v_{i}}] is the graph induced by {v_{1}, …, v_{i}} in H. Moreover, if H is d-degenerate and this is certified by a certain ordering of the vertices of H, then we call this ordering a d-degenerate ordering of H.

Remark 33. Let d = d_{H} = max{δ(J): J ⊂ H}. Then H has a d-degenerate ordering. Indeed we can find such an ordering in the following way. First select a vertex v ∈ V (H) such that deg_{H}(v) = δ(H) ≤ d_{H} (by the definition of d_{H}) and set v_{k} = v. Let H_{k−1} = H −v_{k}, then we repeat the same procedure on H_{k−1} and obtain a vertex v_{k−1} with deg_{H_{k−1}}(v_{k−1}) ≤ δ(H_{k−1}) ≤ d_{H}. Continuing in this way, we obtain the desired ordering of V (H) after k = |V (H)| steps. In fact, d_{H} is the smallest integer d for which H admits a d-degenerate ordering.

We may now prove Fact 31.

Proof. Suppose k ≥ 1 is given, and let D(k) be as in the statement of the fact. We may clearly suppose that k ≥ 2.

First we show that D(k) ≥ ⌊2k/3⌋. It suffices to exhibit a triangle-free graph H on k vertices for which D_{H} ≥ ⌊2k/3⌋. We show that the complete bipartite graph H = K(⌈k/3⌉, ⌊2k/3⌋) with vertex classes of cardinality ⌈k/3⌉ and ⌊2k/3⌋ will do. We have d_{H} = max_{J⊂H} δ(J) ≥ δ(H) = ⌈k/3⌉. Therefore 2d_{H} ≥ 2⌈k/3⌉ ≥ 2k/3 ≥ ⌊2k/3⌋. Since Δ(H) = ⌊2k/3⌋, we have D_{H} = min{2d_{H}, Δ(H)} ≥ ⌊2k/3⌋.

Let us now show that D(k) ≤ ⌊2k/3⌋. To that end, let H be a triangle-free graph on k vertices. We show that D_{H} ≤ 2k/3. Suppose Δ(H) > 2k/3. Let u be a vertex of H with maximum degree, and suppose v_{1}, …, v_{k} is an ordering of the vertices of H with the last Δ(H) vertices v_{k−Δ(H)+1}, …, v_{k} forming the neighborhood of u in H. We claim that this is a (⌈k/3⌉−1)-degenerate ordering of the vertices of H.

To see this, let H_{h} = H[{v_{1}, …, v_{h}}] for all 1 ≤ h ≤ k. Since H is trianglefree, every vertex v_{h} with k−Δ(H)+1 ≤ h has its neighborhood contained in the set {v_{1}, …, v_{k−Δ(H)}}. Thus deg_{h}(v_{h}) ≤ k − Δ(H) < k/3 for all k − Δ(H) + 1 ≤ h ≤ k, and hence for all 1 ≤ h ≤ k. Therefore deg_{h}(v_{h}) ≤ ⌈k/3⌉ − 1 for all h and we do indeed have a (⌈k/3⌉ − 1)-degenerate ordering as claimed. Hence 2d_{H} ≤ 2(⌈k/3⌉ − 1) ≤ 2k/3, and hence D_{H} = min{2d_{H}, Δ(H)} ≤ 2k/3, as required.

3.2.2 The extension lemma and a corollary

In this section, we shall establish a simple lemma, the Extension Lemma, and a corollary, Corollary 36. They will be used in the proofs of Theorems 16, 18, and 23.

Let H and G be graphs. In what follows, H will always have k vertices and e edges and G will always have n vertices. In this section, H is an arbitrary graph; in Sections 3.2.3 and 3.2.4, we shall consider triangle-free graphs H.

Let E(H, G) denote the set of all embeddings of H in G. Moreover, if l ∈ [k] and F = (v_{1}, …, v_{l}) ∈ V (H)^{l} and X = (x_{1}, …, x_{l}) ∈ V (G)^{l}, let E(H, G, F, X) denote the set of all embeddings f ∈ E(H, G) such that f(v_{i}) = x_{i} for all i ∈ [l]. Clearly, we may always assume that the v_{i} (1 ≤ i ≤ l) and the x_{i} (1 ≤ i ≤ l) are all distinct. Recall that F^{set} = {v_{1}, …, v_{l}} and X^{set} = {x_{1}, …, x_{l}}.

Below, for any graph H′ and any l-tuple F of vertices of H′, we write w(H′, F) for the number of edges in H′ that do not have both endpoints in F^{set}. That is,

w(H′, F) = |E(H′)| − |E(H′[F^{set}])|.

We now prove the following simple lemma.

Lemma 34 (Extension Lemma). Let graphs G and H be given. Suppose 0 ≤ l ≤ max{2, d_{H}}, and let F ∈ V (H)^{l} and X ∈ V (G)^{l} be fixed. Let C > 0 be a constant and suppose G ∈ BDD(C, D_{H}). Then

|E(H, G, F, X)| ≤ C^{k−l}n^{k−l}p^{w(H,F)},

where k = |V (H)|, n = |V (G)|, and p = e(G)\binom{n}{2}^{−1}. In particular, if F^{set} ⊂ V (H) is a stable set, then

|E(H, G, F, X)| ≤ C^{k−l}n^{k−l}p^{e},

where e = |E(H)|.

In Claim 35 below, we prove the Extension Lemma under a stronger hypothesis. We then show that the hypothesis of this claim is satisfied even with the weaker assumption of the Extension Lemma.

Claim 35. Let G, H, F and X be as in Lemma 34. Assume (in addition to the hypotheses of Lemma 34) that there exists a D_{H}-degenerate ordering v_{1}, …, v_{k} of H such that F = {v_{1}, …, v_{ℓ}}. Then

|E(H, G, F, X)| ≤ C^{k−l}n^{k−l}p^{w(H,F)},

where k = |V (H)|, n = |V (G)|, and p = e(G)\binom{n}{2}^{−1}.

Proof. Consider a D_{H}-degenerate ordering v_{1}, …, v_{k} of H with F^{set} = {v_{1}, …, v_{l}}. We shall prove that

(*) for all l ≤ h ≤ k, we have

|E(H_{h}, G, F, X)| ≤ C^{h−l}n^{h−l}p^{w(H_{h},F)},  (13)
where H_{h} = H[{v_{1}, …, v_{h}}].

We prove (*) by induction on h. The case in which h = l is clear. Now suppose that l < h ≤ k and that (13) holds for smaller values of h. We wish to prove (13). To that end, first observe that, by our choice of the ordering v_{1}, …, v_{k} of the vertices of H, we have deg_{H_{h}}(v_{h}) ≤ D_{H}. Therefore, as G ∈ BDD(C, D_{H}), if we let r = deg_{H_{h}}(v_{h}), then any embedding of H_{h−1} can be extended in at most Cnp^{r} ways to an embedding of H_{h}. Using the induction hypothesis and the fact that w(H_{h}, F) = w(H_{h−1}, F) + r, we have

|E(H_{h}, G, F, X)| ≤ Cnp^{r}|E(H_{h−1}, G, F, X)|
≤ Cnp^{r} × C^{h−l−1}n^{h−l−1}p^{w(H_{h−1},F)} = C^{h−l}n^{h−l}p^{w(H_{h},F)},

verifying (13). This completes the induction step and assertion (*) follows by induction. Our lemma follows on setting h = k in (13).

Proof of Lemma 34. To prove Lemma 34, it suffices to show that there exists a D_{H}-degenerate ordering v_{1}, …, v_{k} of H such that F^{set} = {v_{1}, …, v_{ℓ}}. Indeed, we may then simply apply Claim 35. In the remainder of this proof, we prove the existence of such a D_{H}-degenerate ordering.

We distinguish the following two cases. Case 1: d_{H} = 1

Fix a 1-degenerate ordering L = v_{1}, …, v_{k} of H. By hypothesis, |F | ≤ max{2, d_{H}} = 2. If F^{set} = ∅, then our fixed 1-degenerate ordering L will do. If F^{set} = {v_{i}}, we consider the new ordering

L′ = v_{i}, v_{1}, …, v̂_{i}, …, v_{i_{k}},

where x̂ means that the element x is omitted in the listing of L′. Since L is a 1-degenerate ordering, it follows that L′ is a 2-degenerate ordering.

If F^{set} = {v_{i}, v_{j}}, let L_{v_{i}} and L_{v_{j}} be the set of vertices in the ‘left neighborhood’ of v_{i} and v_{j} in the ordering L, respectively. Clearly, |L_{v_{i}} ∩ L_{v_{j}}| ≤ 1 because L is a 1-degenerate ordering. This leads us to the following possibilities.

(i) L_{v_{i}} ∩ L_{v_{j}} = ∅

Consider the ordering

L′ = v_{i}, v_{j}, v_{1}, …, v̂_{i}, …, v̂_{j}, …, v_{k}.

Since L = v_{1}, …, v_{k} is a 1-degenerate ordering and L_{v_{i}} ∩ L_{v_{j}} = ∅, it is clear that L′ is a 2-degenerate ordering as required.

(ii) L_{v_{i}} ∩ L_{v_{j}} ≠ ∅

Suppose L_{v_{i}} ∩ L_{v_{j}} = {v_{s}}. Clearly, s < i, j. Consider the ordering

L′ = v_{i}, v_{j}, v_{s}, v_{1}, …, v̂_{s}, …, v̂_{i}, …, v̂_{j}, …, v_{k}.

The vertex v_{s} has 2 left neighbors (v_{i} and v_{j}) in the ordering L′. Furthermore, since H is a forest (because d_{H} = 1), any vertex u ∉ {v_{i}, v_{j}, v_{s}} is joined to at most one vertex in {v_{i}, v_{j}, v_{s}}. Therefore the left degree of any vertex u in the ordering L′ is at most 2. Consequently L′ is a 2-degenerate ordering as required.

Case 2: d_{H} ≥ 2

By Remark 33, our graph H has a d_{H}-degenerate ordering L. We now observe that if relocate the vertices in F at the beginning of that ordering, then we obtain a D_{H}-degenerate ordering of the vertices of H. To see this, let L′ = v_{1}, …, v_{k} be this ordering. If D_{H} = Δ(H), then clearly any ordering of V (H) is a D_{H}-ordering. Thus suppose that D_{H} = 2d_{H}. As in Definition 32, let H_{h} = H[{v_{1}, …, v_{h}}] (0 ≤ h ≤ k). Owing to the assumption that l ≤ max{2, d_{H}} = d_{H}, we have

deg_{H_{h}}(v_{h}) ≤ l + d_{H} ≤ 2d_{H} = D_{H}.

This proves that there exist a D_{H}-degenerate ordering L′ = v_{1}, …, v_{k} of H such that F = {v_{1}, …, v_{ℓ}}, as required.

The following notation will be used in the next corollary. Set

E^{ni}(H, G) = {f ∈ E(H, G): f is a non-induced embedding}.

Corollary 36. Let C > 1, k ≥ 1, and η > 0 be fixed and let p = p(n) = o(1) be a function of n. Then there exists an integer n_{1} such that, for any graph H with k vertices and any graph G ∈ BDD(C, D_{H}) with |E(G)| ≤ pn^{2} and n = |V (G)| ≥ n_{1}, we have

|E^{ni}(H, G)| < ηn^{k}p^{e},  (14)

where and e = |E(H)|.

Proof. Let η, p, H and G be as in the statement of the corollary. The case in which k = 1 is clear, and hence we suppose k ≥ 2. To count non-induced embeddings of H in G, we select an edge {x, y} ∈ E(G) and a pair u, v of distinct, non-adjacent vertices of H. By Lemma 34 applied to F = (u, v) and X = (x, y), the number of embeddings f: V (H) → V (G) such that f(u) = x and f(v) = y is at most C^{k−2}n^{k−2}p^{e}.

Since {x, y} ∈ E(G) can be selected in at most pn^{2} ways, the ordered pair X can be selected in ≤ 2pn^{2} ways. Similarly, F can be selected in ≤ 2\binom{k}{2} ways. Therefore

|E^{ni}(H, G)| ≤ 4pn^{2}\binom{k}{2}C^{k−2}n^{k−2}p^{e} < 2k^{2}C^{k−2}n^{k}p^{e+1}.

Since p = o(1) and C, k, and η > 0 are constants, there exists an integer n_{1} such that (14) holds for all n ≥ n_{1}, as required.

3.2.3 Proof of Lemma 30

This section is devoted to the proof of Lemma 30. We start by introducing some notation and terminology. Let G_{n} be an n-vertex graph with p = e(G_{n})\binom{n}{2}^{−1}. For every integer r ≥ 1 and real ε > 0, we let

B(ε, r) = {X ∈ [V (G_{n})]^{r}: |N_{G_{n}}(X) − np^{r}| ≥ εnp^{r}},

and

B_{stb}(ε, r) = {X ∈ B(ε, r): X is a stable set in G_{n}}.

A set B ⊂ V (G_{n}) will be said to be ε-bad if B ∈ B_{stb}(ε, r) for some r with 1 ≤ r ≤ d_{H}.

If G_{n} satisfies TUPLE_{ε}(d_{H}), we have

|B_{stb}(ε, r)| ≤ |B(ε, r)| < ε\binom{n}{r}

for all r ≤ d_{H}.

Let us fix a triangle-free graph H as in the statement of Lemma 30. We shall also fix a d_{H}-degenerate ordering v_{1}, …, v_{k} of the vertices of H. As before, we let H_{h} = H[{v_{1}, …, v_{h}}] (1 ≤ h ≤ k). The next definition introduces several important terms for our proof.

Definition 37. For (i)–(iii) below, we suppose that 1 < h ≤ k.

(i) An embedding f: V (H_{h−1}) → V (G_{n}) is clean if the set f(N_{H_{h}}(v_{h})) is not ε-bad; i.e., f(N_{H_{h}}(v_{h})) ∉ B_{stb}(ε, r) for any r with 1 ≤ r ≤ d_{H}. Otherwise f is polluted. When we use the terms ‘clean’ and ‘polluted’, the value of ε will be clear from the context.

(ii) Set

E_{poll}(H_{h−1}, G_{n}) = {f ∈ E(H_{h−1}, G_{n}): f is polluted}.

(iii) Finally, set

E_{clean}^{ind}(H_{h−1}, G_{n}) = {f ∈ E(H_{h−1}, G_{n}): f is clean and induced}.

Now we are ready to state another corollary of the Extension Lemma, Corollary 38 below. This corollary, along with Corollary 36, will be the key ingredients in the proof of Lemma 30.

Corollary 38. Let ε > 0, C > 1, and k ≥ 4 be fixed. Suppose 1 < h ≤ k and set r = deg_{H_{h}}(v_{h}). If G_{n} ∈ BDD(C, D_{H}) satisfies TUPLE_{ε}(d_{H}), then

|E_{poll}(H_{h−1}, G_{n})| ≤ εC^{h−r−1}n^{h−1}p^{e(H_{h−1})},

where p = e(G_{n})\binom{n}{2}^{−1}. In particular, for any η > 0, C > 1, and k, there is an ε > 0 that guarantees that |E_{poll}(H_{h−1}, G_{n})| ≤ ηn^{h−1}p^{e(H_{h−1})}.

Proof. By definition, an embedding f of H_{h−1} in G_{n} is polluted if f(N_{H_{h}}(v_{h})) ∈ B_{stb}(ε, r). Fix an r-tuple F such that F^{set} = N_{H_{h}}(v_{h}). We have

E_{poll}(H_{h−1}, G_{n}) = ⋃_{X} E(H_{h−1}, G_{n}, F, X),

where the union is taken over all r-tuples X such that X^{set} ∈ B_{stb}(ε, r). Therefore

|E_{poll}(H_{h−1}, G_{n})| ≤ ∑_{X} |E(H_{h−1}, G_{n}, F, X)|,  (15)

where the sum is over the same r-tuples X. Since TUPLE_{ε}(d_{H}) holds for G_{n} and r = deg_{H_{h}}(v_{h}) ≤ d_{H}, the number of r-tuples X that we are summing over in (15) is at most εn^{r}. Observe also that N_{H_{h}}(v_{h}) is a stable set in H_{h}, because H_{h} ⊂ H is triangle-free. We now apply Lemma 34 to deduce from (15) that |E_{poll}(H_{h−1}, G_{n})| is at most

εn^{r} × C^{h−r−1}n^{h−r−1}p^{e(H_{h−1})} = εC^{h−r−1}n^{h−1}p^{e(H_{h−1})},

and our corollary follows.

We are now ready to prove Lemma 30. We start by outlining the idea of the proof.

Proof strategy for Lemma 30. The proof uses an inductive argument. To keep the induction step working, we need the Extension Lemma, Lemma 34. This lemma yields an upper bound on the number of those “copies” of H in G_{n} that contain a fixed copy of H[F] ⊂ H for some F ⊂ V (H).

Next, we use Corollary 36 to infer that most of the copies of H in G_{n} are induced copies. Then we further restrict the domain to a certain class of embeddings, called clean embeddings, and show that the number of polluted (i.e., not clean) embeddings is negligible. This enables us to reduce the proof of Lemma 30 to the special case when the embeddings of H in G_{n} are clean and induced.

Proof of Lemma 30. Throughout this proof, we suppose that C > 1 is a fixed constant and that G_{n} ∈ BDD(C, D_{H}). We let p = e(G_{n})\binom{n}{2}^{−1}, and suppose that np^{d_{H}} ≥ np^{D_{H}} ≫ 1. Recall that we have a fixed d_{H}-degenerate ordering v_{1}, …, v_{k} of the vertices of H, and that H_{h} = H[{v_{1}, …, v_{h}}] (1 ≤ h ≤ k).

We shall prove by induction on h that

(**) for all 1 ≤ h ≤ k and all δ > 0, there is ε > 0 such that if G_{n} satisfies TUPLE_{ε}(d_{H}), then

|E(H_{h}, G_{n})| ∼_{δ} n^{h}p^{e(H_{h})},  (16)

as long as n is sufficiently large.

Note that (16) clearly holds for any δ > 0 for h = 1. Now suppose that 1 < h ≤ k and that (16) holds for smaller values of h for all δ > 0. Let δ > 0 be given. We wish to show that (16) holds if G_{n} satisfies TUPLE_{ε}(d_{H}) for small enough ε and n is large enough.

We start by showing the lower bound, that is, |E(H_{h}, G_{n})| > (1−δ)n^{h}p^{e(H_{h})}. Let δ′ = min{δ/4, δ/2C}, and let ε′ = ε′(δ′) be the value of ε given by the induction hypothesis to guarantee that

|E(H_{h−1}, G_{n})| ∼_{δ′} n^{h−1}p^{e(H_{h−1})},  (17)

as long as n is sufficiently large. Now put η = δ′/2. Corollary 36 tells us that if n is large enough, then

|E^{ni}(H_{h−1}, G_{n})| ≤ ηn^{h−1}p^{e(H_{h−1})}.  (18)

Also, let ε′′ = ε′′(η) be the value of ε whose existence is guaranteed in Corollary 38 to ensure that

|E_{poll}(H_{h−1}, G_{n})| ≤ ηn^{h−1}p^{e(H_{h−1})}.  (19)

We now let ε = min{ε′, ε′′, δ/8}, and claim that this choice of ε will do. Our induction step is reduced to proving this claim.

For future reference, observe that we have

(1 − 2δ′)(1 − 2ε) ≥ 1 − δ,  (20)
(1 + δ′)(1 + ε) ≤ 1 + \frac{δ}{2},  (21)

and

δ′C ≤ \frac{δ}{2}.  (22)

Let r = deg_{H_{h}}(v_{h}) ≤ d_{H}. Note that then e(H_{h−1}) = e(H_{h}) − r. By our choice of ε, if n is sufficiently large, then the number of embeddings in E(H_{h−1}, G_{n}) that are polluted or non-induced is

≤ 2ηn^{h−1}p^{e(H_{h−1})} = δ′n^{h−1}p^{e(H_{h−1})} = δ′n^{h−1}p^{e(H_{h})−r}

(see (18) and (19)). Hence, by (17), the number |E_{clean}^{ind}(H_{h−1}, G_{n})| of clean induced embeddings of H_{h−1} in G_{n} is such that

(1 − 2δ′)n^{h−1}p^{e(H_{h})−r} < |E_{clean}^{ind}(H_{h−1}, G_{n})| < (1 + δ′)n^{h−1}p^{e(H_{h})−r}. (23)

Given f′ ∈ E_{clean}^{ind}(H_{h−1}, G_{n}), we may estimate from below the number of embeddings f ∈ E(H_{h}, G_{n}) that extend f′ as follows. Since f′ is clean, by definition f′(N_{H_{h}}(v_{h})) ∉ B_{stb}(ε, r). Equivalently, either

(a) f′(N_{H_{h}}(v_{h})) is not a stable set in G, or

(b) |N_{G_{n}}(N_{H_{h}}(v_{h})) − np^{r}| < εnp^{r} holds.

Since H is triangle-free, the set N_{H_{h}}(v_{h}) is a stable set in H_{h}. Since f′ is induced, the set f′(N_{H_{h}}(v_{h})) is also a stable set and consequently (a) fails to hold. Thus (b) must hold, that is,

|N_{G_{n}}(N_{H_{h}}(v_{h})) − np^{r}| < εnp^{r}.  (24)

Note that, to obtain an extension f ∈ E(H_{h}, G_{n}) of f′, we must simply select f(v_{h}) in N_{G_{n}}(f′(N_{H_{h}}(v_{h}))) \ f′(V (H_{h−1})). Consequently, the number of extensions of f′ to embeddings of H_{h} in G_{n} is at least

|N_{G_{n}}(f′(N_{H_{h}}(v_{h}))) \ f′(V (H_{h−1}))|

≥ (1 − ε)np^{r} − (h − 1) ≥ (1 − 2ε)np^{r}, (25)

where we used (24), the fact that np^{r} ≥ np^{d_{H}} ≫ 1, and that n is large. Combining (20), the lower bound in (23), and (25), we obtain that

|E(H_{h}, G_{n})| > (1 − 2δ′)n^{h−1}p^{e(H_{h})−r}(1 − 2ε)np^{r} ≥ (1 − δ)n^{h}p^{e(H_{h})}. (26)

Now we need to show that |E(H_{h}, G_{n})| < (1+δ)n^{h}p^{e(H_{h})}. Fix f′ ∈ E(H_{h−1}, G_{n}). The number of extensions of f′ to embeddings of H_{h} in G_{n} is bounded from above by

|N_{G_{n}}(f′(N_{H_{h}}(v_{h})))|.  (27)

If, furthermore, f′ ∈ E_{clean}^{ind}(H_{h−1}, G_{n}), then we know that (24) holds and hence the quantity in (27) is ≤ (1 + ε)np^{r}. Combining this fact with the upper bound in (23) and recalling (21), we obtain that the number of embeddings f ∈ E(H_{h}, G_{n}) whose restrictions to V (H_{h−1}) are in E_{clean}^{ind}(H_{h−1}, G_{n}) is

< (1 + δ′)n^{h−1}p^{e(H_{h})−r}(1 + ε)np^{r}

= (1 + δ′)(1 + ε)n^{h}p^{e(H_{h})} ≤ (1 + \frac{δ}{2}) n^{h}p^{e(H_{h})}. (28)

We already know that |E(H_{h−1}, G_{n})\E_{clean}^{ind}(H_{h−1}, G_{n})| ≤ δ′n^{h−1}p^{e(H_{h})−r}. Since r = deg_{G_{n}}(v_{h}) ≤ d_{H} ≤ D_{H} and G_{n} ∈ BDD(C, D_{H}), each such embedding f′ gives rise to ≤ Cpn^{r} embeddings f ∈ E(H_{h}, G_{n}). Therefore, the number of embeddings f ∈ E(H_{h}, G_{n}) whose restrictions to V (H_{h−1}) are not in E_{clean}^{ind}(H_{h−1}, G_{n}) is, by (22),

≤ δ′n^{h−1}p^{e(H_{h})−r} × Cnp^{r} ≤ \frac{δ}{2}n^{h}p^{e(H_{h})}.  (29)

From (28) and (29), we deduce that

|E(H_{h}, G_{n})| < (1 + δ)n^{h}p^{e(H_{h})}.  (30)

Inequalities (26) and (30) complete our induction step, and hence (**) follows by induction. Lemma 30 follows on taking h = k in (**).

3.2.4 Proof of Theorem 16

In this short section, we observe that we have already done all the work to prove Theorem 16. Indeed, let H and {G_{n}}_{n=1}^{∞} be as in the statement of Theorem 16. We first observe that we may boost hypothesis (iii) in the statement of that theorem to TUPLE(d_{H}), by applying Lemma 29. But then we are in condition to apply Lemma 30. We leave the details to the reader.

3.3 Proof of Theorem 23

Throughout this section, H will be a (not necessarily triangle-free) graph on k vertices and e edges. Recall that we denote the set of embedding of H in a graph G by E(H, G). The set of induced embeddings of H in G will be denoted by E^{ind}(H, G), and the set of non-induced embeddings of H in G will be denoted by E^{ni}(H, G).

To prove Theorem 23, we need to prove the implications

NSUB(k + 1) ⇒ INDTUP(k − 1)

and INDTUP(k − 1) ⇒ NSUB(k),

for all appropriate sequences of graphs {G_{n}}_{n=1}^{∞}. The implications above will be proved in Lemmas 39 and 41 below.

Lemma 39. Let k ≥ 3 and C > 1 be fixed. Let p = p(n) = o(1) be a function of n satisfying np^{k−1} ≫ 1. Then

NSUB(k + 1) ⇒ INDTUP(k − 1)

for any sequence of graphs \{G_{n}\}_{n=1}^{∞} with p = p(n) = e(G_{n})\binom{n}{2}^{−1} and G_{n} ∈ BDD(C, k − 1) for all n.

Proof. We shall be somewhat sketchy in this proof. Let the sequence of graphs {G_{n}}_{n=1}^{∞} be as in the statement of our lemma. Suppose that INDTUP(k − 1) fails to hold. We will show that NSUB(k + 1) fails to hold as well. By definition of INDTUP(k − 1), we know that there are integers 1 ≤ r < k and 0 ≤ t ≤ \binom{r}{2} for which we have

| Bad^{ind}(r, t)| ≠ o(n^{r}p^{t}),  (31)

where

Bad^{ind}(r, t) = {X ⊂ V (G_{n}): |X| = r, e(X) = t, and |N(X) − np^{r}| ≠ o(np^{r})}.

Given a graph F with r vertices and t edges, let E(F, G_{n}; Bad^{ind}(r, t)) be the set of induced embeddings f of F in G_{n} with the image f(V (F)) of f in the family Bad^{ind}(r, t). Formally,

E(F, G_{n}; Bad^{ind}(r, t)) = {f ∈ E^{ind}(F, G_{n}): f(V (F)) ∈ Bad^{ind}(r, t)}.

Observe that there are at most \binom{\binom{r}{2}}{t} graphs on r vertices and t edges that can be induced on X ∈ Bad^{ind}(r, t). Hence we deduce from (31) that there is a graph F with r vertices and t edges such that

|E(F, G_{n}; Bad^{ind}(r, t))| ≠ o(n^{r}p^{t}).  (32)

Unwinding the definitions, we see that (32) means that the number of induced embeddings f of F in G_{n} failing to satisfy

|N(f(V (F)))| ∼ np^{r}

fails to be o(n^{r}p^{t}).

Suppose now that the vertices of F are u_{1}, …, u_{r}. Let u_{r+1} and u_{r+2} be two new vertices. We let F_{1} be the graph obtained from F by adding u_{r+1} to F and joining it to all vertices in F. Moreover, we let F_{2} be the graph obtained from F_{1} by adding u_{r+2} to F_{1} and joining it to all vertices in F. Note that u_{r+1} and u_{r+2} are not adjacent in F_{2}. Finally, we let F_{3} be obtained from F_{2} by adding the edge {u_{r+1}, u_{r+2}}. For convenience, put F_{0} = F.

In Claim 40 below, we prove that

|E^{ind}(F_{i}, G_{n})| ≁ n^{|V (F_{i})|}p^{|E(F_{i})|},

for some i, 0 ≤ i ≤ 3. Consequently NSUB(k +1) fails, which is a contradiction. This contradiction proves Lemma 39.

Claim 40. For some i, 0 ≤ i ≤ 3, we have

|E^{ind}(F_{i}, G_{n})| ≁ n^{|V (F_{i})|}p^{|E(F_{i})|}.

Proof. Assume for a contradiction that the number of embeddings of F_{i} in G_{n} (0 ≤ i ≤ 3) is ∼ n^{|V (F_{i})|}p^{|E(F_{i})|}. We will show that

|E(F, G_{n}; Bad^{ind}(r, t))| = o(n^{r}p^{t}),

which would contradict (32).

Since p = o(1), we may deduce from Corollary 36 that the number of induced embeddings |E^{ind}(F_{i}, G_{n})| of F_{i} in G_{n} satisfies

|E^{ind}(F_{i}, G_{n})| ∼ n^{|V (F_{i})|}p^{|E(F_{i})|},  (33)

for all 0 ≤ i ≤ 3.

For each induced embedding f of F to G_{n}, put

d(f) = |N(f(V (F)))|;

that is, d(f) is the number of joint neighbors of the vertices in the image of f. Clearly, we have

|E^{ind}(F_{1}, G_{n})| = ∑{d(f): f ∈ E^{ind}(F, G_{n})}.  (34)

Moreover, by (33) and the fact that p = o(1), we have that

|E^{ind}(F_{2}, G_{n})| ∼ |E^{ind}(F_{2}, G_{n})| + |E^{ind}(F_{3}, G_{n})|

= ∑{d(f)(d(f) − 1): f ∈ E^{ind}(F, G_{n})}. (35)

Note that (33) and (34) imply that

∑{d(f): f ∈ E^{ind}(F, G_{n})} ∼ n^{r+1}p^{t+r} ∼ |E^{ind}(F, G_{n})|np^{r}.  (36)

Since np^{r} ≥ np^{k−1} ≫ 1, we may deduce from (36) that

∑_{f} d(f)^{2} ≥ \frac{1}{|E^{ind}(F, G_{n})|}( ∑_{f} d(f))^{2} ≫ ∑_{f} d(f),  (37)

where all the sums above are over f ∈ E^{ind}(F, G_{n}). Combining (33), (35), and (37), we deduce that

∑{d(f)^{2} : f ∈ E^{ind}(F, G_{n})} ∼ n^{r+2}p^{t+2r} ∼ |E^{ind}(F, G_{n})| (np^{r})^{2} .  (38)

In view of (36) and (38), we may now simply apply Lemma 26 to deduce that

d(f) = |N(f(V (F)))| ∼ np^{r}

for (1−o(1))|E^{ind}(F, G_{n})| ∼ n^{r}p^{t} embeddings f ∈ E^{ind}(F, G_{n}). This means that

|E(F, G_{n}; Bad^{ind}(r, t))| = o(n^{r}p^{t}).

However, as observed above, this contradicts (32). Thus the claim holds.

We now prove the implication

INDTUP(k − 1) ⇒ NSUB(k),

for all appropriate sequences of graphs {G_{n}}_{n=1}^{∞}. We in fact give a more precise assertion in Lemma 41 below.

Lemma 41. Let δ > 0, C > 1 and k ≥ 3 be fixed. Let H be a (not necessarily triangle-free) graph on k vertices, and let p = p(n) = o(1) be a function of n satisfying np^{D_{H}} ≫ 1. Then there exist ε > 0 and an integer n_{3} for which the following holds. If a sequence of graphs {G_{n}}_{n=1}^{∞} is such that, for all n,

(i) G_{n} ∈ BDD(C, D_{H}),

(ii) p = p(n) = e(G_{n})\binom{n}{2}^{−1},

(iii) INDTUP_{ε}(d_{H}) holds for G_{n},

then the number of embedding of H in G_{n} is

N(H, G_{n}) ∼_{δ} n^{k}p^{e}

for all n ≥ n_{3}, where e = |E(H)|.

Proof. The proof of this lemma is very similar to the proof of Lemma 30, and hence we shall only sketch an informal proof.

We shall assume throughout that C > 1 and k ≥ 3 are fixed constants and that G_{n} ∈ BDD(C, D_{H}) for all n, where {G_{n}}_{n=1}^{∞} is as in the statement of our lemma. Let us also fix a graph H as in the statement of our lemma. As in the proof of Lemma 30, we shall also fix a d_{H}-degenerate ordering v_{1}, …, v_{k} of the vertices of H. As before, if 1 ≤ h ≤ k, we shall write H_{h} for the graph H[{v_{1}, …, v_{h}}] induced by {v_{1}, …, v_{h}} in H.

We shall prove by induction on h that

(†) for all 1 ≤ h ≤ k, if property INDTUP(d_{H}) holds for {G_{n}}_{n=1}^{∞}, then

|E(H_{h}, G_{n})| ∼ n^{h}p^{e(H_{h})}.  (39)

Note that (†) is trivially true for h = 1. Now suppose that 1 < h ≤ k and that (†) holds for smaller values of h. We need to show that (39) holds assuming that INDTUP(d_{H}) holds.

By Corollary 36, we know that

|E^{ni}(H_{h−1}, G_{n})| = o(n^{h−1}p^{e(H_{h−1})}).  (40)

From the induction hypothesis and (40), we may deduce that

|E^{ind}(H_{h−1}, G_{n})| ∼ n^{h−1}p^{e(H_{h−1})}.  (41)

We now need to introduce some notation. Let r = deg_{H_{h}}(v_{h}), and suppose that the neighborhood N_{H_{h}}(v_{h}) of v_{h} in H_{h} induces t edges in H_{h}. Clearly, N_{H_{h}}(v_{h}) induces t edges in H_{h−1} as well. As in the proof of Lemma 39, we put

Bad^{ind}(r, t) = {X ⊂ V (G_{n}): |X| = r, e(X) = t, and |N(X) − np^{r}| ≠ o(np^{r})}.

In words, Bad^{ind}(r, t) is the family of the r-element sets of vertices of G_{n} that induce t edges in G_{n} and fail to have a joint neighborhood of cardinality ∼ np^{r}.

Since r = deg_{H_{h}}(v_{h}) ≤ d_{H} and we are assuming that INDTUP(d_{H}) holds, we have

| Bad^{ind}(r, t)| = o(n^{r}p^{t}).  (42)

We now let

E(H_{h−1}, G_{n}; Bad^{ind}(r, t)) = {f ∈ E^{ind}(H_{h−1}, G_{n}): f(N_{H_{h}}(v_{h})) ∈ Bad^{ind}(r, t)}.

We will need the following claim, Claim 42. We delay its proof until the end of this section.

Claim 42. We have

|E(H_{h−1}, G_{n}; Bad^{ind}(r, t))| = o(n^{h−1}p^{e(H_{h−1})}).  (43)

Assuming Claim 42, we proceed with the proof of Lemma 41.

If f is an embedding of H_{h−1} in G_{n}, let us write d(f) for the number of extensions of f to embeddings of H_{h} in G_{n}. Note that

(‡) if

f ∈ E^{ind}(H_{h−1}, G_{n}) \ E(H_{h−1}, G_{n}; Bad^{ind}(r, t)),  (44)

then

d(f) ∼ np^{r}.  (45)

Observation (‡), relation (41), and Claim 42 imply that

|E(H_{h}, G_{n})| ≳ n^{h−1}p^{e(H_{h−1})} × np^{r} = n^{h}p^{e(H_{h})}.  (46)

We now need to estimate |E(H_{h}, G_{n})| from above. Note that any embedding f of H_{h−1} in G_{n} extends to ≤ Cnp^{r} embeddings of H_{h} in G_{n}, because we are assuming that G_{n} ∈ BDD(C, D_{H}) and r = deg_{H_{h}}(v_{h}) ≤ d_{H} ≤ D_{H}. In particular, if

f ∈ E^{ni}(H_{h−1}, G_{n}) ∪ E(H_{h−1}, G_{n}; Bad^{ind}(r, t)),  (47)

then d(f) ≤ Cnp^{r}. Inequality (40) and Claim 42 imply that the number of embeddings f as in (47) is o(n^{h−1}p^{e(H_{h−1})}). It follows that the number of embeddings of H_{h} in G_{n} that extend embeddings f as in (47) is o(n^{h}p^{e(H_{h})}).

Finally, we observe that if an embedding f ∈ E(H_{h−1}, G_{n}) is not as in (47), then it must be as in (44). Recalling (‡), we see that the total number of embeddings of H_{h} in G_{n} is ∼ n^{h}p^{e(H_{h})}. The proof of the induction step is therefore complete, and hence (†) follows by induction. Naturally, Lemma 41 follows by setting h = k in (†).

Now we present the proof of Claim 42, which is a slight extension of the proof of Corollary 38.

Proof of Claim 42. By definition

E(H_{h−1}, G_{n}; Bad^{ind}(r, t))
= {f ∈ E^{ind}(H_{h−1}, G_{n}): f(N_{H_{h}}(v_{h})) ∈ Bad^{ind}(r, t)}.

Fix an r-tuple F such that F^{set} = N_{H_{h}}(v_{h}). By the above definition and the fact that G_{n} satisfies INDTUP(k − 1), we have

|E(H_{h−1}, G_{n}; Bad^{ind}(r, t))| = ∑_{X} |E(H_{h−1}, G_{n}, F, X)|,  (48)

where the sum is over all r-tuples X such that X^{set} ∈ Bad^{ind}(r, t). By (42), the number of r-tuples X that we are summing over in (48) is at most

r! × o(n^{r}p^{t}) = o(n^{r}p^{t}).

For each r-tule X, we apply the Extension Lemma (Lemma 34) to

E(H_{h−1}, G_{n}, F, X)

and deduce from (48) that

|E(H_{h−1}, G_{n}; Bad^{ind}(r, t))| ≤ o(n^{r}p^{t}) × C^{(h−1)−r}n^{(h−1)−r}p^{e(H_{h−1})−t}
= o(n^{h−1}p^{e(H_{h−1})}).  (49)

This concludes the proof of Claim 42.

3.4 Remarks about Theorem 25 (the directed case)

We omit the proof of Theorem 25 (stated in Section 2.2) and make a few remarks about its connection to the undirected case.

Theorem 25 is the directed version of the Embedding Lemma (Theorem 16). Its proof goes along the lines of the the proof of the Embedding Lemma. That is, it uses the directed versions of the Extension Lemma (Lemma 34), Lemma 29, Lemma 30 and Corollary 36. However the proof of the directed versions of the Extension Lemma, Lemma 30 and Corollary 36 are very similar to the proofs for the undirected case. Thus we omit those proofs.

We shall rather state and prove Lemma 43, which is the directed analogue of Lemma 29. Then at the end of this section we briefly say how to deduce Lemma 29 from Lemma 43.

We follow the same notation as in the beginning of Section 2.2. Let G⃗ = (V, E⃗) be a digraph, π = (π_{1}, …, π_{r}) ∈ {+, −}^{r}, and (u_{1}, …, u_{r}) ∈ V^{r}. We let d^{π}(u_{1}, …, u_{r}) = |N^{π}(u_{1}, …, u_{r})|, where

N^{π}(u_{1}, …, u_{r}) = {w ∈ V : ∀i ∈ [r], (u_{i}, w) ∈ E⃗ if π_{i} = +

and (w, u_{i}) ∈ E⃗ if π_{i} = −}. (50)

Lemma 43. Let t ≥ 2 be an integer and let G⃗ = (V, E⃗) be a digraph on n vertices satisfying the following conditions:

(a) for all but o(n) vertices u ∈ V,

d^{+}(u) = \frac{1}{2}pn(1 + o(1)),

(b)

∑_{(u,v)∈V^{2}} (d^{++}(u, v))^{2} = n^{2}(\frac{p^{2}n}{4})^{2}(1 + o(1)).

If p = p(n) ≫ n^{−1/t} and G⃗ ∈ \overrightarrow{BDD}(C, 2), then, for all 2 ≤ r ≤ t, for all π ∈ {+, −}^{r}, and for all but o(n^{r}) r-tuples (u_{1}, …, u_{r}) ∈ V^{r}, we have

d^{π}(u_{1}, …, u_{r}) = \frac{1}{2^{r}} p^{r}n(1 + o(1)).

Proof. First we show that

(c) for all but o(n) vertices u ∈ V, we have

d^{−}(u) = \frac{1}{2}pn(1 + o(1)).

To that end, we first observe that

∑_{a∈V} d^{−}(a) = ∑_{u∈V} d^{+}(u).  (51)

Condition (a) above and the fact that all vertices have degree ≤ Cpn imply that

∑_{u∈V} d^{+}(u) = n (\frac{pn}{2}) (1 + o(1)) + o(n)Cpn = n (\frac{pn}{2}) (1 + o(1)).  (52)

Moreover, by the Cauchy–Schwarz inequality and (b) above, we have

∑_{a∈V} d^{−}(a)^{2} = ∑_{(u,v)∈V^{2}} d^{++}(u, v) ≤ n{ ∑_{(u,v)∈V^{2}} d^{++}(u, v)^{2}}^{1/2}

≤ n (\frac{pn}{2})^{2} (1 + o(1)). (53)

Lemma 26 and (51), (52), and (53) now imply that (c) above does indeed hold. We may deduce from (c) that

∑_{(u,v)∈V^{2}} d^{++}(u, v) = ∑_{a∈V} d^{−}(a)^{2} ≥ n^{2} (\frac{p^{2}n}{4}) (1 + o(1)).  (54)

Lemma 26, condition (b) and (54) now imply that (d) for all but o(n^{2}) pairs (u, v) ∈ V^{2}, we have

d^{++}(u, v) = \frac{1}{4}p^{2}n(1 + o(1)).

Similarly, we may deduce that

(e) for all but o(n^{2}) pairs (u, v) ∈ V^{2}, we have

d^{−−}(u, v) = \frac{1}{4}p^{2}n(1 + o(1)).

Indeed, this is a consequence of Lemma 26 and the identities

∑_{(u,v)∈V^{2}} d^{−−}(u, v) = ∑_{a∈V} d^{+}(a)^{2}

and

∑_{(u,v)∈V^{2}} d^{−−}(u, v)^{2} = ∑_{(a,b)∈V^{2}} d^{++}(a, b)^{2}.

Having established the auxiliary facts (c)–(e), we are now in position to verify Lemma 43. For π = (π_{1}, …, π_{r}) ∈ {+, −}^{r}, let P (π) = |{i: π_{i} = +}| and Q(π) = r − P_{π}. We write u = (u_{1}, …, u_{r}) for a general element in V^{r}. We have

∑_{u∈V^{r}} d^{π}(u) = ∑_{a∈V} d^{−}(a)^{P (π)}d^{+}(a)^{Q(π)}.  (55)

Condition (a) and property (c) deduced above and the fact that all vertices have degree ≤ Cpn allows us to conclude that the right-hand side of (55) is ∼ n(pn/2)^{r} = n^{r}(p^{r}n/2^{r}), so that

∑_{u∈V^{r}} d^{π}(u) = n^{r} (\frac{1}{2^{r}} p^{r}n) (1 + o(1)).  (56)

We now observe that

∑_{u∈V^{r}} d^{π}(u)^{2} = ∑_{(a,b)∈V^{2}} (d^{−−}(a, b))^{P (π)}(d^{++}(a, b))^{Q(π)}.  (57)

Properties (d) and (e) deduced above and the fact that all pairs of vertices have joint degree ≤ Cp^{2}n allows us to conclude that the right-hand side of (57) is ∼ n^{2}(p^{2}n/4)^{r} = n^{r}(p^{r}n/2^{r})^{2}, so that

∑_{u∈V^{r}} d^{π}(u)^{2} = n^{r} (\frac{1}{2^{r}} p^{r}n)^{2} (1 + o(1)).  (58)

Finally, Lemma 26 and (56) and (58) imply that for all but o(n^{r}) r-tuples u ∈ V^{r}, we have

d^{π}(u) = \frac{1}{2^{r}} p^{r}n(1 + o(1)),

which concludes the proof of Lemma 43.

Now we present a sketch of the proof of Lemma 29 (introduced in Section 3), based on Lemma 43. We start by restating Lemma 29 in the following equivalent form.

Lemma 44. Suppose t ≥ 2 and C > 1 are constants and p = p(n) satisfies np^{t} ≫ 1. Let {G_{n}}_{n=1}^{∞} be a sequence of graphs with G_{n} ∈ BDD(C, 2) for all n and |E(G_{n})| = (1 + o(1))p\binom{n}{2}. If

(a) for all but o(n) vertices u ∈ V (G_{n}),

deg_{G_{n}}(u) = pn(1 + o(1)),

(b) for all but at most o(n^{2}) pairs {x_{1}, x_{2}} ⊂ V (G_{n}),

|N_{G_{n}}(x_{1}) ∩ N_{G_{n}}(x_{2})| = p^{2}n(1 + o(1)),

then, for all r ∈ [t], all but at most o(n^{r}) r-element sets {x_{1}, …, x_{r}} ⊂ V (G_{n}) are such that

|N_{G_{n}}(x_{1}) ∩ ⋯ ∩ N_{G_{n}}(x_{r})| = p^{r}n(1 + o(1)).

Sketch of the proof of Lemma 44. Lemma 44 follows from Lemma 43. Suppose we are given a graph G_{n} as above; we then randomly orient its edges to get G⃗_{n}. One can easily show that the hypothesis of Lemma 43 holds almost surely for G⃗_{n}. Finally, note that if G⃗_{n} satisfies the conclusion of Lemma 43, then G_{n} satisfies the conclusion of Lemma 44.

4 Auxiliary facts and related work

4.1 General facts

We have used Facts 45 and 46 given below. Recall that, for two graphs X and Y, the set of all embeddings of X in Y is denoted by E(X, Y).

Fact 45. Let k ≥ 1 be a fixed integer. For any sequence of graphs {G_{n}}_{n=1}^{∞}, we have

NSUB(k + 1) ⇒ NSUB(k).

Proof. Suppose \{G_{n}\}_{n=1}^{∞} satisfies NSUB(k+1) and let p = p(n) = |E(G_{n})|\binom{n}{2}^{−1}. To prove this fact, we have to show that, for any graph H on k vertices, we have

|E(H, G_{n})| = (1 + o(1))n^{k}p^{e},  (59)

where e = |E(H)|. Given a graph H as above we construct H^{+} where V (H^{+}) = V (H) ∪ {u} and E(H^{+}) = E(H). By definition of H^{+}, it follows that

|E(H^{+}, G_{n})| = N(H, G_{n})(n − k).  (60)

By hypothesis, we know that {G_{n}}_{n=1}^{∞} satisfies NSUB(k + 1). Thus

|E(H^{+}, G_{n})| = (1 + o(1))n^{k+1}p^{e}.  (61)

Combining (60) and (61), we obtain (59).

Similarly, we may prove the following simple fact.

Fact 46. Let k ≥ 1 be a fixed integer. For any sequence of graphs {G_{n}}_{n=1}^{∞}, we have

TFSUB(k + 1) ⇒ TFSUB(k).

4.2 Proof of Proposition 6

In this section, we shall sketch the proof of Proposition 6(A) and we shall prove Proposition 6(B) using a construction due to Alon [2].

Proof of Proposition 6 (A). We only outline the proof of Proposition 6(A), because a similar result is proved in [13] (see Theorem B′ in [13]). The graphs G_{i} satisfying properties (i) and (ii) above can be constructed from sparse random graphs whose triangles have been destroyed by the removal of a small fraction of the edges. Replacing each vertex of such a triangle-free “random like graph” by a stable set of appropriate cardinality and each edge by a complete bipartite graph yields suitable graphs G_{i}.

The proof of Proposition 6(B) is based on a family of graphs constructed by Alon [2].

4.2.1 Construction of Alon’s graph

Let k > 1 be an integer not divisible by 3 and let F_{k} = GF(2^{k}) be the Galois field with 2^{k} elements. Depending on the context, we will think of the elements of F_{k} as polynomials over GF(2) or as binary vectors of length k (whose entries are the coefficients of the corresponding polynomial representations). If u and v are two vectors, we will denote their concatenation by u ∘ v.

For any α ∈ F_{k} − {0}, we put the vector α in W_{0} if the constant term of the polynomial α^{7} is 0. Otherwise we put α in W_{1}. Let Γ = (ℤ_{2})^{3k} be the Abelian group with elements the binary vectors of length 3k. Let U_{0} = {w_{0} ∘ w_{0}^{3} ∘ w_{0}^{5} : w_{0} ∈ W_{0}} and U_{1} = {w_{1} ∘ w_{1}^{3} ∘ w_{1}^{5} : w_{1} ∈ W_{1}}. Note that

|U_{0}| = |W_{0}| = 2^{k−1} − 1  and  |U_{1}| = |W_{1}| = 2^{k−1}.

In the following, we will use bold letters to denote vectors of length 3k to distinguish them from vectors of length k.

The Alon graph G = G(Γ) is defined to be the Cayley graph on Γ with generating set

S = U_{0} + U_{1} = {u_{0} + u_{1} : u_{0} ∈ U_{0}, u_{1} ∈ U_{1}} ⊂ Γ.

In other words V (G) = Γ = (ℤ_{2})^{3k} and x, y ∈ V (G) form an edge in G if and only if x + y ∈ S. Let M_{0} (resp. M_{1}) be the 3k × (2^{k−1} − 1) (resp. 3k × 2^{k−1}) matrix whose columns are the vectors in U_{0} (resp. U_{1}). Consider the matrix M = [M_{0}, M_{1}]. It turns out that M is the parity check matrix of a BCH code of designed distance 7. Alon showed that the graph G has the following properties:

(a) G is triangle-free,

(b) G is d = |S| = 2^{k−1}(2^{k−1} − 1)-regular,

(c) The second largest eigenvalue of the adjacency matrix of G has size Θ(2^{k}).

Roughly speaking, properties (a) and (b) follow from the fact any 6 columns in M are linearly independent over GF(2). Property (c) is much more delicate, and depends on the Carlitz–Uchiyama bound for the Hamming weight of dual code words of BCH codes. We refer the reader to Alon [2] for details.

Proof of Proposition 6 (B). From the above discussion, it follows that for each k > 1 not divisible by 3, we have an Alon graph G with the properties (a), (b) and (c) listed above. Let {G_{i}}_{i=1}^{∞} be the family of all such graphs G (ordered according to |V (G_{i})|).

We prove Proposition 6(B) by showing that the family {G_{i}}_{i=1}^{∞} satisfies (i), (ii), and (iii) of Proposition 6(B).

Observe that (i) of Proposition 6(B) is simply (a) above. Next we prove (ii) of Proposition 6(B). For each G_{i}, we have (by definition) n = |V (G_{i})| = 2^{3k} and d = pn = 2^{k−1}(2^{k−1} − 1). Thus, letting k → ∞ yields

p = (\frac{1}{4} + o(1)) n^{−1/3}.  (62)

Let A = (a_{x,y})_{x,y∈V (G_{i})} denote the 0–1 adjacency matrix of the graph G_{i}, with 1 denoting edges. Let λ_{j} (1 ≤ j ≤ n = 2^{3k}) be the eigenvalues of A and adjust the notation so that λ_{1} ≥ |λ_{2}| ≥ ⋯ ≥ |λ_{n}|. It follows from properties (b) and (c) above that

λ_{1} = d = 2^{k−1}(2^{k−1} − 1)  and  |λ_{2}| = Θ(2^{k}).  (63)

Hence {G_{i}}_{i=1}^{∞} satisfies EIG. By Fact 3 in [6], we have EIG ⇒ DISC. Consequently {G_{i}}_{i=1}^{∞} satisfies DISC as well. Now it remains to show that {G_{i}}_{i=1}^{∞} satisfies property TUPLE(2). Assume for a moment that {G_{i}}_{i=1}^{∞} satisfies property EIG(4), defined as follows:

EIG(4): ∑_{i=1}^{n} |λ_{i}|^{4} = (1 + o(1))p^{4}n^{4}.

By Fact 7 and Theorem 3 in [6], we have EIG(4) ⇒ CYCLE(4). By Fact 28 in Section 3.2, we have CYCLE(4) ⇒ TUPLE(2). Therefore, in order to show that {G_{i}}_{i=1}^{∞} satisfies TUPLE(2), it is enough to show that {G_{i}}_{i=1}^{∞} satisfies EIG(4).

By (63), there exists a constant C such that

λ_{1}^{4} = d^{4} = p^{4}n^{4}  (64)

and

∑_{i=2}^{n} |λ_{i}|^{4} < n(C2^{k})^{4} = C^{4}2^{3k} · 2^{4k} = o(p^{4}n^{4}),  (65)

where in (65) we used that p^{4}n^{4} = 2^{8k}. By (64) and (65), our graph sequence {G_{i}}_{i=1}^{∞} satisfies property EIG(4). This concludes the proof of (ii) of Proposition 6(B).

To complete our proof of Proposition 6(B), it remains to show that the graphs G_{i} satisfy (iii). Since this will take some work, we state this fact as a separate lemma (see Lemma 47 below).

Lemma 47. G_{i} ∈ BDD(128, 2) for all i ≥ 1.

We will use the following simple fact in the proof of Lemma 47.

Fact 48. Suppose a_{1} and a_{2} ∈ F_{k} with a_{1} ≠ 0 are given, and consider the system of equations

\begin{cases}x + y & = a_{1} \\ x^{3} + y^{3} & = a_{2}. \end{cases}  (66)

System (66) has at most two pairs of solutions in F_{k}, namely (x, y) = (α, β) and (x, y) = (β, α) for some α and β ∈ F_{k} with β = α + a_{1} ≠ α.

Proof. By substituting x+a_{1} for y in the second equation of (66), we obtain the quadratic equation a_{1}x^{2} + a_{1}^{2}x + a_{1}^{3} + a_{2} = 0, which has at most two solutions. If α is a solution to the latter equation, then so is β = α + a_{1}, as a simple calculation shows. This implies that the solutions to (66) are as claimed.

Proof of Lemma 47. Since (by definition) G_{i} is d-regular, where d = pn, we have deg_{G_{i}}(x) = pn for all x ∈ V (G_{i}). Thus, it remains to show that for any two vertices x ≠ y in V (G_{i}), we have

|N_{G_{i}}(x) ∩ N_{G_{i}}(y)| ≤ 128p^{2}n.

For x ≠ y ∈ V (G_{i}), the vertex t ∈ V (G_{i}) belongs to N(x) ∩ N(y) if and only if there exist s, s′ ∈ S such that x + t = s and y + t = s′, or, equivalently, x + y = s + s′. Consequently,

|N(x) ∩ N(y)| = |{(s, s′) ∈ S × S: s + s′ = x + y}|.

Set a = x + y = a_{1} ∘ a_{2} ∘ a_{3} where a_{1}, a_{2}, and a_{3} are in F_{k}. Let s = (w_{0} + w_{1}) ∘ (w_{0}^{3} + w_{1}^{3}) ∘ (w_{0}^{5} + w_{1}^{5}) and s′ = (v_{0} + v_{1}) ∘ (v_{0}^{3} + v_{1}^{3}) ∘ (v_{0}^{5} + v_{1}^{5}) where v_{0}, w_{0} ∈ W_{0} and v_{1}, w_{1} ∈ W_{1}. Thus the equation x + y = s + s′ can be written as

\begin{cases}w_{0} + w_{1} + v_{0} + v_{1} & = a_{1} \\ w_{0}^{3} + w_{1}^{3} + v_{0}^{3} + v_{1}^{3} & = a_{2} \\ w_{0}^{5} + w_{1}^{5} + v_{0}^{5} + v_{1}^{5} & = a_{3}. \end{cases}  (67)

For any f ∈ F_{k}, let

f̃ = f ∘ f^{3} ∘ f^{5} = (\begin{matrix}f \\ f^{3} \\ f^{5} \end{matrix}) .

We define

P = {(w̃_{0} + w̃_{1}, ṽ_{0} + ṽ_{1}): w_{0}, v_{0} ∈ W_{0} and w_{1}, v_{1} ∈ W_{1} satisfy (67)}. (68)

Observe that

|N(x) ∩ N(y)| = |{(s, s′) ∈ S × S: s + s′ = x + y}| = |P |.

For each z_{0} ∈ W_{0}, set

P (z_{0}) = {(w̃_{0} + w̃_{1}, ṽ_{0} + ṽ_{1}) ∈ P: w_{0} = z_{0}}.

Since any 6 columns of M are linearly independent, a moment’s thought shows that the sets P (z_{0}) (z_{0} ∈ W_{0}) are pairwise disjoint. Therefore

|N(x) ∩ N(y)| = |P | = ∑_{z_{0}∈W_{0}} |P (z_{0})|.  (69)

Let

T = {z_{0} ∈ W_{0} : |P (z_{0})| > 2}.  (70)

We now state a claim that will be used to finish the proof of Lemma 47.

Claim 49. With the same notation as above, the following holds.

(1 ) |P (z_{0})| ≤ |W_{1}| = 2^{k−1} for all z_{0} ∈ W_{0}.

(2 ) |T | ≤ 2.

The proof of Claim 49 is postponed to the end of Section 4.2. Now we are ready to finish the proof of Lemma 47. By (69) and Claim 49, we have

|P | = ∑_{z_{0}∈W_{0}} |P (z_{0})| = ∑_{z_{0}∈T} |P (z_{0})| + ∑_{z_{0}∈W_{0}\T} |P (z_{0})|

≤ |T | · 2^{k−1} + |W_{0}| · 2 ≤ 2 · 2^{k−1} + (2^{k−1} − 1) · 2 < 4 · 2^{k−1}.

Now, it follows from (69) that

|N(x) ∩ N(y)| = |P | < 4 · 2^{k−1} ≤ 128p^{2}n,

because, as a quick calculation shows, p^{2}n = 2^{k−4}(1 − 1/2^{k−1})^{2} ≥ 2^{k−6}. This concludes the proof of Lemma 47, assuming Claim 49.

It remains to prove Claim 49.

Proof of Claim 49. We shall first prove (1) of Claim 49. Let z_{0} ∈ W_{0}. If |P (z_{0})| ≤ 1 then we are done. Otherwise there exist at least two pairs (z̃_{0} + w̃′_{1}, ṽ′_{0} + ṽ′_{1}), (z̃_{0} + w̃′′_{1}, ṽ′′_{0} + ṽ′′_{1}) ∈ P (z_{0}). From the definition of P (z_{0}) ⊂ P and (67), it follows that

w̃′_{1} + ṽ′_{0} + ṽ′_{1} = w̃′′_{1} + ṽ′′_{0} + ṽ′′_{1}.  (71)

Since any 6 columns of the matrix M are linearly independent (see Alon [2]), each element in {w̃′_{1}, w̃′′_{1}, ṽ′_{0}, ṽ′′_{0}, ṽ′_{1}, ṽ′′_{1}} must occur an even number of times. Since W_{0} ∩ W_{1} = ∅, {v′_{0}, v′′_{0}} ⊂ W_{0} and {v′_{1}, v′′_{1}, w′_{1}, w′′_{1}} ⊂ W_{1}, we have ṽ′_{0} = ṽ′′_{0}. In other words if z_{0} is fixed then ṽ_{0} = { \atop v_{0}(z_{0})} is uniquely determined for all pairs (z̃_{0} + w̃_{1}, ṽ_{0} + ṽ_{1}) ∈ P (z_{0}). By the definition of P (z_{0}) ⊂ P, we have

z̃_{0} + w̃_{1} + { \atop v_{0}(z_{0})} + ṽ_{1} = (\begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix}) .  (72)

We distinguish the following two cases.

Case 1: z̃_{0} + { \atop v_{0}(z_{0})} = ( \begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix} )

In this case, equation (72) implies that w_{1} = v_{1}. Hence the elements of P (z_{0}) are of the form (z̃_{0} + w̃_{1}, { \atop v_{0}(z_{0})} + w̃_{1}), where w_{1} ∈ W_{1} is arbitrary. Thus |P (z_{0})| ≤ |W_{1}| = 2^{k−1}. Hence (1) of Claim 49 holds in this case.

Case 2: z̃_{0} + { \atop v_{0}(z_{0})} ≠ ( \begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix} )

Set

(\begin{matrix}a′_{1} \\ a′_{2} \\ a′_{3} \end{matrix}) = (\begin{matrix}a_{1} \\ a_{2} \\ a_{3} \end{matrix}) + z̃_{0} + { \atop v_{0}(z_{0})} ≠ (\begin{matrix}0 \\ 0 \\ 0 \end{matrix}) .  (73)

Then (72) implies that w_{1} + v_{1} = a′_{1}, w_{1}^{3} + v_{1}^{3} = a′_{2}, and w_{1}^{5} + v_{1}^{5} = a′_{3}. Observe that these equations and (73) imply that a′_{1} ≠ 0 (indeed, otherwise w_{1} = v_{1}, and we would have a′_{1} = a′_{2} = a′_{3} = 0, which contradicts (73)). Now Fact 48 implies that the equations w_{1} + v_{1} = a′_{1} and w_{1}^{3} + v_{1}^{3} = a′_{2} are satisfied by at most two pairs (w_{1}, v_{1}). Hence |P (z_{0})| ≤ 2 ≤ 2^{k−1}, and (1) of Claim 49 is proven.

Now we shall prove (2) of Claim 49. If z_{0} ∈ T then |P (z_{0})| > 2 and it follows from the above discussion that for any (z̃_{0} + w̃_{1}, ṽ_{0} + ṽ_{1}) ∈ P (z_{0}), we have ṽ_{0} = { \atop v_{0}(z_{0})} and w̃_{1} = ṽ_{1}. This observation combined with (72) implies that z_{0} + v_{0}(z_{0}) = a_{1} ≠ 0 and z_{0}^{3} + (v_{0}(z_{0}))^{3} = a_{2}. Then Fact 48 implies that these two equations have at most two solution pairs (z_{0}, v_{0}(z_{0})). Thus |T | ≤ 2, proving (2) of Claim 49.

4.3 Connection to random graphs

4.3.1 Theorem 1 for subgraphs of random graphs

Proposition 6 tells us that the implications “DISC ⇒ NSUB(3)”, “TUPLE(2) ⇒ NSUB(3)” and “EIG ⇒ NSUB(3)” fail to be true when p = o(1). However, counterexamples demonstrating this proposition are rare and “do not occur in random graphs”. Before stating a theorem turning this statement precise, we first introduce some definitions.

Let G(m, q) be the random graph on m vertices and edges chosen independently, each with probability q. Thus for a graph G on m vertices and e edges,

Prob (G(m, q) = G) = q^{e}(1 − q)^{\binom{m}{2}−e}.  (74)

Sometimes, we will view G(m, q) as the set of all 2^{\binom{m}{2}} labeled graphs with m vertices and with the probability distribution given in (74).

For G ∈ G(m, q) and c ∈ (0, 1), let R_{G}(c) be the family of all subgraphs F of G (not necessarily induced and not necessarily spanning) such that

|E(F)| ≥ cq\binom{m}{2}.

Fix integers m ≥ k ≥ 4 and let δ, c, ε > 0 be given. Let F = F(k, δ, c, ε, m) be the family of m-vertex graphs G defined as follows:

G ∈ F iff for any F ∈ R_{G}(c) and any pair of properties

P, Q ∈ {NSUB(k), DISC, EIG, TUPLE(2)}, if F satisfies P_{ε}, then F satisfies Q_{δ}.

Theorem 1 extends for “subgraphs of random graphs” if p → 0 sufficiently slowly. More precisely, we have the following theorem (see [13] and [14]).

Theorem 50. Let k ≥ 4 and δ, c ∈ (0, 1) be given. Suppose that

q ≥ m^{−1/(k−1)}(log m)^{100}.

Then there exists ε > 0 such that, for G ∈ G(m, q), we have

Prob (G ∈ F(k, δ, c, ε, m)) → 1 as m → ∞.

4.3.2 Turán’s problem for subgraphs of random graphs

Theorem 16 implies the following extremal result for subgraphs of random graphs. As usual, we write χ(H) for the chromatic number of a graph H.

Theorem 51. Let H be a triangle-free graph, and consider the random graph G(m, q), where q ≫ m^{−1/D_{H}}. Suppose ε > 0 is fixed. Then, asymptotically almost surely, G ∈ G(m, q) satisfies the following property. If F ⊂ G is any subgraph of G with

|E(F)| ≥ (1 − \frac{1}{χ(H) − 1} + ε) q\binom{m}{2},

then F contains a copy of H.

For discussions on Turán type extremal problems for subgraphs of random graphs, see [11, Chapter 8], [12], [13, Section 1.4.2], and [14].

5 Concluding remarks

The are several questions that remain unsettled. We recall a few of them.

(1 ) Although somewhat technical, the main open question is probably Conjecture 20.

(2 ) As mentioned earlier, it would be interesting to know if one can extend Proposition 6 to the existence of graphs G_{i} with |V (G_{i})| = n_{i} and p(n_{i}) = |E(G_{i})|/\binom{n_{i}}{2} ≫ n_{i}^{−1/3} such that G_{i} satisfies (i) and (ii) in Proposition 6 and G_{i} ∈ BDD(C, 2) for some constant C for all i.

(3 ) It would be interesting to extend Theorem 23 to Conjecture 24.

References

[1] N. Alon, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Combinatorica 6 (1986), no. 3, 207–219.

[2] , Explicit Ramsey graphs and orthonormal labelings, Electron. J. Combin. 1 (1994), Research Paper 12, approx. 8 pp. (electronic).

[3] N. Alon and F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics 72 (1988), no. 1-3, 15–19.

[4] N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster, The algorithmic aspects of the regularity lemma, J. Algorithms 16 (1994), no. 1, 80–109.

[5] Noga Alon and Joel H. Spencer, The probabilistic method, second ed., Wiley-Interscience [John Wiley & Sons], New York, 2000, With an appendix on the life and work of Paul Erdős.

[6] F. R. K Chung and R. L. Graham, Sparse quasi-random graphs, Combinatorica, to appear.

[7] F. R. K. Chung and R. L. Graham, Quasi-random tournaments, J. Graph Theory 15 (1991), no. 2, 173–198.

[8] F. R. K. Chung, R. L. Graham, and R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), no. 4, 345–362.

[9] Richard A. Duke, Hanno Lefmann, and Vojtěch Rödl, A fast approximation algorithm for computing the frequencies of subgraphs in a given graph, SIAM J. Comput. 24 (1995), no. 3, 598–620.

[10] P. Frankl, V. Rödl, and R. M. Wilson, The number of submatrices of a given type in a Hadamard matrix and related results, J. Combin. Theory Ser. B 44 (1988), no. 3, 317–328.

[11] Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience, New York, 2000.

[12] Y. Kohayakawa, Szemerédi’s regularity lemma for sparse graphs, Foundations of Computational Mathematics (Berlin, Heidelberg) (F. Cucker and M. Shub, eds.), Springer-Verlag, January 1997, pp. 216–230.

[13] Y. Kohayakawa and V. Rödl, Regular pairs in sparse random graphs I, submitted, 2001.

[14] Y. Kohayakawa, V. Rödl, and M. Schacht, The Turán theorem for random graphs, submitted, 2002.

[15] Y. Kohayakawa, V. Rödl, and L. Thoma, An optimal algorithm for checking regularity (extended abstract), Proceedings of the 13th Annual ACM– SIAM Symposium on Discrete Algorithms (SODA 2002), ACM/SIAM, 2002, pp. 277–286.

[16] T. Łuczak, V. Rödl, and P. Sissokho, unpublished manuscript, 2000.

[17] Vojtěch Rödl, On universality of graphs with uniformly distributed edges, Discrete Math. 59 (1986), no. 1-2, 125–134.

[18] Vojtěch Rödl and Andrzej Ruciński, Threshold functions for Ramsey properties, J. Amer. Math. Soc. 8 (1995), no. 4, 917–942.

[19] Miklós Simonovits and Vera T. Sós, Hereditarily extended properties, quasirandom graphs and not necessarily induced subgraphs, Combinatorica 17 (1997), no. 4, 577–596.

[20] Andrew G. Thomason, Pseudorandom graphs, Random graphs ’85 (Poznań, 1985), North-Holland, Amsterdam, 1987, pp. 307–331.

[21] , Random graphs, strongly regular graphs and pseudorandom graphs, Surveys in Combinatorics 1987 (C. Whitehead, ed.), London Mathematical Society Lecture Note Series, vol. 123, Cambridge University Press, Cambridge–New York, 1987, pp. 173–195.