EFFICIENT TESTING OF HYPERGRAPHS (EXTENDED ABSTRACT)

Y. KOHAYAKAWA*, B. NAGLE**, AND V. RÖDL***

Abstract. We investigate a basic problem in combinatorial property testing, in the sense of Goldreich, Goldwasser, and Ron [9, 10], in the context of 3-uniform hypergraphs, or 3-graphs for short. As customary, a 3-graph F is simply a collection of 3-element sets. Let Forb_{ind}(n, F) be the family of all 3-graphs on n vertices that contain no copy of F as an induced subhypergraph. We show that the property “H ∈ Forb_{ind}(n, F)” is testable, for any 3-graph F. In fact, this is a consequence of a new, basic combinatorial lemma, which extends to 3-graphs a result for graphs due to Alon, Fischer, Krivelevich, and Szegedy [2, 3].

Indeed, we prove that if more than ζn^{3} (ζ > 0) triples must be added or deleted from a 3graph H on n vertices to destroy all induced copies of F, then H must contain ≥ cn^{|V (F)|} induced copies of F, as long as n ≥ n_{0}(ζ, F). Our approach is inspired in [2, 3], but the main ingredients are hypergraph regularity lemmas and counting lemmas for 3-graphs.

1. Introduction

We consider combinatorial property testing, in the sense of Goldreich, Goldwasser, and Ron [9, 10] (see also Ron [14] for a recent survery). We address the problem of testing hypergraph properties; we in fact focus on testing induced subhypergraphs in 3-uniform hypergraphs. (For a recent result on hypergraph property testing, see Czumaj and Sohler [6], where k-colourability is proved to be testable.)

We start with some basic definitions. A k-uniform hypergraph H, k-graph for short, is a family of k-element sets. When k = 2, we speak of graphs, and when k = 3, we have triple systems. A k-graph property P is an infinite class of k-graphs closed under isomorphism. A k-graph H satisfies property P if H ∈ P. A k-graph H is said to be ζ-far from property P if every k-graph H̃ ∈ P with V (H̃) = V (H) differs from H in at least ζ|V (H)|^{k} k-tuples of vertices (i.e., the symmetric difference H △ H̃ has size at least ζ|V (H)|^{k}).

A ζ-test for property P is a randomized algorithm which, given as input a k-graph H and n = | ⋃ H|, is allowed to make queries whether any given k-tuple of vertices belongs to H or not, and distinguishes, with high probability, between the case that H satisfies P and the case that H is ζ-far from P. A property P is said to be testable if, for every ζ > 0, there exists a function f(ζ) and an ζ-test for P which makes a total of f(ζ) queries for any input k-graph. Note that, in particular, the number of queries does not depend on the order of the input k-graph. A ζ-test is

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

**School of Mathematics, Georgia Institute of Technology, Atlanta, GA, 30332, USA, and Department of Mathematics, University of Nevada, Reno, Reno, Nevada, 89557, USA. E-mail address: nagle@math.gatech.edu.

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

Collaboration supported by a CNPq/NSF cooperative grant.

said to be a one-sided test if when H satisfies property P, the test determines that this is the case with probability 1. A property P is said to be strongly-testable if for every ζ > 0, there exists a one sided ζ-test for P.

For a k-graph F, we let Forb_{ind}(n, F) be the property of all k-graphs on n vertices not containing a copy of F as an induced subhypergraph. Recently, Alon, Fischer, Krivelevich and Szegedy [2, 3] studied the graph properties Forb_{ind}(n, F) for arbitrary graphs F. Among other results, they proved that all graph properties of the type Forb_{ind}(n, F) are strongly-testable. A statement central to their main result was the following combinatorial theorem.

Theorem 1. For every ζ > 0 and every graph F, there exists c > 0 so that if a graph G on n > n_{0}(ζ, F) vertices is ζ-far from Forb_{ind}(n, F), then G must contain at least cn^{|V (F)|} copies of F as an induced subgraph.

Observe that Theorem 1 implies that Forb_{ind}(n, F) is a strongly-testable property; if f = |V (F)|, then the maximum number of queries required is O(f^{2}/c): we simply sample α/c random vertices from F, where α > 0 is some large enough constant, and check O(f^{2}/c) suitable adjacencies. This is a strong ζ-test: suppose a given graph G on n vertices contains no copy of F as an induced subgraph. Then, our test will certainly find no copy of F in G as an induced subgraph. Consequently, the test correctly decides with probability 1 that G ∈ Forb_{ind}(n, F). On the other hand, if G is ζ-far from Forb_{ind}(n, F), then, by Theorem 1, the graph G contains cn^{f} copies of F as an induced subgraph. This means that our randomized algorithm (which makes O(f^{2}/c) queries) is able to locate a copy of F with high probability.

The goal of this paper is to extend Theorem 1 to 3-graphs. Since the connection between testability and the combinatorial property illustrated in Theorem 1 remains unchanged from graphs to hypergraphs, we choose to present our work in a purely combinatorial language.

Theorem 2. For every ζ > 0 and 3-graph F, there exists c > 0 so that if a 3-graph G on n > n_{0}(ζ, F) vertices is ζ-far from Forb_{ind}(n, F), then G contains at least cn^{|V (F)|} copies of F as an induced subhypergraph.

We conjecture that Theorems 1 and 2 are true for general k-graphs.

Conjecture 3. For every ζ > 0 and k-graph F, there exists c > 0 so that if a k-graph G on n > n_{0}(ζ, F) vertices is ζ-far from Forb_{ind}(n, F), then G contains at least cn^{|V (F)|} copies of F as an induced subhypergraph.

In Sections 1.1 and 1.2 below, we discuss Conjecture 3 and some related problems.

