Preprint in the style of Combinatorics, Probability and Computing \begin{matrix}c \\ ◯ \end{matrix} 20XX Cambridge University Press

Hereditary Properties of Triple Systems

YOSHIHARU KOHAYAKAWA,^{1}† BRENDAN NAGLE,^{2}‡ and VOJTĚCH RÖDL^{3}§

1 Instituto de Matemática e Estatística, Universidade de São Paulo Rua do Matão 1010, 05508–090 São Paulo, SP, Brazil

2 School of Mathematics, Georgia Institute of Technology Atlanta, GA, 30032, USA

3 Department of Mathematics and Computer Science Emory University, Atlanta, GA, 30032, USA

For an integer s ≥ 2, a property Π^{(s)} is an infinite class of s-uniform hypergraphs closed under isomorphism. We say that a property Π^{(s)} is hereditary if Π^{(s)} is closed under taking induced subhypergraphs. Thus, for some ‘forbidden class’ 𝔽 = {F_{i}^{(s)}: i ∈ I} of s-uniform hypergraphs, Π^{(s)} is the set of all s-uniform hypergraphs not containing any F_{i}^{(s)} ∈ 𝔽 as an induced subhypergraph. Let Π_{n}^{(s)} be those hypergraphs of Π^{(s)} on some fixed n-vertex set. For a set of s-uniform hypergraphs 𝔽 = {F_{i}^{(s)}: i ∈ I}, let

ex_{ind}(n, 𝔽) = max |[n]^{s} \ (M ∪ N)| ,

where the maximum is taken over all M and N ⊆ [n]^{s} with M∩N = ∅ such that, for all G ⊆ [n]^{s} \ (M ∪ N), no F_{i}^{(s)} ∈ 𝔽 appears as an induced subhypergraph of G ∪ M. We show that for s = 3 and any hereditary property Π^{(3)},

log_{2} |Π_{n}^{(3)}| = ex_{ind}(n, 𝔽) + o(n^{3})

holds, where 𝔽 is a forbidden class associated with Π^{(3)}. This result complements a collection of analogous theorems already proven for graphs (i.e., s = 2).

† Research partially supported by FAPESP (Proc. 96/04505–2), by CNPq (Proc. 910064/99–7, 468516/00–0, and 300334/93–1), and by MCT/CNPq through a PRONEX project (Proc. CNPq 664107/1997–4).

‡ Research partially supported by NSF grant INT–0072064. Current address: Department of Mathe-

matics, University of Nevada, Reno, NV, 89557, USA. § Research partially supported by NSF grants DMS–9704114, DMS–0071261, and INT–0072064.

1. Introduction

Our aim in this paper is to investigate the asymptotic rate of growth of hereditary families of hypergraphs as we let the number of vertices of the hypergraphs tend to infinity. Before we proceed, we need to introduce some notation and some definitions.

Let n and s be natural numbers. As usual, let [n]^{s} denote the set of all s-element subsets of [n] = {1, …, n}. More generally, if V is a set, we write [V]^{s} for the set of all s-element subsets of V. An s-uniform hypergraph, or an s-graph for short, is a collection of s-element subsets, called hyperedges or simply edges, of a given vertex set. We often identify our hypergraphs with their edge sets. In particular, we often write |F| for the number of edges in a hypergraph F. Our terminology concerning hypergraphs is standard; see, e.g., Bollobás [2].

For an integer s ≥ 2, a property Π^{(s)} is an infinite class of s-uniform hypergraphs closed under isomorphism. We say that a property is hereditary provided it is closed under taking induced subhypergraphs, and we say that a property is monotone if it is closed under taking arbitrary subhypergraphs. Clearly, every monotone property is also hereditary.

Observe that, for every hereditary property Π^{(s)}, there exists a unique minimal family 𝔽 = {F_{i}^{(s)}: i ∈ I} of pairwise non-isomorphic s-uniform hypergraphs so that Π^{(s)} is the set of all s-uniform hypergraphs not containing any F_{i}^{(s)} ∈ 𝔽 as an induced subhypergraph. We refer to this set of hypergraphs 𝔽 for Π^{(s)} as the forbidden class for Π^{(s)}. Similarly, every monotone property Π^{(s)} admits a unique minimal forbidden class ℍ = {H_{i}^{(s)}: i ∈ I} of pairwise non-isomorphic hypergraphs so that Π^{(s)} is the set of all s-uniform hypergraphs not containing any H^{(s)} ∈ ℍ as a subhypergraph.

Using forbidden classes, we may develop notation to describe hereditary properties Π^{(s)} in an alternative manner. For a class of hypergraphs 𝔽 = {F_{i}^{(s)}: i ∈ I}, denote by Forb_{ind}(𝔽) the class of all s-uniform hypergraphs containing no copy F_{i}^{(s)} ∈ 𝔽 as an induced subhypergraph. Then a hereditary property Π^{(s)} may be equivalently written as Forb_{ind}(𝔽), where 𝔽 is the forbidden class for Π^{(s)}. Similarly, denote by Forb(ℍ) the class of all suniform hypergraphs containing no H^{(s)} ∈ ℍ as a subhypergraph. We may then write a monotone property Π^{(s)} as Forb(ℍ), where ℍ is the forbidden class for Π^{(s)}.

For a hereditary property Π^{(s)}, we denote those hypergraphs of Π^{(s)} on some fixed nelement vertex set by Π_{n}^{(s)}. Using the alternative notation for a hereditary property Π^{(s)}, we may denote those hypergraphs of Forb_{ind}(𝔽) on some fixed n-element vertex set by Forb_{ind}(n, 𝔽). Similarly, we denote those hypergraphs of Forb(ℍ) on some fixed n-element vertex set by Forb(n, ℍ). In what follows, we are interested in the rate of growth of |Π_{n}^{(s)}| for hereditary properties Π^{(s)} as n → ∞.

We now review some of the first results in this area, obtained for the case in which s = 2 and Π^{(s)} is monotone.

Monotone properties of graphs. For a positive integer r, consider the monotone property Π^{(2)} = Forb(K_{r+1}). Erdős, Kleitman, and Rothschild [8] showed that

log_{2} |Forb(n, K_{r+1})| = (1 − \frac{1}{r} + o(1)) \binom{n}{2}.

This result of [8] was later extended by Erdős, Frankl, and Rödl [7] to say that if H is any graph with chromatic number χ(H) = r + 1, then

log_{2} |Forb(n, H)| = (1 − \frac{1}{r} + o(1)) \binom{n}{2}.  (1)

For a property Π^{(s)}, put c_{n}(Π^{(s)}) = \binom{n}{s}^{−1} log_{2} |Π_{n}^{(s)}|, and set c(Π^{(s)}) = lim_{n→∞} c_{n}(Π^{(s)}), when the limit exists. Note that we may express (1) by saying that

c(Forb(H)) = 1 − \frac{1}{χ(H) − 1}.

It turns out that using the same proof from [7] for (1), one may easily determine c(Π^{(2)}) for any monotone property Π^{(2)}. Specifically, for a monotone property Π^{(2)}, let Π^{(2)} = Forb(𝔽), where 𝔽 is the forbidden class for Π^{(2)}. Set r_{0} = min{χ(F): F ∈ 𝔽}. Then along the same lines as [7], one may show that

c(Π^{(2)}) = c(Forb(𝔽)) = 1 − \frac{1}{r_{0} − 1}.

Let us now turn to hereditary properties Π^{(2)} of graphs.

Hereditary properties of graphs. Studying c(Π^{(2)}) in the case in which Π^{(2)} is a hereditary property is more difficult than in the case in which Π^{(2)} is monotone. Prömel and Steger [17, 18, 19, 20] were the first to work on this problem, and studied, for an arbitrary graph H, the hereditary property Forb_{ind}(H). They defined an integer-valued parameter r(H) similar to but more sophisticated than the chromatic number χ(H), and proved that c(Forb_{ind}(H)) = 1 − 1/(r(H) − 1).

Scheinermann and Zito [22] asked the more general question of whether c(Π^{(2)}) always exists for a hereditary property, and if so, what its possible values are. Alekseev [1] and Bollobás and Thomason [4] established the existence of c(Π^{(2)}) and determined its evaluation for every hereditary property Π^{(2)}. They defined an integer-valued parameter r(Π^{(2)}) by extending the definition for r(H) given in [19], and proved that for any hereditary property Π^{(2)}, we have c(Π^{(2)}) = 1 − 1/(r(Π^{(2)}) − 1).

In a very recent paper, Bollobás and Thomason [5] investigate the structure of hereditary properties in the space of random graphs G(n, p); their results substantially extend the ones in [1] and [4], which may be viewed as the p = 1/2 case of the more general results in [5].

We now turn to hypergraphs.

Monotone properties of hypergraphs. Recent work in [15] studied c(Π^{(3)}) for monotone properties Π^{(3)} of triple systems. We recall the following well-known definition. For a set of 3-uniform hypergraphs ℍ = {H_{i}^{(3)}: i ∈ I} and an integer n, define the Turán number ex(n, ℍ) as

ex(n, ℍ) = max{|G|: G ∈ Forb(n, ℍ)}.  (2)

A well-known averaging argument of Katona, Nemetz, and Simonovits [12] shows that, for every family of 3-uniform hypergraphs ℍ, the limiting Turán ratio

ex(ℍ) = lim_{n→∞} \binom{n}{3}^{−1}ex(n, ℍ)  (3)

exists. However, determining this limit, even in the case that ℍ consists of a single hypergraph (say, ℍ = {K_{4}^{(3)}}, where K_{4}^{(3)} is the complete triple system on 4 vertices), is a notoriously hard problem, central to extremal combinatorics. In fact, very few such numbers are known.

The work of [15] connected the problem of determining c(Π^{(3)}) for monotone properties Π^{(3)} to determining Turán numbers for families of triple systems. For a monotone property Π^{(3)}, write Π^{(3)} = Forb(ℍ) where ℍ is the forbidden class for Π^{(3)}. In [15], it was shown that

c(Π^{(3)}) = c(Forb(ℍ)) = ex(ℍ).  (4)

The equality in (4) may be viewed as an extension of (1). Indeed, for a family of graphs ℍ, let ex(n, ℍ) be defined analogously to (2) and set ex(ℍ) = lim_{n→∞} \binom{n}{2}^{−1}ex(n, ℍ). The well-known Erdős–Stone theorem [9] states that ex(ℍ) = 1 − 1/(r_{0} − 1), where r_{0} = min{χ(H): H ∈ ℍ}. Note that (4) does not give an explicit numerical evaluation of c(Π^{(3)}) for most monotone properties Π^{(3)}, as the corresponding task of determining ex(ℍ) is very difficult for most families ℍ.

We now discuss hereditary properties of hypergraphs, and present the main result of this paper.

Hereditary properties of hypergraphs. Returning to the original question of Scheinermann and Zito, one may ask whether c(Π^{(s)}) exists for all hereditary properties Π^{(s)} for arbitrary s ≥ 3. Bollobás and Thomason [3] proved that this is indeed is the case. Their proof, which is based on a beautiful volume inequality extending the Loomis–Whitney inequality [14], gives, however, no indication as to the possible values of c(Π^{(s)}).

In this paper, we study c(Π^{(3)}) for hereditary properties Π^{(3)} of 3-uniform hypergraphs, and prove an identity similar to (4) above. To that end, we consider the following definition extended from [19]. Let 𝔽 = {F_{i}^{(3)}: i ∈ I} be a fixed class of 3-uniform hypergraphs. For an integer n, consider sets M and N ⊆ [n]^{3} with the following two properties:

(i) M ∩ N = ∅. (ii) For all G ⊆ [n]^{3} \ (M ∪ N), we have G ∪ M ∈ Forb_{ind}(n, 𝔽). Let

ex_{ind}(n, 𝔽) = max |[n]^{3} \ (M ∪ N)|,

where the maximum is taken over all M and N that have properties (i) and (ii) above. It is not difficult to show, again by averaging, that for all families of 3-uniform hypergraphs 𝔽, the sequence \binom{n}{3}^{−1}ex_{ind}(n, 𝔽) (n ≥ 3) is non-increasing, and hence

ex_{ind}(𝔽) = lim_{n→∞} \binom{n}{3}^{−1}ex_{ind}(n, 𝔽)  (5)

exists. Our result is then as follows.

Theorem 1. For any hereditary property Π^{(3)} of triple systems,

log_{2} |Π_{n}^{(3)}| = ex_{ind}(n, 𝔽) + o(n^{3}),

where 𝔽 is the forbidden class of triple systems for Π^{(3)}. In particular,

c(Π^{(3)}) = ex_{ind}(𝔽).

As mentioned with (4), determining extremal limits for families of hypergraphs is very difficult. We expect determining ex_{ind}(𝔽) to be at least as difficult. In fact, we show in the next section that there are some hypergraphs F^{(3)} for which determining ex_{ind}(n, F^{(3)}) is equivalent to determining ex(n, F^{(3)}).

The rest of this paper is organized as follows. In the next section, we give some background facts concerning the parameter ex_{ind}(n, F^{(s)}) for single hypergraphs F^{(s)}. In Section 3, we present the main tools of our proof for Theorem 1, the Regularity Lemma for triple systems of [11] and the Counting Lemma of [16]. In Section 4, we give the proof of Theorem 1.