1.1. On Conjecture 3: the Special Case F^{(k)} = K_{k+1}^{(k)}. The validity of Conjecture 3 in the

special case F^{(k)} = K_{k+1}^{(k)}, the complete k-graph on k + 1 vertices, has an interesting connection to the following well known and deep problem concerning arithmetic progressions.

Let r_{k}(n) be the maximum cardinality of a set of integers A ⊂ {1, …, n} which contains no arithmetic progressions of length k. A conjecture of Erdős and Turán from 1936 stated that r_{k}(n) = o(n). Roth [15] proved r_{3}(n) = o(n). In 1975, Szemerédi proved his celebrated result that r_{k}(n) = o(n), confirming the Erdős–Turán conjecture. Furstenberg [8] and, more recently, Gowers [11] have given alternative proofs. The sharpest result to date for k = 3 is due to Bougain [5].

In [16], Ruzsa and Szemerédi solved an extremal combinatorial problem yielding an alternative proof to Roth’s theorem [15]. In [7], the following extremal problem was considered. Let F_{1}^{(k+1)} be the (k+1)-graph consisting of two edges intersecting in k points. Let F_{2}^{(k+1)} be the (k+1)-graph with 2k +2 vertices {a_{1}, …, a_{k+1}, b_{1}, …, b_{k+1}} and all (k +1)-tuples of the form {a_{1}, …, a_{k+1}, b_{i}}\{a_{i}}, 1 ≤ i ≤ k + 1. Let ex(n, {F_{1}^{(k+1)}, F_{2}^{(k+1)}}) denote the maximum number of edges of any (k + 1)- graph H^{(k+1)} not containing F_{1}^{(k+1)} or F_{2}^{(k+1)} as a (not necessarily induced) subhypergraph. In [7], a constructive argument was given showing that

ex(n, {F_{1}^{(k+1)}, F_{2}^{(k+1)}}) ≥ r_{k+1}(n)n^{k−1}.  (1)

To verify Conjecture 3 for general k, even in the special case when F^{(k)} = K_{k+1}^{(k)}, will not be

easy. Indeed, we claim that if Conjecture 3 is proved for general k and F^{(k)} = K_{k+1}^{(k)}, then one may quickly deduce Szemerédi’s theorem r_{k}(n) = o(n).

Proof of Claim. Indeed, fix ζ > 0 and let H^{(k+1)} be a (k + 1)-graph on n points and ζn^{k} edges not containing F_{1}^{(k+1)} as a subhypergraph. We shall prove that H^{(k+1)} must contain F_{2}^{(k+1)} if n is large enough. Consequently, for n sufficiently large, we have

ex(n, {F_{1}^{(k+1)}, F_{2}^{(k+1)}}) < ζn^{k}.  (2)

Let

H^{(k)} = {K: |K| = k, K ⊂ E for some E ∈ H^{(k+1)}}

be the set of all k-tuples contained in some (k + 1)-tuple of H^{(k+1)}. Since H^{(k+1)} contains no copy of F_{1}^{(k+1)}, every k-tuple K ∈ H^{(k)} belongs to precisely one (k +1)-tuple H ∈ H^{(k+1)}. Consequently, H^{(k)} is ζ-far from being K_{k+1}^{(k)}-free.

Assuming Conjecture 3 (for F = K_{k+1}^{(k)}), we get that H^{(k)} contains

cn^{k+1} ≫ ζn^{k} = |H^{(k+1)}|

copies of K_{k+1}^{(k)}.

Let {a_{1}, …, a_{k+1}} span a copy of K_{k+1}^{(k)} in H^{(k)} for which {a_{1}, …, a_{k+1}} ∉ H^{(k+1)}. Clearly, each {a_{1}, …, a_{k+1}} \ {a_{i}}, 1 ≤ i ≤ k + 1, is an edge of H^{(k)}. Consequently, there exists b_{i} such that {a_{1}, …, a_{k+1}, b_{i}} \ {a_{i}} is an edge of H^{(k+1)}. Since |H_{1} ∩ H_{2}| < k for all distinct H_{1}, H_{2} ∈ H^{(k+1)}, these b_{i}, 1 ≤ i ≤ k + 1, have to be distinct. Consequently, H^{(k+1)} contains a copy of F_{2}^{(k+1)} as a subhypergraph. □

Owing to (1) and (2), we see r_{k+1}(n)n^{k−1} ≤ ex(n, {F_{1}^{(k+1)}, F_{2}^{(k+1)}}) < ζn^{k}. Consequently, r_{k+1}(n) < ζn^{k} for large enough n.

1.2. On the Non-induced Case. Note that Conjecture 3 is formulated for classes of k-graphs not containing F as an induced subhypergraph (a feature of no importance when F is a clique). One may also consider the class Forb(n, F) of all k-graphs on n vertices which do not contain a copy of F as a (not necessarily induced) subhypergraph. We state the following analogue to Conjecture 3.

Conjecture 4. For every ζ > 0 and k-graph F, there exists c > 0 so that if a k-graph G on n > n_{0}(ζ, F) vertices is ζ-far from Forb(n, F), then G contains at least cn^{|V (F)|} copies of F as a subhypergraph.

For k = 2 and k = 3, Conjecture 4 is true. For k = 2, Conjecture 4 follows by a standard application of Szemerédi’s regularity lemma. For k = 3, the result follows from results of [7] and [12]. Recently, Conjecture 4 was proved for k = 4 and F = K_{5}^{(4)} (see [13]).

Since Conjecture 4 is true for k = 2, we may define the following (finite) function C(ζ, F) = C_{2}(ζ, F). Recall that the quantification of Conjecture 4 is of the form “(∀ζ, F)(∃c, n_{0})”. For given F and ζ, let C(ζ, F) be the supremum of all c for which the implication in Conjecture 4 holds (for the given value of ζ and the given graph F) for some large enough n_{0}. The question of how C(ζ, F) behaves for a fixed F as a function of ζ has been addressed recently by Alon [4], who proved the following theorem.

Theorem 5. For a fixed graph F, the function C(ζ, F) is polynomial in ζ if and only if F is bipartite.

Preliminary results suggest that Theorem 5 extends to k-graphs. Indeed, if F is a k-partite k-graph with partition classes of size t_{1}, …, t_{k}, then, for a constant c_{1} = c_{1}(F) depending only on F, we have

C(ζ, F) ≤ (k/ζ)^{c_{1}t_{1}...t_{k}}.

On the other hand, there exist non k-partite F (e.g., F = K_{k+1}^{(k)}), for which there is a constant c_{2} = c_{2}(F) depending only on F, so that

C(ζ, F) ≥ ζ^{c_{2} log 1/ζ}.

2. Definitions and Notation

2.1. Graph Concepts. We begin with some basic notation. As is customary, if X is a set, we write [X]^{k} for the set of k-element subsets of X. For a graph P and two disjoint sets X, Y ⊂ V (P), we set P [X, Y] = {{x, y} ∈ P: x ∈ X, y ∈ Y }. We define the density d_{P} (X, Y) of P with respect to X and Y ≠ ∅ by d_{P} (X, Y) = |P [X, Y]|/|X||Y |.

For a graph P, we let K_{3}(P) be the set of vertex sets of triangles in P. Thus, {x, y, z} ∈ K_{3}(P) if and only if x, y, and z are mutually adjacent in P.

A graph P with a fixed k-partition V_{1} ∪ ⋯ ∪ V_{k} is referred to as a k-partite cylinder. We write P = ⋃_{1≤i<j≤k} P^{ij}, where P^{ij} = P [V_{i}, V_{j}], 1 ≤ i < j ≤ k. For B ∈ [k]^{3}, we sometimes write P (B) to denote the subgraph of P induced on the vertex set ⋃_{i∈B} V_{i}. When k = 3, we call P a triad.

We proceed with the following definitions. Definition 6 ((α, ε)-regularity). For α and ε > 0 reals, we say that a bipartite graph P with vertex bipartition X ∪ Y is (α, ε)-regular if α(1 − ε) < d_{P} (X_{0}, Y_{0}) < α(1 + ε) for every pair of subsets X_{0} ⊆ X and Y_{0} ⊆ Y with |X_{0}| > ε|X| and |Y_{0}| > ε|Y |. Definition 7 ((ℓ, ε, k)-cylinder). For an integer ℓ and a real ε > 0, we call a k-partite cylinder P = ⋃_{1≤i<j≤k} P^{ij} an (ℓ, ε, k)-cylinder if each bipartite graph P^{ij}, 1 ≤ i < j ≤ k, is (1/ℓ, ε)-regular.

Note that when a triad P is an (ℓ, ε, 3)-cylinder with 3-partition satisfying |V_{1}| = |V_{2}| = |V_{3}| = n, the number |K_{3}(P)| of triangles in P is about n^{3}/ℓ^{3}.

2.2. Hypergraph Concepts. 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 set H(B) to be the set of triples of H induced on the vertex set ⋃_{i∈B} V_{i}.

Let a 3-uniform hypergraph H and a graph P be given so that V (H) = V (P). We say that P underlies H if H ⊆ K_{3}(P). In the remainder of this paper, we only consider hypergraphs H together with graphs P that underly them. We continue with the following technical definitions.

Definition 8 (Density of \overrightarrow{Q}; density of a triad). Let H be a 3-partite 3-cylinder with underlying 3-partite cylinder P = P^{12} ∪ P^{23} ∪ P^{13}. Let \overrightarrow{Q} = (Q(1), …, Q(r)) be an r-tuple of 3-partite cylinders Q(s) = Q^{12}(s) ∪ Q^{23}(s) ∪ Q^{13}(s) satisfying that, for every s ∈ {1, 2, …, r} and for each \{i, j\}, 1 ≤ i < j ≤ 3, we have Q^{ij}(s) ⊆ P^{ij}. Let K_{3}(\overrightarrow{Q}) = ⋃_{s=1}^{r} K_{3}(Q(s)). We define the density d_{H}(\overrightarrow{Q}) of \overrightarrow{Q} as

d_{H}(\overrightarrow{Q}) = \begin{cases}\frac{|H ∩ K_{3}(\overrightarrow{Q})|}{|K_{3}(\overrightarrow{Q})|} & if |K_{3}(\overrightarrow{Q})| > 0, \\ 0 & otherwise. \end{cases}  (3)

If r = 1, we have the notion of the density d_{H}(P) of a (single) triad P with respect to H. Definition 9 ((α, δ, r)-regularity). Let H be a 3-partite 3-cylinder with underlying 3-partite cylinder P = P^{12}∪P^{23}∪P^{13}. Let a positive integer r and a real δ > 0 be given. We say that the 3-cylinder H is (α, δ, r)-regular with respect to P if for any r-tuple of 3-partite cylinders \overrightarrow{Q} = (Q(1), …, Q(r)) as above, if |K_{3}(\overrightarrow{Q})| = | ⋃_{s=1}^{r} K_{3}(Q(s))| > δ|K_{3}(P)|, then |d_{H}(\overrightarrow{Q}) − α| < δ.

We say H is (δ, r)-regular with respect to P if it is (α, δ, r)-regular for some α. If the regularity condition fails to be satisfied for every α, we say that H is (δ, r)-irregular with respect to P.