2. The parameter ex_{ind}(n, F^{(s)}) for single s-uniform hypergraphs F^{(s)}

We begin this section with the following definitions. Let n be an integer and let F^{(s)} be an s-uniform hypergraph. Let M, N ⊆ [n]^{s} have the following two properties:

(i) M ∩ N = ∅. (ii) For all G′ ⊆ G = [n]^{s} \ (M ∪ N), we have G′ ∪ M ∈ Forb_{ind}(n, F^{(s)}), that is, the

hypergraph F^{(s)} is not an induced subhypergraph of G′ ∪ M. It may be worth noting that, in (ii) above, [n]^{s} = G ∪M∪N is a partition of [n]^{s}. Define

ex_{ind}(n, F^{(s)}) = max |G| = max |[n]^{s} \ (M ∪ N)|,

where the maximum is taken over all M and N that have properties (i) and (ii) above. Note that ex_{ind}(n, F^{(s)}) is the special case of ex_{ind}(n, 𝔽), defined in the abstract, when the family 𝔽 consists of the single hypergraph F^{(s)}. Analogously to (5), it is routine to show that, for all hypergraphs F^{(s)}, the limit

ex_{ind}(F^{(s)}) = lim_{n→∞} \binom{n}{s}^{−1}ex_{ind}(n, F^{(s)})

exists.

For an integer n and an s-uniform hypergraph F^{(s)}, let

ex(n, F^{(s)}) = max{|G|: G ∈ Forb(n, F^{(s)})}.

Analogously to (3), it is not hard to show that, for all hypergraphs F^{(s)}, the limit

ex(F^{(s)}) = lim_{n→∞} \binom{n}{s}^{−1}ex(n, F^{(s)})

exists.

In this section, we present some properties of the function ex_{ind}(n, F^{(s)}) for s-uniform hypergraphs F^{(s)}. All of the following facts are quite straightforward to prove, and therefore we only sketch the proofs of a few. In all that follows, F^{(s)} denotes an arbitrary suniform hypergraph. We begin with the following first fact.

Fact 2. ex_{ind}(n, F^{(s)}) ≥ ex(n, F^{(s)})

Indeed, let H^{(s)} be an F^{(s)}-free s-uniform hypergraph on n vertices and ex(n, F^{(s)}) edges. In the definition of ex_{ind}(n, F^{(s)}), set G = H^{(s)}, M = ∅, and N = [n]^{s} \ G. Note that, as defined, G, M, and N satisfy properties (i) and (ii) from the definition of ex_{ind}(n, F^{(s)}). By definition, ex_{ind}(n, F^{(s)}) ≥ |G| = ex(n, F^{(s)}), and so the proof is complete.

In what follows, we denote the complete s-uniform hypergraph on k vertices by K_{k}^{(s)}. The next fact follows immediately from the definition of ex_{ind}(n, F^{(s)}).

Fact 3. ex_{ind}(n, K_{k}^{(s)}) = ex(n, K_{k}^{(s)})

Denote by K_{k}^{(s)} − e the s-uniform hypergraph of \binom{k}{s} − 1 edges on k points. The following fact, independently observed by D. Mubayi, complements Fact 3.

Fact 4. ex_{ind}(n, K_{k}^{(s)} − e) = ex(n, K_{k}^{(s)} − e)

The proof of Fact 4 follows along the lines of the proof of upcoming Fact 7, so we omit the details here.

In what follows, we denote the complement [V (F^{(s)})]^{s} \ F^{(s)} of an s-uniform hypergraph F^{(s)} by \overline{F^{(s)}}.

Fact 5. ex_{ind}(n, F^{(s)}) = ex_{ind}(n, \overline{F^{(s)}})

Indeed, if the partition [n]^{s} = G ∪ M ∪ N of [n]^{s} establishes the value of ex_{ind}(n, F^{(s)}), then the partition [n]^{s} = G ∪ M′ ∪ N′, where M′ = N and N′ = M, establishes a lower bound for ex_{ind}(n, \overline{F^{(s)}}), and vice-versa.

Facts 2 and 5 immediately imply the following.

Fact 6. ex_{ind}(n, F^{(s)}) ≥ max\{ex(n, F^{(s)}), ex(n, \overline{F^{(s)}})\}

We continue with the following fact.

Fact 7. Let F_{s+1}^{(s)} be an s-uniform hypergraph with s + 1 vertices and at least (s + 1)/2 edges. Then ex_{ind}(n, F_{s+1}^{(s)}) = ex(n, F_{s+1}^{(s)}).

Indeed, let F_{s+1}^{(s)} have f edges, where (s + 1)/2 ≤ f ≤ s + 1. We mention in advance that the key observation in our proof of Fact 7 is that all s-uniform hypergraphs consisting of f edges on s + 1 points are isomorphic.

Suppose, on the contrary, that ex_{ind}(n, F_{s+1}^{(s)}) > ex(n, F_{s+1}^{(s)}). Let the partition [n]^{s} = G ∪ M ∪ N of [n]^{s} establish the value ex_{ind}(n, F_{s+1}^{(s)}). As |G| > ex(n, F_{s+1}^{(s)}), the hypergraph G must contain a copy of F_{s+1}^{(s)}. Let X_{0} denote the vertex set of a copy of F_{s+1}^{(s)} in G. Let

g_{0} = |[X_{0}]^{s} ∩ G|, m_{0} = |[X_{0}]^{s} ∩ M|, and n_{0} = |[X_{0}]^{s} ∩ N |.

Note that

g_{0} + m_{0} + n_{0} = s + 1,

and thus

g_{0} + m_{0} ≤ s + 1.

As [X_{0}]^{s} ∩ G contains a copy of F_{s+1}^{(s)}, we have

g_{0} ≥ f.

Consequently,

f + m_{0} ≤ g_{0} + m_{0} ≤ s + 1,

and with f ≥ (s + 1)/2, we see that

m_{0} ≤ \frac{s + 1}{2} ≤ f ≤ g.

Let G′ ⊆ G be obtained by deleting any m_{0} edges from [X_{0}]^{s} ∩ G. As all s-uniform hypergraphs of f edges on s+1 points are isomorphic, it is easy to see that G′∪M contains an induced copy of F_{s+1}^{(s)}. This, however, contradicts that the partition [n]^{s} = G ∪ M ∪ N of [n]^{s} establishes the value ex_{ind}(n, F_{s+1}^{(s)}).

Fact 8. Let F_{s+1}^{(s)} be an s-uniform hypergraph with s + 1 vertices and at most (s + 1)/2

edges. Then ex_{ind}(n, F_{s+1}^{(s)}) = ex(n, \overline{F_{s+1}^{(s)}}).

Indeed, by Facts 5 and 7, we have ex_{ind}(n, F_{s+1}^{(s)}) = ex_{ind}(n, \overline{F_{s+1}^{(s)}}) = ex(n, \overline{F_{s+1}^{(s)}}).

For our next fact, we need the following notions. An s-uniform hypergraph H^{(s)} is called t-partite if there exists a partition V (H^{(s)}) = V_{1} ∪ … ∪ V_{t} so that every s-tuple of H^{(s)} meets each V_{i} (1 ≤ i ≤ t) at most once. Denote by K_{s+1}^{(s)} − 2e the s-uniform hypergraph consisting of s−1 edges on s+1 vertices. Observe that K_{4}^{(3)} −2e is 3-partite, but K_{s+1}^{(s)} − 2e is not s-partite for any s ≥ 4. More generally, a hypergraph F_{s+1}^{(s)}(m) with m ≥ 3 hyperedges is not s-partite for any s ≥ 2. Consequently, for any s ≥ 3, an suniform hypergraph H^{(s)} is such that both H^{(s)} and \overline{H^{(s)}} are s-partite if and only if H^{(s)} has at most s points, or else, s = 3 and H^{(3)} = K_{4}^{(3)} − 2e. An old theorem of P. Erdős [6] states that an s-uniform hypergraph H^{(s)} is s-partite if and only if ex(n, H^{(s)}) = o(n^{s}). This theorem, together with Facts 2 and 6, implies the following.

Fact 9. Suppose s ≥ 3 and ex_{ind}(n, F^{(s)}) = o(n^{s}). Then F^{(s)} must either have at most s vertices, or else, s = 3 and F^{(3)} = K_{4}^{(3)} − 2e.

We conclude this section with the following fact. Recall that for a fixed s-uniform hypergraph F^{(s)}, we write ex_{ind}(F^{(s)}) for the limit lim_{n→∞} \binom{n}{s}^{−1}ex_{ind}(n, F^{(s)}), which is always guaranteed to exist.

Fact 10. The set X = {ex_{ind}(F^{(s)}): F^{(s)}} is well-ordered.

Indeed, we show that, (*) for every δ > 0, the number of hypergraphs F^{(s)} with 0 ≤ ex_{ind}(F^{(s)}) < 1−δ is finite. To that end, we show that (**) there exists an integer t = t(δ) so that every F^{(s)} satisfying 0 ≤ ex_{ind}(F^{(s)}) < 1−δ also satisfies that both F^{(s)} and \overline{F^{(s)}} are t-partite. As there are only finitely many s-uniform hypergraphs F^{(s)} satisfying that both F^{(s)} and \overline{F^{(s)}} are t-partite (say, by Ramsey’s theorem), assertion (*) follows and Fact 10 is proved.

We now prove assertion (**). Suppose to the contrary that there is δ > 0 such that, for every integer t, there is a hypergraph F^{(s)} for which ex_{ind}(F^{(s)}) < 1 − δ but not both of F^{(s)} and \overline{F^{(s)}} are t-partite. Using Fact 5, we may assume, without loss of generality, that F^{(s)} is not t-partite. Moreover, we may suppose t to be sufficiently large for our inequalities to hold. For n ≥ n_{0}(t), let m = n/t, and consider the complete t-partite s-uniform hypergraph K_{t}^{(s)}(m) on n vertices. As F^{(s)} is not t-partite, F^{(s)} ⊈ K_{t}^{(s)}(m); thus ex(n, F^{(s)}) > \binom{t}{s}m^{s} > (1 − δ^{2})\binom{n}{s}. On the other hand, by Fact 2, ex_{ind}(n, F^{(s)}) ≥ ex(n, F^{(s)}) > (1 − δ^{2})\binom{n}{s}, and, with n sufficiently large, \binom{n}{s}^{−1}ex_{ind}(n, F^{(s)}) is less than, say, δ^{2} apart from ex_{ind}(F^{(s)}). Since ex_{ind}(F^{(s)}) < 1 − δ, we have a contradiction for any small enough δ.

We close this section mentioning that the results in Frankl and Rödl [10] imply that the set

L_{<∞} = {ex(𝔽): 𝔽 is a finite family of s-uniform hypergraphs}

is not well-ordered for any s ≥ 3. As it turns out, the set L_{<∞}^{ind}, defined in the analogous way for the parameter ex_{ind}(𝔽), is not well ordered either. This shows that the set L_{<∞}^{ind} is considerably richer than the set X defined in Fact 10.

3. The Regularity Lemma and Related Topics

In this section, we present the Regularity Lemma for triple systems of [11] and the Counting Lemma of [16]. The reader who is not familiar with the regularity lemma of Szemerédi [23] is strongly encouraged to study the excellent survey of Komlós and Simonovits [13], before reading this section.

We mention now that the remainder of this paper is concerned only with triple systems and graphs. As the distinction between graphs and triple systems will be clear in context, we suppress the superscript “(s)” in all that follows.

3.1. Graphs and Cylinders In this subsection, we provide background definitions and notation used in [16].

Definition 11 (Partite cylinders, triads). We refer to a k-partite graph P with a fixed k-partition (V_{1}, …, V_{k}) of V = V (P) as a k-partite cylinder, and write P = ⋃_{1≤i<j≤k} P^{ij}, where P^{ij} = P [V_{i}, V_{j}] = {{v_{i}, v_{j}} ∈ P: v_{i} ∈ V_{i}, v_{j} ∈ V_{j}}. If B ∈ [k]^{3}, then the 3-partite cylinder P (B) = ⋃_{{i,j}∈[B]^{2}} P^{ij} is referred to as a triad.

Definition 12 (Density d_{P} (X, Y)). Suppose P ⊆ [V]^{2} is a graph with vertex set V = V (P), and let X, Y ⊆ V be two nonempty disjoint subsets of V. We define the density d_{P} (X, Y) of the pair (X, Y) with respect to P as

d_{P} (X, Y) = \frac{|\{x, y\} ∈ P: x ∈ X, y ∈ Y \}|}{|X||Y |}.

Definition 13 ((l, ε, k)-cylinder). Suppose P = ⋃_{1≤i<j≤k} P^{ij} is a k-partite cylinder with k-partition (V_{1}, …, V_{k}), and let a positive integer l and a real number ε > 0 be given. We call P an (l, ε, k)-cylinder provided all pairs (V_{i}, V_{j}), 1 ≤ i < j ≤ k, induce P^{ij} satisfying that, whenever V′_{i} ⊆ V_{i} and V′_{j} ⊆ V_{j} are such that |V′_{i}| > ε|V_{i}| and |V′_{j}| > ε|V_{j}|, we have

\frac{1}{l}(1 − ε) < d_{P^{ij}}(V′_{i}, V′_{j}) < \frac{1}{l}(1 + ε).

The artificial condition in Definition 13 that l should be an integer will become natural later, when we discuss the regularity lemma for hypergraphs in Section 3.3.

We now define an auxiliary set system pertaining to a k-partite cylinder P.

Definition 14 (K_{j}(P)). For a k-partite cylinder P, we denote by K_{j}(P) (1 ≤ j ≤ k) the j-uniform hypergraph whose edges are precisely those j-element subsets of V (P) that span cliques of order j in P.

Note that the quantity |K_{j}(P)| is the total number of cliques in P of order j, that is, |K_{j}(P)| = |{X ⊆ V (P): |X| = j, [X]^{2} ⊆ P }|. As it turns out, for an (l, ε, k)-cylinder P, the quantity |K_{j}(P)| is easy to estimate.

Fact 15. For any positive integers k and l and a positive real θ, there exists ε > 0 such that, whenever P is an (l, ε, k)-cylinder with k-partition (V_{1}, …, V_{k}), where |V_{1}| = … = |V_{k}| = m, we have

(1 − θ)m^{k}l^{−\binom{k}{2}} < |K_{k}(P)| < (1 + θ)m^{k}l^{−\binom{k}{2}}.  (6)

Fact 15 is by now standard; the reader may for instance consult [13, Theorem 2.1].

3.2. 3-Uniform Hypergraphs and 3-Cylinders In this subsection, we give definitions pertaining to 3-uniform hypergraphs. Recall that by a 3-uniform hypergraph H on vertex set V, we mean H ⊆ [V]^{3}. As mentioned before, when there is no confusion in doing so, we identify the hypergraph H with its set of triples.

By a k-partite 3-uniform hypergraph H with a k-partition (V_{1}, …, V_{k}), we understand a hypergraph H with its vertex set V = V (H) partitioned into k classes V = V_{1} ∪…∪V_{k}, where each triple e ∈ H satisfies that for each i ∈ [k], we have |e ∩ V_{i}| ≤ 1.

Definition 16 (k-partite 3-cylinder; H(B)). We refer to any k-partite, 3-uniform hypergraph H with a fixed k-partition (V_{1}, …, V_{k}) as a k-partite 3-cylinder. For B ∈ [k]^{3}, we define H(B) as that 3-partite 3-cylinder induced by H on ⋃_{i∈B} V_{i}.

Definition 17 (P underlies H). Suppose P is a k-partite cylinder with k-partition (V_{1}, …, V_{k}), and H is a k-partite 3-cylinder with k-partition (V_{1}, …, V_{k}). We say that P underlies the 3-cylinder H if H ⊆ K_{3}(P).

As in Definition 14, we define an auxiliary set system pertaining to the 3-cylinder H.

Definition 18 (K_{j}(H)). For a k-partite 3-cylinder H, denote by K_{j}(H) (1 ≤ j ≤ k), that j-uniform hypergraph whose edges are precisely those j-element subsets of V (H) that span a clique of order j in H.

Clearly, the quantity |K_{j}(H)| defined above is the total number of cliques of order j in H, that is, |K_{j}(H)| = |{X ⊆ V (H): |X| = j, [X]^{3} ⊆ H}|. We now define a notion of density for hypergraphs.

Definition 19 (Density d_{H}(P)). Let H be a 3-partite 3-cylinder and suppose P = P^{12} ∪ P^{23} ∪ P^{13} is a 3-partite cylinder that underlies H. We define the density d_{H}(P) of H with respect to P as