2.3. A Hypergraph Regularity Lemma. In this section, we state the a Hypergraph Regularity Lemma, due to Frankl and Rödl [7]. First, we state a number of supporting definitions. Definition 10 ((ℓ, t, γ, ε)-partition). Let V be a set with |V | = N. An (ℓ, t, γ, ε)- partition P of [V]^{2} is an (auxiliary) partition V = V_{1} ∪ ⋯ ∪ V_{t} of V, together with a system of edge-disjoint bipartite graphs {P_{α}^{ij}: 1 ≤ i < j ≤ t, 0 ≤ α ≤ ℓ}, such that

(i) V = ⋃_{1≤i≤t} V_{i} is a t-equitable partition, i.e., we have ⌊N/t⌋ ≤ |V_{i}| ≤ ⌈N/t⌉ for all 1 ≤ i ≤ t, (ii) ⋃_{α=0}^{ℓ} P_{α}^{ij} = K(V_{i}, V_{j}) for all i, j, 1 ≤ i < j ≤ t, where K(V_{i}, V_{j}) denotes the complete

bipartite graph with vertex bipartition V_{i} ∪ V_{j}, (iii) for all but γ\binom{t}{2}ℓ indices 1 ≤ i < j ≤ t, 1 ≤ α ≤ ℓ, the graph P_{α}^{ij} is (ℓ^{−1}, ε)-regular.

If we do not have or do not care about (iii), and, moreover, P_{0}^{ij} = ∅ for all 1 ≤ i < j ≤ t, we say that P above is an (ℓ, t)-partition of [V]^{2}. For an (ℓ, t)-partition P = {P_{α}^{ij}: 1 ≤ i < j ≤ t, 0 ≤ α ≤ ℓ} of [V]^{2}, the set of triads generated by P is

Triad(P) = {P = P_{α}^{ij} ∪ P_{β}^{jk} ∪ P_{γ}^{ik}: 1 ≤ i < j < k ≤ t, 0 ≤ α, β, γ ≤ ℓ} .

Definition 11 ((δ, r)-regular partition). Let H be a 3-uniform hypergraph with vertex set V where |V | = N. We say that an (ℓ, t, γ, ε)-partition P of [V]^{2} is (δ, r)-regular for H if

∑ {|K_{3}(P)|: P ∈ Triad(P) is (δ, r)-irregular} < δN^{3}.

Theorem 12 (Hypergraph Regularity Lemma [7]). For every δ and γ with 0 < γ ≤ 2δ^{4}, for all integers t_{0} and ℓ_{0} and for all integer-valued functions r(t, ℓ) and all functions ε(ℓ) > 0, there exist T_{0}, L_{0}, and N_{0} such that any 3-uniform hypergraph H ⊆ [N]^{3}, N ≥ N_{0}, admits a (δ, r(t, ℓ))-regular (ℓ, t, γ, ε(ℓ))-partition for some t and ℓ satisfying t_{0} ≤ t ≤ T_{0} and ℓ_{0} ≤ ℓ ≤ L_{0}.

2.4. The Counting Lemma. In this section, we present the Counting Lemma, Lemma 14 below. We begin by describing the context in which this lemma applies. Setup 13. Fix integers f, ℓ, and r. Let δ and ε > 0 be given, together with an indexed family {α_{B}: B ∈ [f]^{3}} of positive reals. We consider the following conditions on a given hypergraph H and underlying graph P.

(i) H is an f-partite 3-cylinder with f-partition V_{1} ∪ ⋯ ∪ V_{f}, where |V_{1}| = ⋯ = |V_{f}| = m.

(ii) P = ⋃_{1≤i<j≤f} P^{ij} is an underlying (ℓ, ε, f)-cylinder of H.

(iii) For all B ∈ [f]^{3}, the 3-partite 3-cylinder H(B) is (α_{B}, δ, r)-regular with respect to the triad P (B) (cf. Definition 9).

Finally, suppose F is a 3-uniform hypergraph with vertex set V (F) = [f]. For B ∈ [f]^{3}, we let ρ_{B} = α_{B} if B ∈ F, and we let ρ_{B} = 1 − α_{B} if B ∉ F. In the main lemma of this section, we are concerned with the number of induced, transversal copies of F in H, by which we mean the number of functions ι: V (F) = [f] ↪ V (H) with ι(i) ∈ V_{i} for all 1 ≤ i ≤ f that induces an isomorphism of F onto the image H[im ι] = H ∩ [im ι]^{3} of ι. We denote the set of such ι by F_{ind}(H; V_{1}, …, V_{f}).

Lemma 14 (Counting Lemma [12]). Let f ≥ 3 be a fixed integer. For all constants α and β > 0, there exists δ > 0 for which the following holds. For all integers ℓ, there exist an integer r and a real ε > 0 so that whenever an f-partite 3-cylinder H with an underlying cylinder P satisfy the conditions of Setup 13 with constants f, δ, l, r and ε and an indexed family {α_{B}: B ∈ [f]^{3}} of reals, with α ≤ α_{B} ≤ 1 − α for all B ∈ [f]^{3}, we have

\frac{Π_{B∈[f]^{3}}ρ_{B}}{ℓ^{\binom{f}{2}}} m^{f}(1 − β) ≤ |F_{ind}(H; V_{1}, …, V_{f})| ≤ \frac{Π_{B∈[f]^{3}}ρ_{B}}{ℓ^{\binom{f}{2}}} m^{f}(1 + β)

for any triple system F on [f].

3. The Perfect Reduction Lemma

It is well-known that in the regularity lemma of Szemerédi, one cannot avoid the existence of irregular pairs [1]. It proved to be vital for the proof of Theorem 1 to develop a version of the regularity lemma that, within large subsets of a Szemerédi partition, admits no irregular pairs. Here, we need a similar version of Theorem 12 that admits no irregular triads.