d_{H}(P) = \{ \begin{matrix}|H|/|K_{3}(P)| & if |K_{3}(P)| > 0, \\ 0 & otherwise. \end{matrix}

Note that we may think of the notion of density introduced above as a measure of the proportion of triangles of P that are also triples of H. More generally, we shall have to measure the density of our system H against ‘thinner’ triads. Suppose Q ⊆ P, where Q = ⋃_{{i,j}∈[3]^{2}} Q^{ij} and Q^{ij} ⊆ P^{ij} (1 ≤ i < j ≤ 3). One can define the density d_{H}(Q) of H with respect to Q as

d_{H}(Q) = \{ \begin{matrix}|H ∩ K_{3}(Q)|/|K_{3}(Q)| & if |K_{3}(Q)| > 0, \\ 0 & otherwise. \end{matrix}  (7)

We shall need an extension of the definition in (7) above: we shall consider a ‘simultaneous density’ of H with respect to a fixed r-tuple of triads (Q(1), …, Q(r)).

Definition 20 (Density d_{H}(Q⃗)). Let H be a 3-partite 3-cylinder with an underlying 3-partite cylinder P = P^{12} ∪ P^{23} ∪ P^{13}. Let Q⃗ = (Q(1), …, Q(r)) be an r-tuple of triads Q(s) = ⋃_{{i,j}∈[3]^{2}} Q^{ij}(s) satisfying that, for every s ∈ [r] and every {i, j} ∈ [3]^{2}, we have Q^{ij}(s) ⊆ P^{ij}. We define the density d_{H}(Q⃗) of H with respect to Q⃗ as

d_{H}(Q⃗) = \{ \begin{matrix}|H ∩ ⋃_{s=1}^{r} K_{3}(Q(s))| /| ⋃_{s=1}^{r} K_{3}(Q(s))| & if | ⋃_{s=1}^{r} K_{3}(Q(s))| > 0, \\ 0 & otherwise. \end{matrix}

We now give a definition that provides a notion of regularity for 3-cylinders.

Definition 21 ((δ, r)- and (α, δ, r)-regularity). Let H be a 3-partite 3-cylinder with an underlying 3-partite cylinder P = P^{12} ∪ P^{23} ∪ P^{13}. Let r be a given positive integer and let δ > 0 be given. We say that H is (δ, r)-regular with respect to P if condition (*) below is satisfied. (*) Let Q⃗ = (Q(1), …, Q(r)) be an arbitrary r-tuple of triads Q(s) = ⋃_{{i,j}∈[3]^{2}} Q^{ij}(s),

where Q^{ij}(s) ⊆ P^{ij} for all s ∈ [r] and {i, j} ∈ [3]^{2}. Then if

| ⋃_{s=1}^{r} K_{3}(Q(s))| > δ|K_{3}(P)|,

we have

|d_{H}(Q⃗) − d_{H}(P)| < δ.  (8)

If, moreover, it is specified that H is (δ, r)-regular with respect to P with density d_{H}(P) = α for some α, then we say that H is (α, δ, r)-regular with respect to P. If H is not (δ, r)- regular with respect to P, then we say that H is (δ, r)-irregular with respect to P.

3.3. The Regularity Lemma In this section, we state a regularity lemma for 3-uniform hypergraphs established in [11]. First we state a number of supporting definitions.

Definition 22 (Equitable partition; m = |V_{i}|). Let t be an integer and let V be an n-element set. We define an equitable partition of V as a partition V = V_{0} ∪ V_{1} ∪ … ∪ V_{t} of V, where

(i) |V_{1}| = … = |V_{t}| = ⌊n/t⌋ = m, (ii) |V_{0}| < t.

Definition 23 ((l, t, γ, ε)-partition). Let V be a set, γ and ε be given positive constants, and l and t be given positive integers. An (l, t, γ, ε)-partition P of [V]^{2} is an (auxiliary) partition V = V_{0} ∪ … ∪ V_{t} of V, together with a system of edge-disjoint bipartite graphs P_{α}^{ij} (1 ≤ i < j ≤ t, α = 0, 1, …, l_{ij} ≤ l) such that

(i) V = V_{0} ∪ … ∪ V_{t} is an equitable partition of V, (ii) ⋃_{α=0}^{l_{ij}} P_{α}^{ij} = K(V_{i}, V_{j}) for all 1 ≤ i < j ≤ t; in other words, the bipartite graphs P_{α}^{ij}

(0 ≤ α ≤ l_{ij}) form a decomposition of the complete bipartite graph K(V_{i}, V_{j}) with vertex sets V_{i} and V_{j},

(iii) all but ≤ γ\binom{t}{2}m^{2} pairs \{v_{i}, v_{j}\} with v_{i} ∈ V_{i} and v_{j} ∈ V_{j}, where 1 ≤ i < j ≤ t, are

edges of ε/2l-regular bipartite graphs P_{α}^{ij}, and (iv) for all but ≤ γ\binom{t}{2} pairs (i, j), where 1 ≤ i < j ≤ t, we have |P_{0}^{ij}| ≤ γm^{2} and

\frac{1}{l} (1 − \frac{ε}{2}) ≤ d_{P_{α}^{ij}}(V_{i}, V_{j}) ≤ \frac{1}{l} (1 + \frac{ε}{2})

for all α = 1, …, l_{ij}.

Note that by (iii) and (iv) above, we are ensured that nearly all P_{α}^{ij} are (l, ε, 2)- cylinders (see Fact 26 below).

Definition 24 ((δ, r)-regular partition P). Suppose we have a 3-uniform hypergraph H ⊆ [n]^{3} and P, an (l, t, γ, ε)-partition of [n]^{2}; recall we write m = |V_{1}| = … = |V_{t}|. Let P be a triad of P, and let further

μ_{P} = \frac{|K_{3}(P)|}{m^{3}}.  (9)

We say that the (l, t, γ, ε)-partition P is (δ, r)-regular if

∑ \{μ_{P}: P is a (δ, r)-irregular triad of P\} < δ (\frac{n}{m})^{3} .  (10)

For future reference, we make the following remark.

Remark 25. Using the definition of μ_{P} in (9), the inequality in (10) is easily rewritten as

∑ {|K_{3}(P)|: P is a (δ, r)-irregular triad of P} < δn^{3}.

We infer from the inequality above that

|{h ∈ H: h ∈ K_{3}(P) for some (δ, r)-irregular triad P of P}| < δn^{3}.  (11)

The following fact appears as Proposition 4.6 in [21] (with a slight but inessential difference in wording) and asserts that in a (δ, r)-regular (l, t, γ, ε)-partition there are not too many bipartite graphs P_{α}^{ij} that fail to be (l, ε, 2)-cylinders, nor are there many triads P = P_{α}^{ij} ∪ P_{β}^{jk} ∪ P_{γ}^{ik} that fail to be (δ, r)-regular.

Fact 26. Let positive constants γ and δ and integers l > 1/γ and r be given. There exists ε = ε(l) > 0 so that, for all integers t, the following holds: whenever P = {P_{α}^{ij}: 0 ≤ α ≤ l_{ij} ≤ l, 1 ≤ i < j ≤ t} is an (l, t, γ, ε)-partition that is (δ, r)-regular with respect to a hypergraph H, we have (i)

∑_{1≤i<j≤t} |\{α ≥ 1: P_{α}^{ij} is not an (l, ε, 2)-cylinder\}| < 3γ\binom{t}{2}l,

(ii) if I_{1} is the set of all triads P of P that are (δ, r)-irregular with respect to H, then |I_{1}| < (2δ + γ)t^{3}l^{3}.

We update Fact 26 by giving the following easy variation of statement (i). (i′) Denote by I_{2} the set of triads P of P that contain as a member a bipartite graph P_{α}^{ij}

(0 ≤ α ≤ l_{ij}, 1 ≤ i < j ≤ t) satisfying that either α = 0 or P_{α}^{ij} is not an (l, ε, 2)- cylinder. Then if l > 1/γ and ε = ε(l) is sufficiently small, we have |I_{2}| < 2γt^{3}l^{3}.

Adapting Fact 26 with statement (i′) yields the following fact.

Fact 27. Let P = {P_{α}^{ij}: 0 ≤ α ≤ l_{ij} ≤ l, 1 ≤ i < j ≤ t} be an (l, t, γ, ε)-partition that is (δ, r)-regular with respect to a hypergraph H. Let I = I_{1} ∪ I_{2}, that is, I is the set of all triads P of P that are either (δ, r)-irregular with respect to H or else are such that contain as a member a bipartite graph P_{α}^{ij} (0 ≤ α ≤ l_{ij}, 1 ≤ i < j ≤ t) satisfying that either α = 0 or P_{α}^{ij} is not an (l, ε, 2)-cylinder. If l > 1/γ and ε = ε(l) is sufficiently small, then |I| < (3γ + 2δ)t^{3}l^{3}.

We now state the Regularity Lemma of [11].

Theorem 28. For every δ and γ with 0 < γ ≤ 2δ^{4}, for all integers t_{0} and l_{0} and for all integer-valued functions r = r(t, l) and all functions ε(l), there exist T_{0}, L_{0}, and N_{0} such that any 3-uniform hypergraph H ⊆ [n]^{3}, where n ≥ N_{0}, admits a (δ, r(t, l))-regular, (l, t, γ, ε(l))-partition for some t and l satisfying t_{0} ≤ t < T_{0} and l_{0} ≤ l < L_{0}.

For future reference, we state the following two definitions concerning (l, t, γ, ε)-regular partitions P for a triple system H.

Definition 29 (Ξ = Ξ(P) = {ξ = {i, j, k}_{αβγ}}). Let P = {P_{α}^{ij}: 0 ≤ α ≤ l_{ij} ≤ l, 0 ≤ i < j ≤ t} be an (l, t, γ, ε)-partition of a vertex set V. We write Ξ = Ξ(P) for the set of 6-tuples ξ = (i, j, k, α, β, γ) with 0 ≤ α ≤ l_{ij} ≤ l, 0 ≤ β ≤ l_{jk} ≤ l, and 0 ≤ γ ≤ l_{ik} ≤ l, for all 0 ≤ i < j < k ≤ t. Furthermore, we shall write {i, j, k}_{αβγ} for such 6-tuples ξ ∈ Ξ.

Clearly, given an (l, t, γ, ε)-partition P as in Definition 29, we may think of each ξ ∈ Ξ = Ξ(P) as specifying the triad

P_{ξ} = P_{α}^{ij} ∪ P_{β}^{jk} ∪ P_{γ}^{ik},

where ξ = {i, j, k}_{αβγ}. Therefore, Ξ may be identified with the family of triads of P.

Definition 30 (Density vector s⃗). Let H be a triple system admitting a (δ, r)-regular (l, t, γ, ε)-partition P. Let s⃗ = (s_{ξ}) be the vector of integers indexed by the ξ ∈ Ξ = Ξ(P), where s_{ξ} = ⌊δ^{−1}d_{H}(P_{ξ})⌋ for all ξ ∈ Ξ. We say that s⃗ is the density vector of H over P.

Let s⃗ = (s_{ξ}) be a density vector as above. Then, clearly, if ξ = {i, j, k}_{αβγ} ∈ Ξ, then

s_{ξ}δ ≤ d_{H}(P_{ξ}) = d_{H}(P_{α}^{ij} ∪ P_{β}^{jk} ∪ P_{γ}^{ik}) < (s_{ξ} + 1)δ.

3.4. The Counting Lemma We begin our discussion of the Counting Lemma of [16] by describing the general ‘environment’ in which this lemma applies. As in [16], we call this environment the Setup.

Setup. For given constants k, δ, l, r, and ε, and a given set {α_{B}: B ∈ [k]^{3}} of positive reals, suppose

(i) H is a k-partite 3-cylinder with k-partition (V_{1}, …, V_{k}) with |V_{1}| = … = |V_{k}| = m, (ii) P = ⋃_{1≤i<j≤k} P^{ij} is an (l, ε, k)-cylinder underlying H, (iii) for all B ∈ [k]^{3}, the 3-partite 3-cylinder H(B) is (α_{B}, δ, r)-regular with respect to the

triad P (B) (see Definition 21).

The main result of [16] is the following Counting Lemma.

Lemma 31 (The Counting Lemma). Let k ≥ 4 be a fixed integer. For all constants α and β > 0, there exists δ > 0 such that, for all integers l ≥ 1/δ, there exist r and ε > 0 so that, whenever a k-partite 3-cylinder H with an underlying cylinder P satisfies the conditions of the Setup with constants k, δ, l, r, and ε, and set {α_{B}: B ∈ [k]^{3}}, where α_{B} ≥ α for all B ∈ [k]^{3}, we have

(1 − β)l^{−\binom{k}{2}}m^{k} ∏_{B∈[k]^{3}} α_{B} ≤ |K_{k}(H)| ≤ (1 + β)l^{−\binom{k}{2}}m^{k} ∏_{B∈[k]^{3}} α_{B}.  (12)

For our purposes in this paper, we are content to know that under the hypotheses of the Counting Lemma, at least one copy of K_{k}^{(3)} is ensured within H, provided m is sufficiently large.

4. Proof of Theorem 1

Recall that in Theorem 1, we promised to show that for any hereditary property Π of triple systems,

log_{2} |Π_{n}| = ex_{ind}(n, 𝔽) + o(n^{3}),  (13)

where 𝔽 is the forbidden class of triple systems associated with Π. To that end, let Π be a fixed hereditary property of triple systems, and let 𝔽 be its class of forbidden triple systems. We show the equality in (13). We begin by first showing the easy lower bound

log_{2} |Π_{n}| ≥ ex_{ind}(n, 𝔽).  (14)

Let [n]^{3} = G ∪ M ∪ N be a partition of [n]^{3} that gives the value of ex_{ind}(n, 𝔽). More explicitly, let G ⊆ [n]^{3} be of size |G| = ex_{ind}(n, 𝔽), with the property that there exist disjoint sets M and N ⊆ [n]^{3} \ G, such that M ∪ N = [n]^{3} \ G, so that, for all G′ ⊆ G, no F ∈ 𝔽 is an induced subhypergraph of M ∪ G′. Since there are 2^{|G|} = 2^{ex_{ind}(n,𝔽)} subhypergraphs G′ ⊆ G, and each such G′ is such that G′ ∪ M ∈ Π_{n}, the inequality in (14) is established. (Clearly, this simple argument holds for all s, and not simply for s = 3.)

What remains to be shown is the more difficult upper bound. We show that, for any ν > 0, the inequality

log_{2} |Π_{n}| ≤ ex_{ind}(n, 𝔽) + νn^{3}  (15)

holds for sufficiently large n.

To that end, let ν > 0 be given. To show (15), we first define some auxiliary parameters. We define positive constants σ, μ, α_{0}, θ, τ, δ, and γ, and positive integers k_{0}, l_{0}, t_{0}, as well as functions ε = ε(l) and r = r(l). The following description of these auxiliary parameters is rather technical. The reader may find it useful to have in mind that these constants obey the ‘hierarchy’ given in (16) and (17) below:

ν ≫ σ, μ ≫ \frac{1}{k_{0}} , α_{0}, τ, θ ≫ δ > γ > \frac{1}{l_{0}} ≫ \frac{1}{r} ≫ ε,  (16)

γ > \frac{1}{t_{0}} .  (17)

In what follows, we shall be considering hypergraphs with n vertices, where n is such that

ε, \frac{1}{t_{0}} ≫ \frac{1}{n}.

4.1. Definition of the Auxiliary Constants For the given constant ν > 0, define positive constants

μ = μ(ν),  (18)
σ = σ(ν),  (19)
θ_{1} = θ_{1}(ν),  (20)
τ = τ(ν),  (21)

all smaller than 1, such that

2θ_{1} + 9μ + 4σ log \frac{2e}{σ} < \frac{ν}{2} ,  (22)

and

τ ≤ μ^{3} < σ < \frac{1}{8}.  (23)

With μ, σ, θ_{1}, and τ as in (22) and (23), the following inequality holds for all sufficiently large integers n:

(ex_{ind}(n, 𝔽) + 4μn^{3} + τn^{3})(1 + θ_{1}) + n^{2} log n + 4n^{3}σ log \frac{2e}{σ}
< ex_{ind}(n, 𝔽) + νn^{3}.  (24)

For the constant τ > 0 in (21), let

k_{0} = k_{0}(τ)  (25)

be an integer satisfying that for all integers n ≥ t ≥ k_{0}, we have

|\binom{t}{3}^{−1}ex_{ind}(t, 𝔽) − \binom{n}{3}^{−1}ex_{ind}(n, 𝔽)| < τ.  (26)

Note that the existence of k_{0} follows from the fact that ex_{ind}(𝔽) = lim_{n→∞} \binom{n}{3}^{−1}ex_{ind}(n, 𝔽) exists for any fixed family of triple systems 𝔽.

For the constants μ and σ given in (18) and (19), let positive constants θ_{2}, δ_{1}, and α_{0}, and a positive integer t_{1} satisfy

\frac{2}{t_{1}} < δ_{1},  (27)
2δ_{1}^{1/2}\binom{k_{0}}{3} ≤ μ^{3},  (28)
\frac{α_{0}}{3} ≤ \frac{σ}{2}  (29)
4δ_{1} < \frac{σ}{2} ,  (30)

(31)

and

(2θ_{2} + α_{0} − θ_{2}α_{0}) log \frac{2e}{2θ_{2} + α_{0} − θ_{2}α_{0}} ≤ σ log \frac{2e}{σ},  (32)

and, finally,

100δ_{1} + \frac{100δ_{1}}{μ^{2}} < δ_{1}^{1/2}.  (33)

Set

t′_{0} = max{k_{0}, t_{1}},  (34)
θ = min{θ_{1}, θ_{2}}.  (35)

Some of the remainder of our discussion on defining the auxiliary constants will concern the Counting Lemma, Lemma 31. Recall that regarding the constants involved, Lemma 31 states

“∀k ∀α, β ∃δ: ∀l > \frac{1}{δ} ∃ r, ε so that … ”.

Set

k = k_{0}  (36)

where k_{0} is defined in (25). For an integer f_{0} ≤ k_{0}, the constant α_{0} given in (30) and (32), and β = 1/2, let

δ_{2,f_{0}} = δ_{31}(f_{0}, α_{0})

be that constant guaranteed by Lemma 31. Set

δ_{2} = min{δ_{2,f_{0}}: 4 ≤ f_{0} ≤ k_{0}}.  (37)

Set

δ = min{δ_{1}, δ_{2}},  (38)

where δ_{1} and δ_{2} were given in (27)–(33) and (37). We now let

t_{0} = max{t′_{0}, ⌈2/δ⌉}.  (39)

Set

γ = \frac{δ}{3}  (40)

and let

l_{0} > \frac{1}{γ} > \frac{1}{δ}  (41)

be any integer. We now define functions r(l) and ε(l).

For an integer 4 ≤ f_{0} ≤ k_{0} and any integer l ≥ l_{0} > 1/γ > 1/δ, Lemma 31 gives us

r_{f_{0}}(l) = r_{31}(f_{0}, α_{0}, δ, l),
ε′_{f_{0}}(l) = ε_{31}(f_{0}, α_{0}, δ, l).

For any integer l ≥ l_{0} > 1/γ > 1/δ, set

r(l) = max{r_{f_{0}}(l): 4 ≤ f_{0} ≤ k_{0}},  (42)

ε′(l) = min{ε′_{f_{0}}(l): 4 ≤ f_{0} ≤ k_{0}}.  (43)

For the definition of ε(l), recall Fact 15, which guarantees to every k, l, and θ, an ε > 0 such that, for any (l, ε, k)-cylinder P, relation (6) holds. For k = 3 and θ given in (35), let, for any integer l,

ε_{15} = ε_{15}(l)  (44)

be that function whose existence is guaranteed by Fact 15. For l > 1/γ, let

ε_{27} = ε_{27}(l)  (45)

be that function guaranteed by Fact 27. Set

ε = ε(l) = min{ε′(l), ε_{15}(l), ε_{27}(l)}.  (46)

This concludes the definitions of the constants σ, μ, k_{0}, α_{0}, θ, δ, l_{0}, γ, and t_{0}, and functions r = r(l) and ε = ε(l). We note that, with the constants described above, we may assume that the hierarchy in (16) and (17) is satisfied.

4.2. Proof of (15) We begin our proof of the upper bound

log_{2} |Π_{n}| ≤ ex_{ind}(n, 𝔽) + νn^{3}

as follows. For each H ∈ Π_{n}, we use Theorem 28 to obtain a (δ, r)-regular (l, t, γ, ε)- partition P = P_{H}. To that end, we must first disclose the input constants and functions required by Theorem 28. Recall that regarding the constants involved, Theorem 28 states that

“∀δ, γ, t_{0}, l_{0}, r(t, l), ε(l) ∃T_{0}, L_{0}, N_{0} such that … ”.

Let δ be the constant given in (38), γ be the constant given in (40), t_{0} be the integer given in (39), and l_{0} be the integer given in (41). Furthermore, let r = r(l) be the function given in (42) and ε = ε(l) be the function given in (46).

With the above disclosed input values, Theorem 28 guarantees constants T_{0}, L_{0}, and N_{0} so that any triple system H on n > N_{0} vertices admits a (δ, r)-regular, (l, t, γ, ε)- partition P, for some integers t and l satisfying t_{0} ≤ t ≤ T_{0} and l_{0} ≤ l ≤ L_{0}. We stress that what is important for us is that, provided n > N_{0}, every H ∈ Π_{n} admits a (δ, r)-regular, (l, t, γ, ε)-partition P = P(H). Whenever H ∈ Π_{n} admits many such partitions P, we arbitrarily choose one partition P = P(H) to associate with H. It will be these partitions that will allow us to estimate |Π_{n}| effectively.

Our strategy for estimating |Π_{n}| is as follows. For n > N_{0}, where N_{0} was determined by Theorem 28, and for the family Π_{n}, let P̌ = {P_{1}, …, P_{p}} be the set of all (δ, r)- regular, (l, t, γ, ε)-partitions guaranteed by Theorem 28 for the hypergraphs H ∈ Π_{n}. The crucial observation is that P̌ induces a partition of Π_{n} into equivalence classes

{C(i, s⃗): 1 ≤ i ≤ p and s⃗ a density vector for P_{i}},

defined in the following way: for each i ∈ [p] and density vector s⃗, for all H ∈ Π_{n},

H ∈ C(i, s⃗) ⟺ \{ \begin{matrix}P_{i} ∈ P̌ is the partition P(H) associated with H, \\ and H has density vector s⃗ over P_{i}. \end{matrix}

We note that here we see why it was important to choose a unique partition to associate with each H ∈ Π_{n}. For convenience, denote by S⃗ the set of all possible density vectors (i.e., all vectors of length \binom{t}{3}l^{3} whose coordinates take the integer values between 0 and ⌊1/δ⌋).

In view of the partition of Π_{n} into the equivalence classes {C(i, s⃗): 1 ≤ i ≤ p, s⃗ ∈ S⃗}, we divide the process of estimating |Π_{n}| into two tasks: we estimate the number of such equivalence classes q = |{C(i, s⃗): 1 ≤ i ≤ p, s⃗ ∈ S⃗}|, and we give a uniform upper bound for the cardinality of all these classes C(i, s⃗) (1 ≤ i ≤ p, s⃗ ∈ S⃗). For the first task, we show that

log_{2} q = O(n^{2}),  (47)

and, for the second task, we show that

log_{2} |C(i, s⃗)| = (ex_{ind}(n, 𝔽) + τn^{3} + 4μn^{3})(1 + θ) + 4n^{3}σ log \frac{2e}{σ} + O(1), (48)

for any C(i, s⃗) (1 ≤ i ≤ p, s⃗ ∈ S⃗). Therefore, as a result of (47) and (48), combined with the inequality in (24), we have

log_{2} |Π_{n}| = log_{2} ∑_{i=1}^{p} ∑_{s⃗∈S⃗} |C(i, s⃗)|,

≤ O(n^{2}) + (ex_{ind}(n, 𝔽) + τn^{3} + 4μn^{3})(1 + θ) + 4n^{3}σ log \frac{2e}{σ},
≤ (ex_{ind}(n, 𝔽) + τn^{3} + 4μn^{3})(1 + θ) + n^{2} log n + 4n^{3}σ log \frac{2e}{σ},
≤ ex_{ind}(n, 𝔽) + νn^{3}.  (49)

Thus, we are finished proving (15) once we have established (47) and (48). We do this below, and begin by estimating the value q.

4.2.1. Estimation of q. The number of partitions of the vertex set that arise from regular partitions P ∈ P̌ is at most (T_{0} + 1)^{n}. Moreover, Theorem 28 guarantees families of graphs P_{α}^{ij} (0 ≤ α ≤ l_{ij} ≤ L_{0}, 0 ≤ i < j ≤ t ≤ T_{0}) with at most \binom{T_{0}+1}{2}(L_{0} + 1) members. Since there are at most δ^{−\binom{T_{0}+1}{3}(L_{0}+1)^{3}} density vectors that could be associated to any one P ∈ {P_{1}, …, P_{p}}, the number q of classes is at most

(\frac{1}{δ})^{\binom{T_{0}+1}{3}(L_{0}+1)^{3}} (T_{0} + 1)^{n} (\binom{T_{0} + 1}{2}(L_{0} + 1))^{\binom{n}{2}} = 2^{O(n^{2})}.

Thus, the bound

log_{2} q = O(n^{2}).

is established.

4.2.2. Estimation of |C|. Our second task is to estimate |C(i, s⃗)| for all C(i, s⃗) (1 ≤ i ≤ p, s⃗ ∈ S⃗). To that effect, fix one such C(i, s⃗) and, for simplicity of notation, set C = C(i, s⃗) and P = P_{i}. Let P have equitable partition [n] = V_{0} ∪ … ∪ V_{t}, where, as usual, m = |V_{1}| = … = |V_{t}| = ⌊n/t⌋, and let the system of bipartite graphs of P be P_{α}^{ij} (1 ≤ i < j ≤ t, 0 ≤ α ≤ l_{ij} ≤ l).

We shall estimate from above the number of H ∈ Π_{n} that are members of the equivalence class C. The main tool we use to bound |C| is that the partition P is a (δ, r)-regular, (l, t, γ, ε)-partition with respect to all H ∈ C and that all H ∈ C have density vector s⃗ over P. Owing to this highly regular structure of P, we are able to give an upper bound for |C| in an effective way. We shall show that

log_{2} |C| ≤ (ex_{ind}(n, 𝔽) + τn^{3} + 4μn^{3})(1 + θ) + 4n^{3}σ log \frac{2e}{σ} + O(1).  (50)

Before we plunge into the proof of (50), we give a quick overview of our strategy. Recall we write Ξ = Ξ(P) = {ξ} for the system of ξ = {i, j, k}_{αβγ}, with each such ξ specifying a triad of P. For any fixed H ∈ C, we shall show that we may associate a partition

Ξ = Ξ(P) = I ∪ G ∪ N ∪ M  (51)

of Ξ with the properties we describe below. For simplicity, for any Ξ′ ⊂ Ξ, we write K_{3}(Ξ′) for

⋃_{ξ∈Ξ′} K_{3}(P_{ξ}),

where, we recall, P_{ξ} is the triad P_{α}^{ij} ∪ P_{β}^{jk} ∪ P_{γ}^{ik} if ξ = {i, j, k}_{αβγ}. (P_{1}) The system I = H ∩ K_{3}(I) is such that |I| ≤ 3δn^{3}. (P_{2}) The system N = H ∩ K_{3}(N) is such that |N | ≤ (α_{0}/3)n^{3}. (P_{3}) The system M = H ∩ K_{3}(M) is such that

|K_{3}(M) \ M| ≤ (2θ + α_{0} − α_{0}θ)|K_{3}(M)|.  (52)

(P_{4}) The system G = Ξ \ (I ∪ N ∪ M) is such that (59) below holds. Let G = H ∩ K_{3}(G). (P_{5}) Let

E_{0} = [n]^{3} \ (G ∪ I ∪ N ∪ M).

Then |E_{0}| ≤ δn^{3}. A little thought now shows that the existence of a partition as in (51), satisfying properties (P_{1})–(P_{5}), for every H ∈ C, may be used to bound |C| from above. Indeed, note first that we have established a partition

H = E_{0} ∪ I ∪ N ∪ M ∪ G

for any given H ∈ C. Observe also that (i) the number of partitions of Ξ into 4 parts as in (51) is at most 4^{|Ξ|} = O(1), (ii) the number of choices we have for the triples in I ∪ N ∪ M is 2^{cn^{3}}, where c = c(δ, α_{0}, θ) → 0 as δ, α_{0}, θ → 0, (iii) once G is fixed, the number of choices we have for the triples in G is

≤ 2^{|K_{3}(G)|},  (53)

which may be estimated using (59) and the fact that all ξ ∈ G are such that the associated triad P_{ξ} is an (l, ε, 3)-cylinder, and (iv) the number of choices we have for the triples in E_{0} is at most 2^{δn^{3}}. To obtain an upper bound for |C| it then suffices to put together observations (i)–(iv). We do this in detail in what follows.

Fix H ∈ C.

Definition of I. We put ξ = {i, j, k}_{αβγ} ∈ Ξ in I if any of the following conditions holds:

(i) α = 0, β = 0, or γ = 0, (ii) P_{α}^{ij}, P_{β}^{jk}, or P_{γ}^{ik} is not an (l, ε, 2)-cylinder, (iii) P_{ξ} = P_{α}^{ij} ∪ P_{β}^{jk} ∪ P_{γ}^{ik} is not a (δ, r)-regular triad with respect to H({i, j, k}). Note that it follows from Fact 27 that since l ≥ l_{0} > 1/γ (see (41)), ε ≤ ε_{27} (see (46)), and γ = δ/3 (see (40)) that

|I| < (3γ + 2δ)t^{3}l^{3} < 3δt^{3}l^{3}.

Note that, because t ≥ 5, we may further conclude that

|I| < 100δl^{3}\binom{t}{3}.  (54)

As it turns out, we shall also be interested in viewing I ⊂ Ξ as a hypergraph on [t] = {1, …, t}, where we allow multiple, or parallel, edges: for each {i, j, k} (1 ≤ i < j < k ≤ t), as many as l^{3} parallel triples

{i, j, k}_{αβγ} ∈ I

are possible.

We now put I = H ∩ K_{3}(I). It follows from statements (iii) and (iv) of Definition 23 and (11) from Remark 25 that

|I| ≤ 4γ\binom{t}{2} (\frac{n}{t})^{2} n + δn^{3} ≤ 3δn^{3}.  (55)

Definition of N. We put ξ = {i, j, k}_{αβγ} ∈ Ξ\I in N if P_{ξ} is a ‘thin’ regular triad, that is, a regular triad that captures few triples of H. More precisely, we put ξ = {i, j, k}_{αβγ} ∈ Ξ \ I in N if

d_{H}(P_{ξ}) < α_{0},

where α_{0} is given in (29) and (32).

We now put N = H∩K_{3}(N). Note that by the definition of N, every triad P_{ξ} with ξ ∈ N is an (l, ε, 3)-cylinder. It follows from Fact 15 that for the constant θ in (35) and our choice of ε in (46), we have

\frac{m^{3}}{l^{3}} (1 − θ) < |K_{3}(P_{ξ})| < \frac{m^{3}}{l^{3}} (1 + θ).

Therefore, we conclude that |N | satisfies

|N | ≤ α_{0}\binom{t}{3}l^{3} (\frac{n}{t})^{3} \frac{1}{l^{3}} (1 + θ) ≤ \frac{α_{0}}{3} n^{3}.  (56)

As for I, we shall be considering N as a multi-hypergraph on the vertex set [t] (that is, a multi-set on [t]^{3}).

Definition of M. We put ξ = {i, j, k}_{αβγ} ∈ Ξ \ I in M if P_{ξ} is a ‘thick’ regular triad, that is, a regular triad that captures many triples of H. More precisely, we put ξ = {i, j, k}_{αβγ} ∈ Ξ \ I in M if

d_{H}(P_{ξ}) > 1 − α_{0},

where α_{0} is given in (29) and (32). We also put M = H ∩ K_{3}(M).

We are interested in estimating |M|. Set

c_{M} = |M| /\binom{t}{3}l^{3} .

As when dealing with N and N, we observe that every triad P_{ξ} with ξ ∈ M is an (l, ε, 3)-cylinder. Applying Fact 15 to each such triad P_{ξ} we conclude that

\frac{m^{3}}{l^{3}} (1 − θ) < |K_{3}(P_{ξ})| < \frac{m^{3}}{l^{3}} (1 + θ),

and hence

|M|\frac{m^{3}}{l^{3}} (1 − θ) < |K_{3}(M)| < |M|\frac{m^{3}}{l^{3}} (1 + θ).  (57)

Consequently,

c_{M}\binom{t}{3}l^{3}(1 − α_{0})\frac{m^{3}}{l^{3}} (1 − θ) ≤ |M| ≤ c_{M}\binom{t}{3}l^{3} \frac{m^{3}}{l^{3}} (1 + θ).  (58)

Finally, M may also be considered as a multi-hypergraph on the vertex set [t].

Definition of G. We now let G = Ξ \ (I ∪ N ∪ M). Thus, ξ ∈ G if P_{ξ} is a regular triad with density with respect to H bounded away from 0 and 1 by at least α_{0}. More precisely, we have ξ = {i, j, k}_{αβγ} ∈ G if and only if

(i) α, β, γ > 0 and P_{ξ} = P_{α}^{ij} ∪ P_{β}^{jk} ∪ P_{γ}^{ik} is an (l, ε, 3)-cylinder, (ii) H is (ᾱ, δ, r)-regular with respect to P_{ξ}, where ᾱ = ᾱ(ξ) satisfies α_{0} ≤ ᾱ ≤ 1 − α_{0}. We now state the following claim about G.

Lemma 32. With μ > 0 as defined in (18), we have

|G| ≤ (ex_{ind}(t, 𝔽) + 4μ\binom{t}{3}) l^{3}.  (59)

Owing to the technical nature of our proof of Lemma 32 above, we give its proof in a separate section (see Section 4.2.3) and continue proving (50). Before we proceed, let us remark that, as with I, N and M, the system G may be viewed as a multi-hypergraph on [t].

We now put G = H ∩ K_{3}(G). The main use of Lemma 32 is in estimating the total number of triple systems G that may arise in this form, once G is fixed.

To that end, consider

K_{3}(G) = ⋃_{ξ∈G} K_{3}(P_{ξ}).

It follows from Fact 15 that, for the constant θ in (35) and our choice of ε in (46), we have

|K_{3}(P_{ξ})| < \frac{m^{3}}{l^{3}} (1 + θ).  (60)

Using Lemma 32 and (60), we see that

|K_{3}(G)| ≤ \frac{m^{3}}{l^{3}} (1 + θ)|G|,
≤ m^{3} (ex_{ind}(t, 𝔽) + 4μ\binom{t}{3}) (1 + θ).

The easy but essential observation now is that, if G is fixed, the total number of systems G that may arise as H ∩ K_{3}(G), as we vary H ∈ C, is at most

2^{|K_{3}(G)|} ≤ 2^{m^{3}(ex_{ind}(t,𝔽)+4μ\binom{t}{3})(1+θ)}
≤ 2^{(n/t)^{3}(ex_{ind}(t,𝔽)+4μ\binom{t}{3})(1+θ)}  (61)

(see (53)).

Definition of E_{0}. We define E_{0} to consist of all triples e ∈ H that do not occur in

K_{3}(Ξ) = ⋃_{ξ∈Ξ} K_{3}(P_{ξ}).  (62)

More explicitly, a triple e ∈ H is in E_{0} if either

(i) e ∩ V_{0} ≠ ∅, or else (ii) |e ∩ V_{i}| ≥ 2 for some i ∈ [t]. Note that |E_{0}| satisfies

|E_{0}| ≤ T_{0}n^{2} + nt (\frac{n}{t})^{2} ≤ (o(1) + \frac{1}{t_{0}} ) n^{3} ≤ δn^{3},  (63)

where the last inequality follows from (39).

Final estimate for |C|. We now put together the information we have to prove (50). We start by recalling that the number of partitions of Ξ = Ξ(P) is

4^{|Ξ|} = O(1).  (64)

The number of choices that there exist for E_{0} = E_{0}(H) (H ∈ C) is, because of (63),

≤ \binom{\binom{n}{3}}{δn^{3}}.  (65)

The number of choices that there exist for I = I(H) (H ∈ C) is, because of (55),

≤ \binom{\binom{n}{3}}{3δn^{3}}.  (66)

The number of choices that there exist for N = N (H) (H ∈ C) is, because of (56),

≤ \binom{\binom{n}{3}}{(α_{0}/3)n^{3}}.  (67)

Additionally, recalling (52), (58), and (57), we see that the number of choices that there exist for M = M(H) (H ∈ C), once M ⊂ Ξ is fixed, is

≤ \binom{|K_{3}(M)|}{(2θ + α_{0} − α_{0}θ)|K_{3}(M)|}

≤ \binom{c_{M(H)}\binom{t}{3}m^{3}(1 + θ)}{c_{M(H)}\binom{t}{3}m^{3}(1 − θ)(1 − α_{0})}
= \binom{c_{M(H)}\binom{t}{3}m^{3}(1 + θ)}{c_{M(H)}\binom{t}{3}m^{3}(1 + θ − (1 − θ)(1 − α_{0}))}

≤ (\frac{e(1 + θ)}{2θ + α_{0} − θα_{0}} )^{(2θ+α_{0}−θα_{0})n^{3}}
≤ 2^{(2θ+α_{0}−θα_{0})n^{3} log(2e/(2θ+α_{0}−θα_{0}))}.  (68)

Because of the inequality in (32), we further conclude that the quantity in (68) is

≤ 2^{σn^{3} log(2e/σ)} < 2^{2σn^{3} log(2e/σ)}.  (69)

Combining (61) with (64)–(67), and (69), we infer that

log_{2} |C| ≤ (ex_{ind}(t, 𝔽) + 4μ\binom{t}{3}) \frac{n^{3}}{t^{3}} (1 + θ) + 4n^{3}σ log \frac{2e}{σ} + O(1).  (70)

The major work in bounding |C| from above is finished. However, to establish (50), we need to replace ex_{ind}(t, 𝔽) by ex_{ind}(n, 𝔽). Recall that we chose k_{0} in (25) so that, for the auxiliary constant τ > 0 in (21), we have

|\binom{t}{3}^{−1}ex_{ind}(t, 𝔽) − \binom{n}{3}^{−1}ex_{ind}(n, 𝔽)| < τ

for all n ≥ t ≥ k_{0} or, equivalently,

|\binom{t}{3}^{−1}\binom{n}{3}ex_{ind}(t, 𝔽) − ex_{ind}(n, 𝔽)| < τ\binom{n}{3}.

With n sufficiently large, the above inequality implies

ex_{ind}(t, 𝔽)\frac{n^{3}}{t^{3}} ≤ ex_{ind}(n, 𝔽) + τn^{3}.  (71)

Combining (70) with (71) we obtain

log_{2} |C| ≤ (ex_{ind}(n, 𝔽) + τn^{3} + 4μn^{3})(1 + θ) + 4n^{3}σ log \frac{2e}{σ} + O(1).

Therefore, inequality (50) follows.

We now return to the task of proving Lemma 32.

4.2.3. Proof of Lemma 32. The proof of Lemma 32 will require some work. We shall in fact make use of two auxiliary propositions (Propositions 33 and 36) and two auxiliary claims (Claims 34 and 35). The proofs of these results are given in later sections.

Let us now start the proof of Lemma 32. We shall suppose for a contradiction that we in fact have

|G| > (ex_{ind}(t, 𝔽) + 4μ\binom{t}{3}) l^{3}.  (72)

Recall we have the partition Ξ = I ∪ G ∪ N ∪ M of Ξ = Ξ(P) as in (51). Moreover, we recall that we may think of I, G, N, and M as multi-hypergraphs.

We prove the proposition below, which extends Fact 4.1 of [15]. Let ψ: [t]^{2} → [l] be any ‘choice’ function. We say that ξ = {i, j, k}_{αβγ} ∈ Ξ is chosen by ψ if

ψ({i, j}) = α, ψ({j, k}) = β, and ψ({i, k}) = γ.

Proposition 33. There exists ψ: [t]^{2} → [l] such that

|\{ξ ∈ G: ξ is chosen by ψ\}| ≥ \frac{|G|}{l^{3}} (1 − \frac{μ}{2}) ,

and

|\{ξ ∈ I: ξ is chosen by ψ\}| ≤ δ^{1/2}\binom{t}{3}.

We shall prove Proposition 33 in Section 4.2.4. Let us continue with the proof of Lemma 32. Recall our (contrary) assumption in (72). Let ψ: [t]^{2} → [l] be the function guaranteed by Proposition 33, and define G^{ψ}, I^{ψ}, N^{ψ}, and M^{ψ} as

G^{ψ} = {{i, j, k} ∈ [t]^{3}: ∃ξ = {i, j, k}_{αβγ} ∈ G such that ψ chooses ξ}
I^{ψ} = {{i, j, k} ∈ [t]^{3}: ∃ξ = {i, j, k}_{αβγ} ∈ I such that ψ chooses ξ}  (73)
N^{ψ} = {{i, j, k} ∈ [t]^{3}: ∃ξ = {i, j, k}_{αβγ} ∈ N such that ψ chooses ξ}
M^{ψ} = {{i, j, k} ∈ [t]^{3}: ∃ξ = {i, j, k}_{αβγ} ∈ M such that ψ chooses ξ}

Note that G^{ψ}, I^{ψ}, N^{ψ} and M^{ψ} are each triple systems on the vertex set [t] = {1, …, t}, without parallel triples. Note that [t]^{3} = G^{ψ} ∪ I^{ψ} ∪ N^{ψ} ∪ M^{ψ} is a partition. We infer from (72) and Proposition 33 that

|G^{ψ}| ≥ \frac{|G|}{l^{3}} (1 − \frac{μ}{2})
> (ex_{ind}(t, 𝔽) + 4μ\binom{t}{3}) (1 − \frac{μ}{2}) ,
≥ ex_{ind}(t, 𝔽) + 2μ\binom{t}{3},  (74)

and

|I^{ψ}| ≤ δ^{1/2}\binom{t}{3}.

If we could ensure I^{ψ} = ∅ now, we could immediately begin working on producing a contradiction. However, since we cannot ensure that I^{ψ} = ∅, our goal is to find a subset K_{0} ⊆ [t] with |K_{0}| = k_{0} (see (25)), with [K_{0}]^{3} ∩ I^{ψ} = ∅ and G^{ψ} ∩ [K_{0}]^{3} large. We now produce this set K_{0}. For convenience, in what follows, we define the following set:

K_{good, G^{ψ}} = \{K ∈ [t]^{k_{0}}: |G^{ψ} ∩ [K]^{3}| ≥ ex_{ind}(k_{0}, 𝔽) + μ\binom{k_{0}}{3}\} .  (75)

We now state the following claim, whose proof is postponed to Section 4.2.5.

Claim 34. The inequality in (74) implies that

|K_{good, G^{ψ}}| ≥ μ^{3}\binom{t}{k_{0}}.

We continue with another claim. Once again, for convenience, we use the following notation analogous to (75). Define

K_{good, I^{ψ}} = {K ∈ [t]^{k_{0}}: [K]^{3} ∩ I^{ψ} = ∅} .

Our claim is then as follows.

Claim 35.

|K_{good, I^{ψ}} | ≥ (1 − δ^{1/2}\binom{k_{0}}{3}) \binom{t}{k_{0}}.  (76)

Claim 35 is proved in Section 4.2.5. As a result of Claims 34 and 35, we have

|K_{good, G^{ψ}} ∩ K_{good,I^{ψ}} | ≥ (μ^{3} − δ^{1/2}\binom{k_{0}}{3}) \binom{t}{k_{0}} > 0,

where the last inequality follows from (28) and (38). Let K_{0} ∈ [t]^{k_{0}} satisfy that

K_{0} ∈ K_{good, G^{ψ}} ∩ K_{good,I^{ψ}}.

For M^{ψ}, N^{ψ}, and G^{ψ} given in (73), set

M_{K_{0}}^{ψ} = M^{ψ} ∩ [K_{0}]^{3},
N_{K_{0}}^{ψ} = N^{ψ} ∩ [K_{0}]^{3},
G_{K_{0}}^{ψ} = G^{ψ} ∩ [K_{0}]^{3}.

We note the following properties of M_{K_{0}}^{ψ}, N_{K_{0}}^{ψ}, and G_{K_{0}}^{ψ}. (I) Recall that G^{ψ}, I^{ψ}, M^{ψ}, and N^{ψ} are each triple systems on vertex set [t]. Conse-

quently, G_{K_{0}}^{ψ}, M_{K_{0}}^{ψ}, and N_{K_{0}}^{ψ} are triple systems with vertex set K_{0}. Moreover, recall that G^{ψ} ∪ I^{ψ} ∪ M^{ψ} ∪ N^{ψ} = [t]^{3} is a partition of [t]^{3}. Since I^{ψ} ∩ [K_{0}]^{3} = ∅, we infer that G_{K_{0}}^{ψ} ∪ M_{K_{0}}^{ψ} ∪ N_{K_{0}}^{ψ} = [K_{0}]^{3} is a partition of [K_{0}]^{3}.

(II) Since K_{0} ∈ K_{good, G^{ψ}}, the system G_{K_{0}}^{ψ} satisfies

|G_{K_{0}}^{ψ}| = |G^{ψ} ∩ [K_{0}]^{3}| ≥ ex_{ind}(k_{0}, 𝔽) + μ\binom{k_{0}}{3} > ex_{ind}(k_{0}, 𝔽).

(III) Following our observations in (I) and (II), since G_{K_{0}}^{ψ} ∪ M_{K_{0}}^{ψ} ∪ N_{K_{0}}^{ψ} = [K_{0}]^{3} is a partition of [K_{0}]^{3} and |G_{K_{0}}^{ψ}| > ex_{ind}(k_{0}, 𝔽), it follows directly from the definition

of ex_{ind}(k_{0}, 𝔽) that there exists G̃_{K_{0}}^{ψ} ⊆ G_{K_{0}}^{ψ} and F ∈ 𝔽 so that F is an induced

subhypergraph of G̃_{K_{0}}^{ψ} ∪ M_{K_{0}}^{ψ}. We show that, as a result of the conclusion in (III), the same hypergraph F must also appear as an induced subhypergraph of H, which will be a contradiction. Before showing this, however, we expand our observation in (III).

Let F_{0} be the copy of F induced in G̃_{K_{0}}^{ψ} ∪ M_{K_{0}}^{ψ}. For simplicity of notation, we suppose V (F_{0}) = [f_{0}] = {1, …, f_{0}}. We observe the following:

(IV) Each 1 ≤ i ≤ f_{0} corresponds to a vertex class V_{i} of our (δ, r)-regular, (l, t, γ, ε)- equitable partition P. Moreover, every 1 ≤ i < j ≤ f_{0} corresponds to a bipartite graph P^{ij} = P_{α}^{ij} with bipartition V_{i} ∪ V_{j} in our partition P, where α = ψ({i, j}) > 0 for the function ψ: [t]^{2} → [l] given by Proposition 33. Finally, every 1 ≤ i < j < k ≤ f_{0} corresponds to a triad P^{ij} ∪ P^{jk} ∪ P^{ik} of our partition P.

(V) Since [f_{0}]^{3} ∩ I^{ψ} = ∅, each 1 ≤ i < j ≤ f_{0} corresponds to an (l, ε, 2)-cylinder P^{ij} in our partition P. Moreover, since [f_{0}]^{3} ∩ I^{ψ} = ∅, every triad P^{ij} ∪ P^{jk} ∪ P^{ik} (1 ≤ i < j < k ≤ f_{0}) is (δ, r)-regular with respect to H.

(VI) Every {i, j, k} ∈ G̃_{K_{0}}^{ψ} ∩ F_{0} corresponds to a triad P^{ij} ∪ P^{jk} ∪ P^{ik} of our partition P satisfying that P^{ij} ∪ P^{jk} ∪ P^{ik} is (ᾱ, δ, r)-regular with respect to H, for some ᾱ = ᾱ({i, j, k}) with α_{0} ≤ ᾱ ≤ 1 − α_{0}, where α_{0} is given in (29) and (32).

(VII) Every {i, j, k} ∈ M_{K_{0}}^{ψ}∩F_{0} corresponds to a triad P = P^{ij}∪P^{jk}∪P^{ik} of our partition P

such that H has P -density d_{P} (H) satisfying d_{P} (H) > 1 − α_{0} > α_{0}. (VIII) For every triple \{i, j, k\} ∈ \overline{F_{0}}, where \overline{F_{0}} = [f_{0}]^{3} \ F_{0} is the complement of F_{0}, we

have {i, j, k} ∈ N_{K_{0}}^{ψ} ∪ G_{K_{0}}^{ψ}. Indeed, F_{0} is induced in G̃_{K_{0}}^{ψ} ∪ M_{K_{0}}^{ψ} and hence, in particular, \overline{F_{0}} ∩ M_{K_{0}}^{ψ} = ∅. We distinguish between two cases.

(VIII)(a) If {i, j, k} ∈ G_{K_{0}}^{ψ}, then we conclude, as in (VI), that the triad P^{ij} ∪ P^{jk} ∪ P^{ik} is (ᾱ, δ, r)-regular with respect to H, for some ᾱ = ᾱ({i, j, k}) with α_{0} ≤ ᾱ ≤

1 − α_{0}.

(VIII)(b) If {i, j, k} ∈ N_{K_{0}}^{ψ}, then we conclude that H has P -density d_{P} (H) satisfying

d_{P} (H) < α_{0}, where P = P^{ij} ∪ P^{jk} ∪ P^{ik}. This concludes our observations concerning G_{K_{0}}^{ψ}, M_{K_{0}}^{ψ}, and N_{K_{0}}^{ψ}.

We proceed with the following proposition.

Proposition 36. There exists a set X_{0} ⊆ V (H) and a function π: [f_{0}] → X_{0} so that π is an isomorphism between F_{0} and H ∩ [X_{0}]^{3}.

Note that Proposition 36 contradicts the fact that H ∈ Forb_{ind}(n, 𝔽) since π guarantees that H ∩ [X_{0}]^{3} is an induced copy of F in H. Therefore, assumption (72) is indeed false, and Lemma 32 is proved.

In the remaining sections, we prove Propositions 33 and 36 and Claims 34 and 35.

4.2.4. Proof of Proposition 33. The proof of Proposition 33 will be based on the probabilistic method.

Proof of Proposition 33. We begin our proof by defining

ϱ = |G| /\binom{t}{3}l^{3} .

If ϱ = 1, Proposition 33 is easily implied by Fact 4.1 of [15]. Consequently, we may and shall assume that ϱ < 1.

We estimate ϱ. Note that it follows from our assumption in (72) that

ϱ = |G| /\binom{t}{3}l^{3} > \binom{t}{3}^{−1}ex_{ind}(t, 𝔽) + 4μ\binom{t}{3} > 4μ.  (77)

We now define an auxiliary bipartite graph Γ = (V (Γ), E(Γ)). To that effect, let Ψ = {ψ: [t]^{2} → [l]} and W = [t]^{3} × [l] × [l] × [l]. We have Ξ ⊂ W. Note that

|Ψ| = l^{\binom{t}{2}}  (78)

and

|W | = \binom{t}{3}l^{3}.  (79)

Define the bipartite graph Γ by setting

V (Γ) = Ψ ∪ W,

and

E(Γ) = {{ψ, ξ}: ψ chooses ξ}.

For a vertex x ∈ V (Γ), let N_{Γ}(x) denote the neighbourhood of x in Γ as usual, that is, N_{Γ}(x) = {y ∈ V (Γ): {x, y} ∈ E(Γ)}. Note that for each ψ ∈ Ψ,

|N_{Γ}(ψ)| = \binom{t}{3},  (80)

and, for each ξ ∈ W,

|N_{Γ}(ξ)| = l^{\binom{t}{2}−3}.  (81)

For ψ ∈ Ψ, set

N_{Γ,G}(ψ) = N_{Γ}(ψ) ∩ G,
N_{Γ,I}(ψ) = N_{Γ}(ψ) ∩ I.

In the notation above, Proposition 33 states that there exists ψ ∈ Ψ such that

|N_{Γ,G}(ψ)| ≥ \frac{|G|}{l^{3}} (1 − \frac{μ}{2}) ,  (82)

and

|N_{Γ,I}(ψ)| ≤ δ^{1/2}\binom{t}{3}.  (83)

To prove the existence of ψ ∈ Ψ satisfying (82) and (83), we proceed with the following considerations. Note that the average degrees Ave(|N_{Γ,G}|) = |Ψ|^{−1} ∑_{ψ∈Ψ} |N_{Γ,G}(ψ)| and Ave(|N_{Γ,I}|) = |Ψ|^{−1}∑_{ψ∈Ψ} |N_{Γ,I}(ψ)| satisfy

Ave(|N_{Γ,G}|) = |Ψ|^{−1} ∑_{ψ∈Ψ} |N_{Γ,G}(ψ)| = |Ψ|^{−1} ∑_{ξ∈G} |N_{Γ}(ξ)|

and

Ave(|N_{Γ,I}|) = |Ψ|^{−1} ∑_{ψ∈Ψ} |N_{Γ,I}(ψ)| = |Ψ|^{−1} ∑_{ξ∈I} |N_{Γ}(ξ)|.

As a result of (81), we further see that

Ave(|N_{Γ,G}|) = \frac{|G|}{l^{3}}  (84)

and

Ave(|N_{Γ,I}|) = \frac{|I|}{l^{3}}.  (85)

Now, set

η = \frac{μ}{2} × \frac{ϱ}{1 − ϱ},  (86)

and

d = 1 + \frac{2}{η} .  (87)

Note that d > 1. We shall see that Proposition 33 easily follows from the next fact.

Fact 37. For ψ ∈ Ψ chosen independently and uniformly at random, we have

Pr [ψ satisfies |N_{Γ,G}(ψ)| > \frac{|G|}{l^{3}} (1 − \frac{μ}{2}) and |N_{Γ,I}(ψ)| ≤ d\frac{|I|}{l^{3}}] > 0.

Before proving Fact 37, we observe that the existence of ψ ∈ Ψ satisfying |N_{Γ,G}(ψ)| > |G|l^{−3}(1 − μ/2) and |N_{Γ,I}(ψ)| ≤ |I|dl^{−3} proves Proposition 33. Indeed, to see that |N_{Γ,I}(ψ)| ≤ δ^{1/2}\binom{t}{3}, consider the following. With d = 1 + 2/η, we see by (54) that

d\frac{|I|}{l^{3}} ≤ (1 + \frac{2}{η} ) 100δ\binom{t}{3} = (100δ + \frac{200δ}{η} ) \binom{t}{3}.

With η given in (86) and the inequality in (77), we further see that

d\frac{|I|}{l^{3}} ≤ (100δ + \frac{100δ}{μ^{2}} ) \binom{t}{3}.

With the inequality in (33), we conclude that

d\frac{|I|}{l^{3}} ≤ (100δ + \frac{100δ}{μ^{2}} ) \binom{t}{3} ≤ δ^{1/2}\binom{t}{3}.

The proof of Proposition 33 is complete.

We now prove Fact 37.

Proof of Fact 37. Independently and uniformly at random, select ψ ∈ Ψ. Clearly,

Pr [|N_{Γ,G}(ψ)| < \frac{|G|}{l^{3}} (1 − \frac{μ}{2}) or |N_{Γ,I}(ψ)| > d\frac{|I|}{l^{3}}]
≤ Pr [|N_{Γ,G}(ψ)| < \frac{|G|}{l^{3}} (1 − \frac{μ}{2})] + Pr [|N_{Γ,I}(ψ)| > d\frac{|I|}{l^{3}}] . (88)

We bound (88) from above, and begin by easily estimating the second term on the righthand side of this inequality.

We see that

Pr [|N_{Γ,I}(ψ)| > d\frac{|I|}{l^{3}}] < \frac{1}{d}.  (89)

Indeed, (85) says that

E[|N_{Γ,I}(ψ)|] = \frac{|I|}{l^{3}},

and hence Markov’s inequality tells us that (89) follows.

To bound the first term on the right-hand side of (88), we proceed with the following fact.

Fact 38.

Pr [|N_{Γ,G}(ψ)| < \frac{|G|}{l^{3}} (1 − \frac{μ}{2})] < \frac{1}{1 + η} .

We now continue our proof of Fact 37 assuming Fact 38. For the randomly chosen ψ ∈ Ψ, we infer from (88), (89), and (98) that

Pr [|N_{Γ,G}(ψ)| < \frac{|G|}{l^{3}} (1 − \frac{μ}{2}) or |N_{Γ,I}(ψ)| > d\frac{|I|}{l^{3}}] < \frac{1}{d} + \frac{1}{1 + η} .  (90)

However, as defined in (87), d = 1 + 2/η, thus

\frac{1}{d} + \frac{1}{1 + η} = \frac{η}{2 + η} + \frac{1}{1 + η} < 1.

Thus our proof of Fact 37 is complete.

We now have to prove Fact 38.

Proof of Fact 38. For ψ ∈ Ψ, we infer from (80) that

|N_{Γ,G}(ψ)| + |N_{Γ}(ψ) \ N_{Γ,G}(ψ)| = |N_{Γ}(ψ)| = \binom{t}{3}.  (91)

Note that (84) says that for ψ ∈ Ψ randomly chosen,

E[|N_{Γ,G}(ψ)|] = \frac{|G|}{l^{3}}.

From (91), we thus infer that

E[|N_{Γ}(ψ) \ N_{Γ,G}(ψ)|] = \binom{t}{3} − E[|N_{Γ,G}(ψ)|],
= \binom{t}{3} − \frac{|G|}{l^{3}}.  (92)

Now, for ψ ∈ Ψ, if

|N_{Γ,G}(ψ)| < \frac{|G|}{l^{3}} (1 − \frac{μ}{2}) ,  (93)

it would then follow from (91) that

|N_{Γ}(ψ) \ N_{Γ,G}(ψ)| > \binom{t}{3} − \frac{|G|}{l^{3}} (1 − \frac{μ}{2}) .  (94)

One can calculate that with η = (μ/2)(ϱ/(1 − ϱ)), we have

\binom{t}{3} − \frac{|G|}{l^{3}} (1 − \frac{μ}{2}) ≥ (1 + η) (\binom{t}{3} − \frac{|G|}{l^{3}}) .

Thus, from (92), if ψ ∈ Ψ is randomly chosen and satisfies (93), then

|N_{Γ}(ψ) \ N_{Γ,G}(ψ)| > \binom{t}{3} − \frac{|G|}{l^{3}} (1 − \frac{μ}{2}) ≥ (1 + η)E[|N_{Γ}(ψ) \ N_{Γ,G}(ψ)|].  (95)

Thus, we infer from (93), (94), and (95) that

Pr [|N_{Γ,G}(ψ)| < \frac{|G|}{l^{3}} (1 − \frac{μ}{2})] ≤ Pr [|N_{Γ}(ψ)\N_{Γ,G}(ψ)| > (1+η)E[|N_{Γ}(ψ)\N_{Γ,G}(ψ)|]].

(96)

Using Markov’s inequality, we see that

Pr [|N_{Γ}(ψ) \ N_{Γ,G}(ψ)| > (1 + η)E[|N_{Γ}(ψ) \ N_{Γ,G}(ψ)|]] < \frac{1}{1 + η} .  (97)

We infer from (96) and (97) that

Pr [|N_{Γ,G}(ψ)| < \frac{|G|}{l^{3}} (1 − \frac{μ}{2})] < \frac{1}{1 + η} ,  (98)

and thus the proof of Fact 38 is complete.

4.2.5. Proof of Claims 34 and 35. In this section we prove the two claims that we used in the proof of Lemma 32. We start with Claim 34.

Proof of Claim 34. On the contrary, assume

|K_{good, G^{ψ}}| < μ^{3}\binom{t}{k_{0}}.  (99)

Define an auxiliary bipartite graph Λ = (V (Λ), E(Λ)) with bipartition V (Λ) = [t]^{k_{0}} ∪ [t]^{3} and edge set E(Λ) = {{K, Y }: K ∈ [t]^{k_{0}}, Y ∈ [K]^{3} ∩ G^{ψ}}. Then

|G^{ψ}|\binom{t − 3}{k_{0} − 3} = |E(Λ)| = ∑_{K∈[t]^{k_{0}}} deg_{Λ}(K).  (100)

By (74), we see that

|G^{ψ}|\binom{t − 3}{k_{0} − 3} > (ex_{ind}(t, 𝔽) + 2μ\binom{t}{3}) \binom{t − 3}{k_{0} − 3}.  (101)

On the other hand, our assumption in (99) says that more than (1−μ^{3})\binom{t}{k_{0}} sets K ∈ [t]^{k_{0}} satisfy

deg_{Λ}(K) < ex_{ind}(k_{0}, 𝔽) + μ\binom{k_{0}}{3}.  (102)

Hereditary Properties of Triple Systems 31

Applying (101) and (102) to (100), we conclude

\binom{t − 3}{k_{0} − 3} (ex_{ind}(t, 𝔽) + 2μ\binom{t}{3})

< (1 − μ^{3})\binom{t}{k_{0}} (ex_{ind}(k_{0}, 𝔽) + μ\binom{k_{0}}{3}) + μ^{3}\binom{t}{k_{0}}\binom{k_{0}}{3}

≤ \binom{t}{k_{0}} (ex_{ind}(k_{0}, 𝔽) + μ\binom{k_{0}}{3}) + μ^{3}\binom{t}{k_{0}}\binom{k_{0}}{3}.

Dividing through by \binom{t}{k_{0}}\binom{k_{0}}{3}, we obtain

\binom{t}{3}^{−1}ex_{ind}(t, 𝔽) + 2μ < \binom{k_{0}}{3}^{−1}ex_{ind}(k_{0}, 𝔽) + μ + μ^{3},

or, equivalently,

μ < \binom{k_{0}}{3}^{−1}ex_{ind}(k_{0}, 𝔽) − \binom{t}{3}^{−1}ex_{ind}(t, 𝔽) + μ^{3}.  (103)

Note that with t_{0} and k_{0} defined in (25) and (39), and with t ≥ t_{0}, we have

\binom{k_{0}}{3}^{−1}ex_{ind}(k_{0}, 𝔽) − \binom{t}{3}^{−1}ex_{ind}(t, 𝔽) < τ.  (104)

Employing (104) in (103), we obtain

μ < τ + μ^{3}.

With τ < μ^{3} (see (23)), we further conclude that

μ < 2μ^{3},

which contradicts μ < 1/2 (see (23)). Thus, Claim 34 is proved. Proof of Claim 35. For each \{i, j, k\}_{αβγ} ∈ I^{ψ}, there are at most \binom{t−3}{k_{0}−3} sets K ∈ [t]^{k_{0}} with \{i, j, k\}_{αβγ} ∈ [K]^{3}. Since |I^{ψ}| < δ^{1/2}\binom{t}{3}, we have

| \{K ∈ [t]^{k_{0}}: [K]^{3} ∩ I^{ψ} ≠ ∅\} | ≤ |I^{ψ}|\binom{t − 3}{k_{0} − 3},
< δ^{1/2}\binom{t}{3}\binom{t − 3}{k_{0} − 3},
= δ^{1/2}\binom{k_{0}}{3}\binom{t}{k_{0}},

which implies (76) and hence Claim 35 is proved. 4.2.6. Proof of Proposition 36. We first produce the promised set X_{0}. To that end, define the f_{0}-partite graph

P_{f_{0}} = ⋃_{1≤i<j≤f_{0}} P^{ij}.

Note that P_{f_{0}} has vertex set V_{1} ∪ … ∪ V_{f_{0}}. Note that, because of (V), our graph P_{f_{0}} is an (l, ε, f_{0})-cylinder.

In what follows, we shall work with triples ϑ = {i, j, k}, where 1 ≤ i < j < k ≤ f_{0}. Let Θ = {ϑ = {i, j, k}: 1 ≤ i < j < k ≤ f_{0}} be the set of such triples. For each ϑ = {i, j, k} ∈ Θ, we have the triad P_{ϑ} = P^{ij} ∪P^{jk} ∪P^{ik}. Moreover, for each ϑ = {i, j, k} ∈ Θ, define the triple system

D^{ϑ} = \{ \begin{matrix}H ∩ K_{3}(P_{ϑ}) & if ϑ ∈ F_{0}, \\ K_{3}(P_{ϑ}) \ H & if ϑ ∉ F_{0}. \end{matrix}

Set

D = ⋃_{ϑ∈Θ} D^{ϑ}.

Note that D has vertex set V_{1}∪…∪V_{f_{0}}. We now make the following observations about D and P_{f_{0}}.

(a) Because of (V), for every ϑ = {i, j, k} ∈ F_{0}, the 3-partite hypergraph D^{ϑ} is (δ, r)- regular with respect to P_{ϑ}. Additionally, as H is (δ, r)-regular with respect to every P_{ϑ} (ϑ ∈ Θ), it follows that K_{3}(P_{ϑ}) \ H is also (δ, r)-regular with respect to P_{ϑ}. Consequently, for every ϑ ∈ Θ, the system D^{ϑ} is (δ, r)-regular with respect to P_{ϑ}.

(b) Observe that, for every ϑ ∉ F_{0}, we have

d_{P_{ϑ}}(D^{ϑ}) = 1 − d_{P_{ϑ}}(H).

(c) Because of (VI) and (VII), if ϑ ∈ F_{0}, then D^{ϑ} is (ᾱ, δ, r)-regular with respect to P_{ϑ}, where ᾱ = ᾱ(ϑ) ≥ α_{0}.

(d) Suppose that ϑ ∈ Θ\F_{0}. From (VIII) we see that ϑ ∈ G_{K_{0}}^{ψ} ∪N_{K_{0}}^{ψ}. From (VIII)(a), we have that if ϑ ∈ G_{K_{0}}^{ψ}, then d_{P_{ϑ}}(H) ≤ 1−α_{0}. If ϑ ∈ N_{K_{0}}^{ψ}, then d_{P_{ϑ}}(H) < α_{0}. Using (b), we conclude in either case that d_{P_{ϑ}}(D^{ϑ}) = 1 − d_{P_{ϑ}}(H) ≥ α_{0}. Thus, for ϑ ∈ Θ \ F_{0}, we have that D^{ϑ} is (ᾱ, δ, r)-regular with respect to P_{ϑ}, where ᾱ = ᾱ(ϑ) ≥ α_{0}.

(e) Combining our observations in (c) and (d), for all ϑ, the system D^{ϑ} is (ᾱ, δ, r)-regular with respect to P_{ϑ}, where ᾱ = ᾱ(ϑ) ≥ α_{0}.

(f ) Owing to the inequalities in (37) and (42), we have δ ≤ δ_{31}(f_{0}, α_{0}) and r ≥ r_{31}(f_{0}, α_{0}, δ, l), where δ_{31}(f_{0}, α_{0}) verified the applicability of Lemma 31 for the parameters f_{0} and α_{0} and r_{31}(f_{0}, α_{0}, δ, l) verified the applicability of Lemma 31 for the parameters f_{0}, α_{0}, δ, and l.

(g) P_{f_{0}} is an (l, ε, f_{0})-cylinder. Here, because of (43), we have ε ≤ ε_{31}(f_{0}, α_{0}, δ, l, r), where ε_{31}(f_{0}, α_{0}, δ, l, r) verified the applicability of Lemma 31 for the parameters f_{0}, α_{0}, δ, l, and r.

(h) By observations (a)–(g) above, we see that D and P_{f_{0}} satisfy the hypotheses of Lemma 31. As a result, we conclude that D contains a copy of K_{f_{0}}^{(3)}. We are nearly finished with the proof of Proposition 36. Let X_{0} be a vertex set inducing

a copy of K_{f_{0}}^{(3)} in D. We now show that X_{0} induces a copy of F in H. Indeed, define a function π: [f_{0}] → X_{0} by letting π(i) be the unique element of V_{i} ∩ X_{0}, for each i ∈ [f_{0}]. We proceed with the following claim.

Claim 39. The map π: [f_{0}] → X_{0} is an isomorphism between F_{0} and H ∩ [X_{0}]^{3}.

Proof. Clearly π is a bijection. We show that ϑ = {i, j, k} ∈ F_{0} if and only if π(ϑ) = {π(i), π(j), π(k)} ∈ H ∩ [X_{0}]^{3}. Let ϑ ∈ Θ be given. As X_{0} spans a copy of K_{f_{0}}^{(3)} in D, clearly, π(ϑ) ∈ D^{ϑ}. We consider the following two cases. Case 1. ϑ ∈ F_{0} In this case, by the definition of D^{ϑ}, we have D^{ϑ} = H ∩ K_{3}(P_{ϑ}). As π(ϑ) ∈ D^{ϑ}, we have π(ϑ) ∈ H.

Case 2. ϑ ∈ Θ \ F_{0} In this case, by the definition of D^{ϑ}, we have D^{ϑ} = K_{3}(P_{ϑ}) \ H. As π(ϑ) ∈ D^{ϑ}, we have π(ϑ) ∉ H.

In view of the above, the proof of Claim 39 is complete.

This finishes our proof of Proposition 36.

5. Concluding remarks

We believe that the investigation of the parameter ex_{ind}(n, F) may be of independent interest. As observed before, the determination of ex_{ind}(n, F) for general hypergraphs F will not be simple, as this problem is more general than that of determining Turán numbers for complete hypergraphs. It would be interesting to study the behaviour of ex_{ind}(n, F) in greater depth, further clarifying the similarities and differences between ex_{ind}(n, F) and the classical Turán numbers ex(n, F). Let us give an example.

Recall that we defined the sets L_{<∞} and L_{<∞}^{ind} in Section 2, and that these sets are not well-ordered. Somewhat unexpectedly, the set of ‘left accumulation points’ of these sets coincide (we say that α is a left accumulation point of a set Z ⊂ ℝ if one may find a strictly decreasing sequence (α_{t})_{t=1}^{∞} in Z with α_{t} ↘ α). We hope to come back to this and related results in the near future.

The proof of our main result in this paper, Theorem 1, is based in a crucial manner on the Regularity Lemma from [11] and on the Counting Lemma from [16]. Even with these results at hand, the proof of Theorem 1 is fairly elaborate, at least from the technical point of view, because the basic objects involved in the Regularity Lemma and in the Counting Lemma are already somewhat technical. We believe that simplifying these lemmas to the point of making applications such as the one presented in this paper straightforward would be of great interest.

References

[1] V. E. Alekseev, On the entropy values of hereditary classes of graphs, Discrete Mathematics and Applications 3 (1993), 191–199.

[2] Béla Bollobás, Combinatorics, Cambridge University Press, Cambridge, 1986, Set systems, hypergraphs, families of vectors and combinatorial probability. MR 88g:05001

[3] Béla Bollobás and Andrew Thomason, Projections of bodies and hereditary properties of hypergraphs, Bull. London Math. Soc. 27 (1995), no. 5, 417–424. MR 96e:52006

[4] , Hereditary and monotone properties of graphs, The mathematics of Paul Erdős, II, Springer, Berlin, 1997, pp. 70–78. MR 98a:05085

34 Y. Kohayakawa, B. Nagle, and V. Rödl

[5] , The structure of hereditary properties and colourings of random graphs, Combinatorica 20 (2000), no. 2, 173–202. MR 2001e:05114

[6] P. Erdős, On extremal problems of graphs and generalized graphs, Israel Journal of Mathematics 2 (1964), 183–190.

[7] P. Erdős, P. Frankl, and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs and Combinatorics 2 (1986), no. 2, 113–121.

[8] P. Erdős, D. J. Kleitman, and B. L. Rothschild, Asymptotic enumeration of K_{n}-free graphs, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, Accad. Naz. Lincei, Rome, 1976, pp. 19–27. Atti dei Convegni Lincei, No. 17. MR 57 #2984

[9] P. Erdős and A. H. Stone, On the structure of linear graphs, Bulletin of the American Mathematical Society 52 (1946), 1087–1091.

[10] P. Frankl and V. Rödl, Hypergraphs do not jump, Combinatorica 4 (1984), no. 2-3, 149–159. MR 86f:05097

[11] Peter Frankl and Vojtěch Rödl, Extremal problems on set systems, Random Structures Algorithms 20 (2002), no. 2, 131–164. MR 1 884 430

[12] Gyula Katona, Tibor Nemetz, and Miklós Simonovits, On a problem of Turán in the theory of graphs, Mat. Lapok 15 (1964), 228–238. MR 30 #2483

[13] J. Komlós and M. Simonovits, Szemerédi’s regularity lemma and its applications in graph theory, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), János Bolyai Math. Soc., Budapest, 1996, pp. 295–352. MR 97d:05172

[14] L. H. Loomis and H. Whitney, An inequality related to the isoperimetric inequality, Bull. Amer. Math. Soc 55 (1949), 961–962. MR 11,166d

[15] Brendan Nagle and Vojtěch Rödl, The asymptotic number of triple systems not containing a fixed one, Discrete Math. 235 (2001), no. 1-3, 271–290, Combinatorics (Prague, 1998). MR 1 829 856

[16] , Regularity properties for triple systems, Random Structures & Algorithms (2002), to appear.

[17] Hans Jürgen Prömel and Angelika Steger, Excluding induced subgraphs: quadrilaterals, Random Structures and Algorithms 2 (1991), 55–71.

[18] , The asymptotic number of graphs not containing a fixed color-critical subgraph, Combinatorica 12 (1992), 463–473.

[19] , Excluding induced subgraphs III. A general asymptotic, Random Structures and Algorithms 3 (1992), no. 1, 19–31. MR 93d:05065

[20] , The asymptotic structure of H-free graphs, Graph structure theory (Seattle, WA, 1991), Contemp. Math., vol. 147, Amer. Math. Soc., Providence, RI, 1993, pp. 167–178.

[21] Vojtěch Rödl and Andrzej Ruciński, Ramsey properties of random hypergraphs, Journal of Combinatorial Theory, Series A 81 (1998), no. 1, 1–33. MR 98m:05175

[22] Edward R. Scheinerman and Jennifer Zito, On the size of hereditary classes of graphs, J. Combin. Theory Ser. B 61 (1994), no. 1, 16–39. MR 95e:05061

[23] Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), CNRS, Paris, 1978, pp. 399– 401. MR 81i:05095