3.1. Preliminary Definitions. In this section, we consider the following setup. Setup 15. Let H be a 3-uniform hypergraph on n vertices. Let V (H) = V_{1} ∪ ⋯ ∪ V_{t} be a t-equitable partition, that is, for all 1 ≤ i ≤ t, suppose we have ⌊n/t⌋ ≤ |V_{i}| ≤ ⌈n/t⌉. Let P = {P_{α}^{ij}: 1 ≤ i < j ≤ t, 1 ≤ α ≤ ℓ} be an (ℓ, t)-partition of [V (H)]^{2}.

Observe that α ≥ 1 in Setup 15, since in (ℓ, t)-partitions we have P_{0}^{ij} = ∅. Definition 16 ((δ_{0}, τ)-reduction). Let H and P as in Setup 15 be given. For δ_{0}, τ > 0, we say the graph Q is a (δ_{0}, τ)-reduction of P if the following hold:

1. Q has a t-partition V (Q) = ⋃_{1≤i≤t} W_{i}, where W_{i} ⊆ V_{i}, 1 ≤ i ≤ t, and |W_{1}| = ⋯ = |W_{t}| ≥

τn.

2. For all but δ_{0}\binom{t}{3}ℓ^{3} indices 1 ≤ i < j < k ≤ t, 1 ≤ α, β, γ ≤ ℓ, the triads P = P_{α}^{ij} ∪ P_{β}^{jk} ∪ P_{γ}^{ik}

and Q_{P} = Q ∩ P satisfy |d_{H}(Q_{P}) − d_{H}(P)| < δ_{0}.

Definition 17 ((δ, r, ε, ℓ′)-perfect reduction). Let H and P as in Setup 15 be given. Let a graph Q be a (δ_{0}, τ)-reduction of P. For reals δ and ε > 0 and for integers r and ℓ′, we say that Q is a (δ, r, ε, ℓ′)-perfect reduction of P if Q satisfies the following conditions:

1. For each 1 ≤ i < j ≤ t, 1 ≤ α ≤ ℓ, the graph Q ∩ P_{α}^{ij} is ((ℓ′ℓ)^{−1}, ε)-regular.

2. For each 1 ≤ i < j < k ≤ t, 1 ≤ α, β, γ ≤ ℓ, the triad Q∩(P_{α}^{ij} ∪ P_{β}^{jk} ∪ P_{γ}^{ik}) is (δ, r)-regular.

We are now able to state the main lemma in this section.

Lemma 18 (Perfect Reduction Lemma). For all integers t_{0}, for all δ_{0} > 0, for all functions δ(ℓ), ε(ℓ), and r(ℓ), there exist τ > 0 and integers T_{0}, L_{0}, L′_{0} and N_{0} for which the following holds: for any H on n ≥ N_{0} vertices, there exist integers t_{0} ≤ t ≤ T_{0}, 1 ≤ ℓ ≤ L_{0}, 1 ≤ ℓ′ ≤ L′_{0}, such that

(a) there exists an (ℓ, t)-partition P = {P_{α}^{ij}: 1 ≤ i < j ≤ t, 1 ≤ α ≤ ℓ}, as in Setup 15,

(b) there exists a (δ_{0}, τ)-reduction Q of P (see Definition 16 ) which is a (δ(ℓ), r(ℓ′ℓ), ε(ℓ′ℓ), ℓ′)- perfect reduction of P (see Definition 17 ).

4. Sketch of the Proof of Theorem 2

4.1. Definition of the Constants. Theorem 2 asserts that for any triple system F and any ζ > 0, there is a constant c > 0 for which we have |F_{ind}(H)| ≥ cn^{|V (F)|}, whenever H is ζ-far from Forb_{ind}(n, F). Thus, suppose we are given F and ζ > 0. We let f = |V (F)|. All the constants below are defined in terms of f and ζ.

In fact, for simplicity, and also because we do not care about the exact value of the constants (and we do not know their best possible values), we only give the ‘hierarchy’ governing their sizes. Roughly speaking, in what follows, when we already have B and we say ‘A ≪ B’, we mean that A should be small enough with respect to B.

We start by letting α_{0} ≪ ζ. We apply Lemma 14, the Counting Lemma, with f = |V (F)|, α = α_{0}, and β = 1/2. Lemma 14 then gives us a constant δ_{CL} = δ_{CL}(f, α_{0}, 1/2) > 0. Given that the quantification in Lemma 14 is “(∀f, α, β)(∃δ)(∀ℓ)(∃r, ε)”, that lemma gives us functions r^{f,α,β,δ}(ℓ) and ε^{f,α,β,δ}(ℓ). We let r_{CL}(ℓ) = r_{CL}^{f,α_{0},1/2,δ_{CL}}(ℓ) and ε_{CL}(ℓ) = ε_{CL}^{f,α_{0},1/2,δ_{CL}}(ℓ).

One part of the proof we sketch below is based on a lemma, the statement of which is implicit in Section 4.2.2: roughly speaking, this lemma says that there exists a real number

τ′ > 0  (4)

and there exist integers

K_{1} = K_{1}(f, ζ) and K_{2} = K_{2}(f, ζ)  (5)

for which one may produce the setup described in (S1)–(S3) and (P4)–(P7) (see Section 4.2.2). Now, once we have the constants K_{1} and K_{2} as in (5), we may complete the definition of our constants.

We now invoke Lemma 18, the Perfect Reduction Lemma, with constants t_{0} ≫ 1/ζ and δ_{0} ≪ ζ. We let the functions δ(ℓ), ε(ℓ), and r(ℓ) in the statement of that lemma be δ(ℓ) = δ_{CL}/K_{1}^{3}K_{2}^{3}, ε(ℓ) = ε_{CL}(ℓ), and r(ℓ) = r_{CL}(ℓ). Lemma 18 then gives us a real constant τ > 0 and integers T_{0}, L_{0}, L′_{0} and N_{0}.

We remark in passing that τ′ in (4) may be taken to be τ/K_{1}. In fact, K_{1} and K_{2} in (5) arise from an application of a certain variant of Theorem 12 (see Nagle and Rödl [12]): roughly speaking, K_{1} is an upper bound for the number of parts into which we split the vertex set of a given hypergraph and K_{2} is an upper bound for the number of parts into which we split certain bipartite graphs.

Finally, we define the constant c = c(f, ζ) > 0 by putting

c = \frac{α\binom{f}{3}_{0}(τ′)^{f}}{2(L_{0}L′_{0}K_{2})^{\binom{f}{2}}} .

Claim 19. The constant c = c(f, ζ) > 0 defined above will do in Theorem 2.

4.2. Proof of Claim 19. We split the proof into Steps I to IV. Suppose we are given a hypergraph H on V = ⋃ H as in the statement of the theorem.

4.2.1. Step I. We first apply Lemma 18, the Perfect Reduction Lemma, to obtain (a) an (ℓ, t)-partition P of [V]^{2} on V = ⋃_{1≤i≤t} V_{i},

(b) a (δ(ℓ), r(ℓℓ′), ε(ℓℓ′), ℓ′)-perfect (δ, τ)-reduction Q of P, where t_{0} ≤ t ≤ T_{0}, 1 ≤ ℓ ≤ L_{0}, and 1 ≤ ℓ′ ≤ L′_{0}.

4.2.2. Step II. Applying a variant of Theorem 12 (see Nagle and Rödl [12]) and several further combinatorial arguments (Turán type arguments and Ramsey type arguments), we obtain the setup we shall now describe. The objects that constitute our setup are described in (S1)–(S3) below. (S1) For every 1 ≤ i ≤ t, we have a partition W′_{i} = ⋃_{1≤i′≤f} A_{ii′} of a subset W′_{i} of W_{i} (see Definition 16). Moreover, we suppose that the V_{i} ⊃ W′_{i} are totally ordered in such a way that A_{i1} < ⋯ < A_{if} for all i.

(S2) For every 1 ≤ i < j ≤ t, 1 ≤ i′, j′ ≤ f, and 1 ≤ α ≤ ℓ, we have a subgraph ^{∗}Q_{α}^{ij}(i′, j′) of the bipartite graph Q_{α}^{ij}(i′, j′) = Q_{α}^{ij} ∩ K(A_{ii′}, A_{jj′}) = Q ∩ P_{α}^{ij} ∩ K(A_{ii′}, A_{jj′}). Moreover, for every 1 ≤ i ≤ t and 1 ≤ i′, i′′ ≤ f with i′ ≠ i′′, we have a subgraph Q(i; i′, i′′) of K(A_{ii′}, A_{ii′′}). (S3) We have functions χ_{1}^{∗}, χ_{2}^{∗}, and χ_{3}^{∗} with domains and codomains as follows:

χ_{1}^{∗}: [t] → {±1}, χ_{2}^{∗}: [t] × [t] \ Δ → {±1}^{I_{2}},  (6)

where Δ = {(i, i): 1 ≤ i ≤ t} and I_{2} = [ℓ] × [ℓ], and

χ_{3}^{∗}: [t]^{3} → {0, ±1}^{I_{3}},  (7)

where I_{3} = [ℓ] × [ℓ] × [ℓ].

The various objects in (S1)–(S3) satisfy the properties (P4)–(P7) given below. (P4) We have |A_{ii′}| = m for all 1 ≤ i ≤ t, 1 ≤ i′ ≤ f, where m ≥ τ′n (see (4)).

(P5) All ^{∗}Q_{α}^{ij}(i′, j′) (1 ≤ i < j ≤ t, 1 ≤ i′, j′ ≤ f, 1 ≤ α ≤ ℓ) and all Q(i; i′, i′′) (1 ≤ i ≤ t, 1 ≤ i′, i′′ ≤ f, i′ ≠ i′′) are (1/ℓℓ′k_{2}, ε_{2}(ℓℓ′k_{2}))-regular for some k_{2} ≤ K_{2} = K_{2}(f, ζ). (P6) We have the following regularity conditions for the triads defined by the bipartite graphs in (S2).

(i) For any 1 ≤ i ≤ t and 1 ≤ i′, i′′, i′′′ ≤ f, set Q^{i}(i′, i′′, i′′′) = Q(i; i′, i′′) ∪ Q(i; i′′, i′′′) ∪ Q(i; i′, i′′′). Then all the triads Q^{i}(i′, i′′, i′′′) are (δ_{CL}, r_{CL}(ℓℓ′k_{2}))-regular.

(ii) For any 1 ≤ i < j ≤ t, 1 ≤ i′, i′′, j′ ≤ f with i′ ≠ i′′, and any 1 ≤ α, β ≤ ℓ, set Q_{αβ}^{ij}(i′, i′′, j′) = ^{∗}Q_{α}^{ij}(i′, j′) ∪^{∗}Q_{β}^{ij}(i′′, j′) ∪ Q(i; i′, i′′). Then all the triads Q_{αβ}^{ij}(i′, i′′, j′) are (δ_{CL}, r_{CL}(ℓℓ′k_{2}))-regular.

(iii) For any 1 ≤ i < j < k ≤ t, 1 ≤ i′, j′, k′ ≤ f, and any 1 ≤ α, β, γ ≤ ℓ, set Q_{αβγ}^{ijk}(i′, j′, k′) = ∗Q_{α}^{ij}(i′, j′) ∪^{∗}Q_{β}^{jk}(j′, k′) ∪^{∗}Q_{γ}^{ik}(i′, k′). Then all the triads Q_{αβγ}^{ijk}(i′, j′, k′) are (μ′, r_{CL}(ℓℓ′k_{2}))- regular, where μ′ = K_{1}^{3}K_{2}^{3}δ(ℓ) = δ_{CL}.

(P7) The triads defined in (P6) satisfy the ‘density-coherence’ properties given below.

(i) For any 1 ≤ i ≤ t, the following holds.

(a) If χ_{1}^{∗}(i) = −1, then d_{H}(Q^{i}(i′, i′′, i′′′)) < 1/2 for all 1 ≤ i′ < i′′ < i′′′ ≤ f.

(b) If χ_{1}^{∗}(i) = 1, then d_{H}(Q^{i}(i′, i′′, i′′′)) ≥ 1/2 for all 1 ≤ i′ < i′′ < i′′′ ≤ f.

(ii) For any 1 ≤ i, j ≤ t with i ≠ j and any 1 ≤ α, β ≤ ℓ, the following holds.

(a) If (χ_{2}^{∗}(i, j))(α, β) = −1, then d_{H}(Q_{αβ}^{ij}(i′, i′′, j′)) < 1/2 for all 1 ≤ i′ < i′′ ≤ f and for

all 1 ≤ j′ ≤ f.

(b) If (χ_{2}^{∗}(i, j))(α, β) = 1, then d_{H}(Q_{αβ}^{ij}(i′, i′′, j′)) ≥ 1/2 for all 1 ≤ i′ < i′′ ≤ f and for

all 1 ≤ j′ ≤ f.

(iii) For any 1 ≤ i < j < k ≤ t and any 1 ≤ α, β, γ ≤ ℓ, the following holds. (a) If (χ_{3}^{∗}({i, j, k}))(α, β, γ) = −1, then d_{H}(Q_{αβγ}^{ijk}(i′, j′, k′)) < α_{0} for all 1 ≤ i′, j′, k′ ≤ f.

(b) If (χ_{3}^{∗}({i, j, k}))(α, β, γ) = 0, then α_{0} ≤ d_{H}(Q_{αβγ}^{ijk}(i′, j′, k′)) ≤ 1 − α_{0} for all 1 ≤

i′, j′, k′ ≤ f.

(c) If (χ_{3}^{∗}({i, j, k}))(α, β, γ) = 1, then d_{H}(Q_{αβγ}^{ijk}(i′, j′, k′)) > 1 − α_{0} for all 1 ≤ i′, j′, k′ ≤ f.

4.2.3. Step III. Based on the functions χ_{1}^{∗}, χ_{2}^{∗}, and χ_{3}^{∗} from (S3), we define a ‘perturbation’ of H. Using the main hypothesis on H, namely, that any small perturbation of H does not destroy all the induced copies of F present in H, we deduce that H′ contains at least one induced copy of F.

Let us define the hypergraph H′. We shall have H′ ⊂ [V]^{3}, where V = ⋃_{1≤i≤t} V_{i}. Let

H′_{tr} = {E ∈ H′: |E ∩ V_{i}| ≤ 1 (1 ≤ i ≤ t)}  (8)

be the subhypergraph of H′ formed by the ‘transversal’ triples in H′. Recall that we have the (ℓ, t)-partition P of [V]^{2}. We thus have the family of triads Triad(P) given by P. Now, the family of triple systems K_{3}(P) (P ∈ Triad(P)) partitions the family {E ∈ [V]^{3} : |E ∩V_{i}| ≤ 1 (1 ≤ i ≤ t)} of the transversal triples in [V]^{3}. Therefore, to define H′_{tr}, we may define H′_{tr} ∩ K_{3}(P) independently for all P ∈ Triad(P). For each P ∈ Triad(P), if P = P_{αβγ}^{ijk} = P_{α}^{ij} ∪ P_{β}^{jk} ∪ P_{γ}^{ik}, we let

H′_{tr} ∩ K(P) = \begin{cases}∅ & if (χ_{3}^{∗}(\{i, j, k\}))(α, β, γ) = −1 \\ H ∩ K_{3}(P) & if (χ_{3}^{∗}(\{i, j, k\}))(α, β, γ) = 0 \\ K_{3}(P) & if (χ_{3}^{∗}(\{i, j, k\}))(α, β, γ) = 1. \end{cases}  (9)

We now proceed to define H′ \ H′_{tr}. We have the following natural partition of the non-transversal triples in [V]^{3}:

{E ∈ [V]^{3} : |E ∩ V_{i}| ≥ 2 some i} = ⋃_{1≤i≤t}[V_{i}]^{3} ∪ ⋃_{i,j,α,β} K_{3}(i, j; α, β),

where the last union is over all 1 ≤ i, j ≤ t with i ≠ j and 1 ≤ α, β ≤ ℓ, and

K_{3}(i, j; α, β) = {{u, v, w} ∈ [V_{i} ∪ V_{j}]^{3} : u, v ∈ V_{i}, u < v, w ∈ V_{j}, {u, w} ∈ P_{α}^{ij}, {v, w} ∈ P_{β}^{ij}}.

To define H′ \H′_{tr}, we may therefore define (H′ \H′_{tr})∩[V_{i}]^{3} (1 ≤ i ≤ t) and (H′ \H′_{tr})∩K_{3}(i, j; α, β) (1 ≤ i, j ≤ t, i ≠ j, 1 ≤ α, β ≤ ℓ) independently. Fix 1 ≤ i ≤ t. We let

(H′ \ H′_{tr}) ∩ [V_{i}]^{3} = \begin{cases}∅ & if χ_{1}^{∗}(i) = −1 \\ [V_{i}]^{3} & if χ_{1}^{∗}(i) = 1. \end{cases}  (10)

Now fix 1 ≤ i, j ≤ t with i ≠ j and 1 ≤ α, β ≤ ℓ. We let

(H′ \ H′_{tr}) ∩ K_{3}(i, j; α, β) = \begin{cases}∅ & if (χ_{2}^{∗}(i, j))(α, β) = −1 \\ K_{3}(i, j; α, β) & if (χ_{2}^{∗}(i, j))(α, β) = 1. \end{cases}  (11)

A crucial property about H′ defined above is given in Claim 20 below.

Claim 20. The hypergraphs H′ and H are ζ-close. Therefore, H′ contains an induced copy of F.

4.2.4. Step IV. We now fix an induced embedding ι: ⋃ F ↪ ⋃ H of F into H. Using this embedding, one may obtain a k-partite 3-cylinder H^{∗} ⊂ H with underlying 2-cylinder P to which one may apply Lemma 14, the Counting Lemma.

To simplify the notation, we may and shall assume that the image im ι of ι meets only V_{1}, …, V_{g}. Let h_{i} = | im ι ∩ V_{i}| (1 ≤ i ≤ g). One may then check that H^{∗} and P may be obtained as described in Claim 21 below.

Claim 21. There is a choice of indices 1 ≤ α(i, i′, j, j′) ≤ ℓ (1 ≤ i < j ≤ g, 1 ≤ i′, j′ ≤ f) for which the following holds. Consider the vertex sets A_{ii′} (1 ≤ i ≤ g, 1 ≤ i′ ≤ h_{i}), and consider the k-partite cylinder P on the partition ⋃_{i,i′} A_{ii′}, where the union is over all 1 ≤ i ≤ g and 1 ≤ i′ ≤ h_{i}, given by the following bipartite graphs: (i) for each 1 ≤ i ≤ g and each 1 ≤ i′ < i′′ ≤ h_{i}, take Q(i; i′, i′′) and (ii) for each 1 ≤ i < j ≤ g and for each 1 ≤ i′ ≤ h_{i}, 1 ≤ j′ ≤ h_{j}, take ^{∗}Q_{α(i,i′,j,j′)}^{ij}(i′, j′). Let H^{∗} ⊂ H be the subhypergraph of H formed by the triples in H ∩ K_{3}(P). Then the hypotheses in Lemma 14 apply, and, consequently, |F_{ind}(H)| ≥ cn^{k}.

Sketch of Proof. Suppose im ι ∩ V_{i} = {x_{i1}, …, x_{ih_{i}}} (1 ≤ i ≤ g), where x_{i1} < ⋯ < x_{ih_{i}} (recall that we suppose that the V_{i} are totally ordered; see (S1)). Fix 1 ≤ i < j ≤ g and 1 ≤ i′ ≤ h_{i} and 1 ≤ j′ ≤ h_{j}. We have {x_{ii′}, y_{jj′}} ∈ P_{α}^{ij} for some 1 ≤ α ≤ ℓ. We let α(i, i′, j, j′) = α, and assert that this choice for α(i, i′, j, j′) (1 ≤ i < j ≤ g, 1 ≤ i′ ≤ h_{i}, 1 ≤ j′ ≤ h_{j}) will do in Claim 21. To verify our assertion, it suffices to use the properties listed in (P7); we omit the details. □

References

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

2. N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Efficient testing of large graphs (extended abstract), 40th Annual Symposium on Foundations of Computer Science (New York City, NY), IEEE Comput. Soc. Press, 1999, pp. 656–666.

3. , Efficient testing of large graphs, Combinatorica 20 (2000), no. 4, 451–476.

4. Noga Alon, Testing subgraphs in large graphs, Proceedings of the 42nd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2001), 2001, pp. 434–439.

5. J. Bourgain, On triples in arithmetic progression, Geom. Funct. Anal. 9 (1999), no. 5, 968–984. MR 2001h:11132 6. A. Czumaj and C. Sohler, Testing hypergraph coloring, Proc. of ICALP, 2001, pp. 493–505.

7. P. Frankl and V. Rödl, Extremal problems on set systems, Random Structures and Algorithms (2002), to appear.

8. Harry Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Analyse Math. 31 (1977), 204–256. MR 58 #16583

9. Oded Goldreich, Shafi Goldwasser, and Dana Ron, Property testing and its connection to learning and approximation, 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, pp. 339–348. MR 1 450 632

10. , Property testing and its connection to learning and approximation, Journal of the Association for Computing Machinery 45 (1998), no. 4, 653–750. MR 1 675 099

11. W. T. Gowers, A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), no. 3, 465–588. MR 1 844 079

12. Brendan Nagle and Vojtěch Rödl, Regularity properties for triple systems, submitted, 2000.

13. Vojtěch Rödl and Jozef Skokan, Uniformity of set systems, manuscript, 2001.

14. Dana Ron, Property testing, Handbook of randomized algorithms (P. M. Pardalos, S. Rajasekaran, J. Reif, and J. D. P. Rolim, eds.), Kluwer Academic Publishers, 2001, to appear.

15. K. F. Roth, On certain sets of integers, Journal of the London Mathematical Society 28 (1953), 104–109.

16. I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, Combinatorics (Proceedings of the Fifth Hungarian Colloquium, Keszthely, 1976), Vol. II (Amsterdam–New York), Colloq. Math. Soc. János Bolyai, no. 18, North-Holland, 1978, pp. 939–945.