Szemerédi’s Regularity Lemma for Sparse Graphs

Y. Kohayakawa^{⋆}

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

Abstract. A remarkable lemma of Szemerédi asserts that, very roughly speaking, any dense graph can be decomposed into a bounded number of pseudorandom bipartite graphs. This far-reaching result has proved to play a central rôle in many areas of combinatorics, both ‘pure’ and ‘algorithmic.’ The quest for an equally powerful variant of this lemma for sparse graphs has not yet been successful, but some progress has been achieved recently. The aim of this note is to report on the successes so far.

1 Introduction

Szemerédi’s celebrated proof [39] of the conjecture of Erdős and Turán [10] on arithmetic progressions in dense subsets of integers is certainly a masterpiece of modern combinatorics. An auxiliary lemma in that work, which has become known in its full generality [40] as Szemerédi’s regularity lemma, has turned out to be a powerful and widely applicable combinatorial tool. For an authoritative survey on this subject, the reader is referred to the recent paper of Komlós and Simonovits [29]. For the algorithmic aspects of this lemma, the reader is referred to the papers of Alon, Duke, Lefmann, Rödl, and Yuster [1] and Duke, Lefmann, and Rödl [8].

Very roughly speaking, the lemma of Szemerédi says that any graph can be decomposed into a bounded number of pseudorandom bipartite graphs. Since pseudorandom graphs have a predictable structure, the regularity lemma is a powerful tool for introducing ‘order’ where none is visible at first. The notion of pseudorandomness that appears in the lemma has to do with distribution of edges. In fact, the bipartite graphs that are used to decompose a given graph are guaranteed to have its edges uniformly distributed with an error term that is quadratic in the number of vertices of the graph, but with an arbitrarily small multiplicative constant. Therefore, we have a handle on the edge distribution of the original graph as long as it has a quadratic number of edges. If the original graph has a subquadratic number of edges, however, Szemerédi’s lemma will tell us nothing. In this note, we focus our attention on certain closely related variants of the regularity lemma that can handle this ‘sparse’ case with some success.

⋆ Partially supported by FAPESP (Proc. 96/4505–2) and CNPq (Proc. 300334/93–1 and ProTeM-CC-II Project ProComb).

An unpublished manuscript of the present author [23] dealt with one such variant. As mentioned there, these variants were also independently discovered by Professor V. Rödl.

These sparse versions of the regularity lemma have already been used for studying extremal properties of graphs [19, 20], of random graphs [21, 22, 24, 26], and of random sets of integers [27], and also for developing an optimal algorithm for checking pseudorandomness of graphs [28]. In the sequel, we shall discuss these applications and we shall also state a few related problems.

Before we close the introduction, let us mention that, since the paper of Komlós and Simonovits [29] went to press, another nice application of the regularity lemma, together with a new variant, has appeared. Frieze and Kannan [14] have approached some MAXSNP-hard problems by means of the regularity lemma. Their method gives polynomial time approximation schemes for many graph partitioning problems if the instances are restricted to dense ones. Their paper thus provides yet another motivation for investigating sparse versions of the fascinating lemma of Szemerédi.

This note is organised as follows. The statement of a version of the regularity lemma for sparse graphs, Theorem 1, is given in Section 2 below. A variant of Theorem 1 is also discussed in that section. We then present in Section 3 an application of Theorem 1 to the study of pseudorandom graphs, highlighting an algorithmic consequence. In Section 4 we present applications of Theorem 1 to graph theory and to combinatorial number theory. A proof of Theorem 1 is outlined in Section 5. We close this note with some remarks and open problems.

Caveat. The regularity lemma is a powerful tool, but, naturally, several of its applications involve many further additional ideas and techniques. Although crucial in the applications we shall discuss below, the sparse version of this lemma is still far weaker than one would wish, and one has to fight quite hard to prove the results in question. Therefore, in this note, we shall not be able to state precisely how this lemma comes in in the proofs of the theorems under discussion. However, we shall try to hint what the rôle of the regularity lemma is in each case.

2 Sparse Variants of the Regularity Lemma

2.1 Preliminary Definitions

Let a graph G = G^{n} of order |G| = n be fixed. For U, W ⊂ V = V (G), we write E(U, W) = E_{G}(U, W) for the set of edges of G that have one endvertex in U and the other in W. We set e(U, W) = e_{G}(U, W) = |E(U, W)|. Now, let a partition P_{0} = (V_{i})_{1}^{ℓ} (ℓ ≥ 1) of V be fixed. For convenience, let us write (U, W) ≺ P_{0} if U ∩ W = ∅ and either ℓ = 1 or else ℓ ≥ 2 and for some i ≠ j (1 ≤ i, j ≤ ℓ) we have U ⊂ V_{i}, W ⊂ V_{j}.

Suppose 0 ≤ η ≤ 1. We say that G is (P_{0}, η)-uniform if, for some 0 ≤ p ≤ 1, we have that for all U, W ⊂ V with (U, W) ≺ P_{0} and |U|, |W | ≥ ηn, we have

|e_{G}(U, W) − p|U||W || ≤ ηp|U||W |.  (1)

We remark that the partition P_{0} is introduced to handle the case of ℓ-partite graphs (ℓ ≥ 2). If ℓ = 1, that is, if the partition P_{0} is trivial, then we are thinking of the case of ordinary graphs. In this case, we shorten the term (P_{0}, η)-uniform to η-uniform.

The prime example of an η-uniform graph is of course a random graph G_{p} = G_{n,p}. Note that for η > 0 a random graph G_{p} with p = p(n) = C/n is almost surely η-uniform provided C ≥ C_{0} = C_{0}(η), where C_{0}(η) depends only on η. Here and in the sequel, we use standard definitions and notation concerning random graphs. Let 0 < p = p(n) ≤ 1 be given. The standard binomial random graph G_{p} = G_{n,p} has as vertex set a fixed set V (G_{p}) of cardinality n and two such vertices are adjacent in G_{p} with probability p, with all such adjacencies independent. For concepts and results concerning random graphs, see, e.g., Bollobás [3].

2.2 A Regularity Lemma for Sparse Graphs

We first introduce a few further definitions that will allow us to state a version of Szemerédi’s lemma for sparse graphs. Let a graph G = G^{n} be fixed as before. Let H ⊂ G be a spanning subgraph of G. For U, W ⊂ V, let

d_{H,G}(U, W) = \{ \begin{matrix}e_{H}(U, W)/e_{G}(U, W) & if e_{G}(U, W) > 0 \\ 0 & if e_{G}(U, W) = 0. \end{matrix}

Suppose ε > 0, U, W ⊂ V, and U ∩ W = ∅. We say that the pair (U, W) is (ε, H, G)-regular, or simply ε-regular, if for all U′ ⊂ U, W′ ⊂ W with |U′| ≥ ε|U| and |W′| ≥ ε|W |, we have

|d_{H,G}(U′, W′) − d_{H,G}(U, W)| ≤ ε.

We say that a partition Q = (C_{i})_{0}^{k} of V = V (G) is (ε, k)-equitable if |C_{0}| ≤ εn, and |C_{1}| = … = |C_{k}|. Also, we say that C_{0} is the exceptional class of Q. When the value of ε is not relevant, we refer to an (ε, k)-equitable partition as a kequitable partition. Similarly, Q is an equitable partition of V if it is a k-equitable partition for some k. If P and Q are two equitable partitions of V, we say that Q refines P if every non-exceptional class of Q is contained in some non-exceptional class of P. If P′ is an arbitrary partition of V, then Q refines P′ if every nonexceptional class of Q is contained in some block of P′. Finally, we say that an (ε, k)-equitable partition Q = (C_{i})_{0}^{k} of V is (ε, H, G)-regular, or simply ε-regular, if at most ε\binom{k}{2} pairs (C_{i}, C_{j}) with 1 ≤ i < j ≤ k are not ε-regular. We may now state an extension of Szemerédi’s lemma to subgraphs of (P_{0}, η)-uniform graphs.

Theorem 1. Let ε > 0 and k_{0}, ℓ ≥ 1 be fixed. Then there are constants η = η(ε, k_{0}, ℓ) > 0 and K_{0} = K_{0}(ε, k_{0}, ℓ) ≥ k_{0} satisfying the following. For any (P_{0}, η)-uniform graph G = G^{n}, where P_{0} = (V_{i})_{1}^{ℓ} is a partition of V = V (G), if H ⊂ G is a spanning subgraph of G, then there exists an (ε, H, G)-regular (ε, k)-equitable partition of V refining P_{0} with k_{0} ≤ k ≤ K_{0}. ⊓ ⊔

Remark. To recover the original regularity lemma of Szemerédi from Theorem 1, simply take G = K^{n}, the complete graph on n vertices.

2.3 A Second Regularity Lemma for Sparse Graphs

In some situations, the sparse graph H to which one would like to apply the regularity lemma is not a subgraph of some fixed η-uniform graph G. A simple variant of Theorem 1 may be useful in this case. For simplicity, we shall not state this variant for ‘P_{0}-partite’ graphs as we did in Section 2.2.

Let a graph H = H^{n} of order |H| = n be fixed. Suppose 0 < η ≤ 1 and 0 < p ≤ 1. We say that H is η-upper-uniform with density p if, for all U, W ⊂ V with U ∩ W = ∅ and |U|, |W | ≥ ηn, we have e_{H}(U, W) ≤ (1 + η)p|U||W |. In the sequel, for any two disjoint non-empty sets U, W ⊂ V, let d_{H,p}(U, W) = e_{H}(U, W)/2p|U||W |.

Now suppose ε > 0, U, W ⊂ V, and U ∩W = ∅. We say that the pair (U, W) is (ε, H, p)-regular, or simply (ε, p)-regular, if for all U′ ⊂ U, W′ ⊂ W with |U′| ≥ ε|U| and |W′| ≥ ε|W | we have

|d_{H,p}(U′, W′) − d_{H,p}(U, W)| ≤ ε.

We say that an (ε, k)-equitable partition P = (C_{i})_{0}^{k} of V is (ε, H, p)-regular, or simply (ε, p)-regular, if at most ε\binom{k}{2} pairs (C_{i}, C_{j}) with 1 ≤ i < j ≤ k are not (ε, p)-regular. We may now state a version of Szemerédi’s regularity lemma for η-upper-uniform graphs.

Theorem 2. For any given ε > 0 and k_{0} ≥ 1, there are constants η = η(ε, k_{0}) > 0 and K_{0} = K_{0}(ε, k_{0}) ≥ k_{0} such that any η-upper-uniform graph H with density 0 < p ≤ 1 admits an (ε, H, p)-regular (ε, k)-equitable partition of its vertex set with k_{0} ≤ k ≤ K_{0}. ⊓ ⊔

Remarks. (i) A further variant of Theorem 1 concerns the existence ε-regular partitions with respect to a collection of graphs on the same vertex set. Such a variant is used [20].

(ii) Variants of Theorems 1 and 2 for sparse hypergraphs may be proved easily. However, we know of no applications of such results. For hypergraph versions of the regularity lemma, see [4, 12].

3 Checking Pseudorandomness of Graphs

The investigation of explicitly constructible graphs that are ‘random-like’ has proved to be very fruitful in providing examples for many extremal problems in graph theory. These graphs have also played a crucial rôle in algorithmic problems: the use of expanders for amplifying the power of random sources is but one example.

The study of pseudorandom graph properties, i.e., properties that random graphs have and somehow capture their ‘random nature,’ can be traced back to Graham and Spencer [18], Rödl [33], and Frankl, Rödl, and Wilson [13]. Thomason [41, 42] and Chung, Graham, and Wilson [7] present further developments that have given this subject the status of a solid theory. (We do not go into the details, but we mention that similar theories for hypergraphs and subsets of ℤ_{n} are now available, see Chung and Graham [5, 6].)

In this section, we shall be concerned with a new pseudorandom graph property introduced by Rödl. This property characterises quasi-random graphs in the sense of Chung, Graham, and Wilson [7]. As a consequence of this characterisation, we shall have an optimal algorithm for checking quasi-randomness of graphs. For the proofs of the results in this section, the reader is referred to [28].

3.1 Preliminary Definitions

Let reals 0 < ε ≤ 1 and 0 < δ ≤ 1 be given. We shall say that a graph G is (1/2, ε, δ)-quasi-random if, for all U, W ⊂ V (G) with U ∩ W = ∅ and |U|, |W | ≥ δn, we have

|e_{G}(U, W) − \frac{1}{2}|U||W || ≤ \frac{1}{2}ε|U||W |.  (2)

If 0 < ϱ ≤ 1 and A are reals, we say that an n-vertex graph J = J^{n} is (ϱ, A)-uniform if, for all U, W ⊂ V (J) with U ∩ W = ∅, we have

|e_{J}(U, W) − ϱ|U||W || ≤ A\sqrt{r|U||W |},  (3)

where r = ϱn. In the sequel, we may take the graph J to be a Lubotzky–Phillips– Sarnak Ramanujan graph X_{p,q} for some values of p and q, see [30]. If J = X_{p,q}, we have r = p + 1 and the graph J is r-regular. Moreover, in this case, inequality (3) holds with A = 2, and in fact r on the right hand side of (3) may be replaced by r − 1.

We shall now define a property for n-vertex graphs G = G^{n}, based on a fixed (ϱ, A)-uniform graph J = J^{n} with the same vertex set as G. Let 0 < ε ≤ 1 be a real. We say that G satisfies property P_{J,△}(ε) if we have

∑_{ij∈E(J)} ||Γ_{G}(i) △ Γ_{G}(j)| − \frac{1}{2}n| ≤ \frac{1}{2}εne(J),  (4)

where, as usual, we write Γ_{G}(x) for the G-neighbourhood of a vertex x of G, and we write A △ B for the symmetric difference (A \ B) ∪ (B \ A). Moreover, in (4) and in the sequel, e(J) denotes the number of edges in J. As we shall see in Section 3.2, inequality (4), which may be checked in time O(n^{2}) if we take J to be a graph with e(J) = O(n), turns out to be a quasi-random property in the sense of [7].

For technical reasons, we need to introduce a variant of property P_{J,△}(ε). Suppose 0 < γ ≤ 1 and 0 < ε ≤ 1 are two reals and G = G^{n} is an n-vertex graph. We shall say that G satisfies property P′_{J,△}(γ, ε) if the inequality

||Γ_{G}(i) △ Γ_{G}(j)| − \frac{1}{2}n| ≤ \frac{1}{2}εn  (5)

fails for at most γe(J) edges ij ∈ E(J) of J. As a quick argument shows, properties P_{J,△}(ε) and P_{J,△}(γ, ε) are equivalent under suitable assumptions on the parameters, see Lemma 5.

3.2 The Equivalence Results

The following three results express the equivalence between quasi-randomness, in the technical sense of Chung, Graham, and Wilson [7], and property P_{J,△}. Loosely speaking, quasi-randomness in the sense of [7] is equivalent to the property of being (1/2, o(1), o(1))-quasi-random, which, as the results below show, is equivalent to property P_{J,△}(o(1)).

Theorem 3. Let an r-regular (ϱ, A)-uniform graph J = J^{n} be fixed, where 0 < ϱ = r/n ≤ 1 and A is an absolute constant. Let constants 0 < ε ≤ 1 and 0 < δ ≤ 1 be given. Then if 0 < ε′ ≤ ε^{2}δ^{3}/8 and r ≥ 2^{10}A^{2}ε^{−2}δ^{−2}, we have that any graph G = G^{n} on the same vertex set as J satisfying property P_{J,△}(ε′) is (1/2, ε, δ)-quasi-uniform. ⊓ ⊔

Theorem 4. Let an r-regular (ϱ, A)-uniform graph J = J^{n} be fixed, where 0 < ϱ = r/n ≤ 1 and A is an absolute constant. Let constants 0 < γ ≤ 1 and 0 < ε ≤ 1 be given. Then there exist constants 0 < ε_{0} = ε_{0}(γ, ε) ≤ 1, 0 < δ_{0} = δ_{0}(γ, ε) ≤ 1, and r_{0} = r_{0}(γ, ε) ≥ 1, which depend only on γ and ε, such that any (1/2, ε′, δ′)-quasi-uniform graph G on the same vertex set as J satisfies property P′_{J,△}(γ, ε) as long as ε′ ≤ ε_{0}(γ, ε), δ′ ≤ δ_{0}(γ, ε), and r ≥ r_{0}(γ, ε). ⊓ ⊔

Lemma 5. Let a (ϱ, A)-uniform graph J = J^{n} be given, where 0 < ϱ ≤ 1 and A is an absolute constant. The following assertions hold.

(i) Let G = G^{n} be a graph on V (J) satisfying property P′_{J,△}(γ, ε), where 0 < γ ≤ 1 and 0 < ε ≤ 1 satisfy γ + ε ≤ 1. Then G has property P_{J,△}(ε + γ).

(ii) Let G = G^{n} be a graph on V (J) satisfying property P_{J,△}(ε) and suppose ε ≤ ε′ ≤ 1. Then G satisfies property P′_{J,△}(ε/ε′, ε′). ⊓ ⊔

An immediate corollary to the above results is as follows.

Corollary 6. Given an n-vertex graph G, we can decide in time O(n^{2}) whether or not G is a quasi-random graph. ⊓ ⊔

Previously, the fastest known method for checking quasi-randomness was based on the quasi-random property P_{J,△} with J the complete graph K^{n} on n vertices. This gave an algorithm of time complexity O(M(n)), where M(n) = O(n^{2.376}) is the time needed for multiplying two n by n matrices with 0–1 entries over the integers.

The Rôle of the Regularity Lemma. Theorem 1 is used in the proof of Theorem 4. Roughly speaking, one takes a graph G as in the statement of Theorem 4, and assumes that it does not satisfy P′_{J,△}(γ, ε). One then takes the spanning subgraph H of J whose edges are the ‘violating edges’ ij ∈ E(J), where we call an edge ij violating if (5) fails for ij. Note that a violating edge may be of two types, corresponding to the two inequalities expressed in (5). Thus, we may naturally split the edges of H into two groups; say H = H_{−} ∪ H_{+}. Assume that, say, e(H_{+}) ≥ (1/2)e(H) ≥ (γ/2)e(J). We may then apply Theorem 1 to the pair H_{+} ⊂ J. Once an H_{+}-dense regular pair (V_{i}, V_{j}) is shown to exist, one may prove that there is a pair (U, W) of suitably large sets that violate (2). Details are given in [28].

4 Further Applications

4.1 Applications in Graph Theory

A classical area of extremal graph theory investigates numerical and structural problems concerning H-free graphs, namely graphs that do not contain a copy of a given fixed graph H as a subgraph. Let ex(n, H) be the maximal number of edges that an H-free graph on n vertices may have. A basic question is then to determine or estimate ex(n, H) for any given H and large n. A solution to this problem is given by the celebrated Erdős–Stone–Simonovits theorem, which states that, as n → ∞, we have

ex(n, H) = (1 − \frac{1}{χ(H) − 1} + o(1)) \binom{n}{2},  (6)

where as usual χ(H) is the chromatic number of H. Furthermore, as proved independently by Erdős and Simonovits, every H-free graph G = G^{n} that has as many edges as in (6) is in fact ‘very close’ (in a certain precise sense) to the densest n-vertex (χ(H) − 1)-partite graph. For these and related results, see, for instance, Bollobás [2].

Here we are interested in a variant of the function ex(n, H). Let G and H be graphs, and write ex(G, H) for the maximal number of edges that an H-free subgraph of G may have. Formally, ex(G, H) = max{e(J): H ⊄ J ⊂ G}, where e(J) stands for the size |E(J)| of J as before. Clearly ex(n, H) = ex(K^{n}, H).

One problem is, then, to study ex(G, H) when G is a ‘typical’ graph, by which we mean a random graph. In other words, we wish to investigate the random variable ex(G_{n,p}, H).

Let H be a graph of order |H| = |V (H)| ≥ 3 and size e(H) > 0. Let us write d_{2}(H) for the 2-density of H, that is,

d_{2}(H) = max \{\frac{e(J) − 1}{|J| − 2}: J ⊂ H, |J| ≥ 3\} .

Given a real 0 ≤ ε ≤ 1 and an integer r ≥ 2, let us say that a graph J is ε-quasi r-partite if J may be made r-partite by the deletion of at most εe(J) of its edges. A general conjecture concerning ex(G_{n,p}, H) is as follows (cf. [26]). As is usual in the theory of random graphs, we say that a property P holds almost surely or that almost every random graph G_{n,p} satisfies P if P holds with probability tending to 1 as n → ∞.

Conjecture 7. Let H be a non-empty graph of order at least 3, and let 0 < p = p(n) ≤ 1 be such that pn^{1/d_{2}(H)} → ∞ as n → ∞. Then the following assertions hold.

(i) Almost every G_{n,p} satisfies

ex(G_{n,p}, H) = (1 − \frac{1}{χ(H) − 1} + o(1)) e(G_{n,p}).  (7)

(ii) Suppose χ(H) ≥ 3. Then for any ε > 0 there is a constant δ = δ(ε) > 0 such that almost every G_{n,p} has the property that any H-free subgraph J ⊂ G_{n,p} of G_{n,p} with e(J) ≥ (1 − δ) ex(G_{n,p}, H) is ε-quasi (χ(H) − 1)-partite. ⊓ ⊔

Recall that any graph G contains an r-partite subgraph J ⊂ G with e(J) ≥ (1 − 1/r)e(G). Thus the content of Conjecture 7(i) is that ex(G_{n,p}, H) is at most as large as the right-hand side of (7). There are a few results in support of Conjecture 7(i).

Any result concerning the tree-universality of expanding graphs, or else a simple application of Theorem 2, gives Conjecture 7(i) for forests. The cases in which H = K^{3} and H = C^{4} are essentially proved in Frankl and Rödl [11] and Füredi [15], respectively, in connection with problems concerning the existence of some graphs with certain extremal properties. The case in which H is a general cycle was settled by Haxell, Kohayakawa, and Łuczak [21, 22] (see also Kohayakawa, Kreuter, and Steger [25]), and the case in which H = K^{4} was settled by Kohayakawa, Łuczak, and Rödl [26]. Conjecture 7(ii) in the case in which 0 < p ≤ 1 is a constant follows easily from Szemerédi’s original regularity lemma. Theorem 2 and a lemma from Kohayakawa, Łuczak, and Rödl [27] concerning induced subgraphs of bipartite graphs may be used to verify Conjecture 7 for H = K^{3} in full, and, more generally, Conjecture 7 may be proved for the case in which H is a cycle by making use of a lemma in Kohayakawa and Kreuter [24].

We must at this point mention that beautiful and very general results concerning Ramsey properties of random graphs in the spirit of Conjecture 7 were proved by Rödl and Ruciński [35, 36]. These authors used the original lemma of Szemerédi. A related result, of a much more restricted scope but apparently not accessible through the techniques in [35, 36], is proved in Kohayakawa and Kreuter [24]. Theorem 2 is crucial in [24].

The Rôle of the Regularity Lemma. A moment’s thought reveals that Theorem 1 is immediately applicable to the situation given in Conjecture 7. Indeed, we have a subgraph J of a random and hence η-uniform graph G_{n,p} at hand and therefore we may invoke Theorem 1 to obtain an (ε, J, G_{n,p})-regular partition P of V = V (G_{n,p}), for any constants ε > 0 and k_{0}. If we further know that

e(J) ≥ (1 − \frac{1}{χ(H) − 1} + δ) e(G_{n,p}),

where δ > 0 is some constant, it is a simple matter to find a set of h = |H| classes V_{i} in the partition P that ‘form a copy of H’ (here we need to have ε suitably small and k_{0} suitably large with respect to δ). If we are dealing with 0 < p ≤ 1 that is a constant, independent of n, then we are finished, since these h classes may be shown to span a copy of H. If p = p(n) → 0 as n → ∞, however, we are stuck, since this last statement does not necessarily hold. In [21, 22, 24, 26], we are forced to take different approaches, all of them based on more involved applications of our sparse variants of the regularity lemma. We shall not go into the details. We shall, however, discuss a conjecture (cf. [26]) from which, if true, one may deduce Conjecture 7 through the standard approach described above.

Suppose H has vertices v_{1}, …, v_{h} (h ≥ 3) and let 0 < p = p(m) ≤ 1 be given. Let also V = (V_{i})_{i=1}^{h} be a family of h pairwise disjoint sets, each of cardinality m. Suppose reals 0 < ε ≤ 1 and 0 < γ ≤ 1 and an integer T are given. We say that an h-partite graph F with h-partition V (F) = V_{1} ∪ ⋯ ∪ V_{h} and size e(F) = |F | = T is an (ε, γ, H; V, T)-graph if the pair (V_{i}, V_{j}) is (ε, F, p)-regular and has p-density γ ≤ d_{F,p}(V_{i}, V_{j}) ≤ 1 whenever v_{i}v_{j} ∈ E(H).

Conjecture 8. Let constants 0 < α ≤ 1 and 0 < γ ≤ 1 be given. Then there exist constants ε = ε(α, γ) > 0 and C = C(α, γ) such that, if p = p(m) ≥ Cm^{−1/d_{2}(H)}, the number of H-free (ε, γ, H; V, T)-graphs is at most

α^{T} \binom{\binom{h}{2}m^{2}}{T}

for all T and all sufficiently large m. ⊓ ⊔

If H above is a forest, Conjecture 8 holds trivially, since, in this case, all (ε, γ, H; V, T)-graphs contain a copy of H. A lemma in Kohayakawa, Łuczak, and Rödl [27] may be used to show that Conjecture 8 holds for the case in which H = K^{3}. The general case of cycles is established in Kohayakawa and Kreuter [24].

Remark. Other graph theoretical applications of the regularity lemma for sparse graphs are given in Haxell and Kohayakawa [19] and Haxell, Kohayakawa, and Łuczak [20]. These applications concern Ramsey and anti-Ramsey properties of random and pseudorandom graphs.

4.2 An Application in Combinatorial Number Theory

We now turn to a problem concerning arithmetic progressions of integers. Here we are interested in the existence of a ‘small’ and ‘sparse’ set R ⊂ [n] = {1, …, n} with the property that every subset A ⊂ R that contains a fixed positive fraction of the elements of R contains also a 3-term arithmetic progression. The measure of sparseness here should reflect the fact that R is locally poor in 3-term arithmetic progressions. Clearly, a natural candidate for such a set R is an M-element set R_{M} uniformly selected from all the M-element subsets of [n], where 1 ≤ M = M(n) ≤ n is to be chosen suitably. The main result of Kohayakawa, Łuczak, and Rödl [27] confirms this appealing and intuitive idea.

For integers 1 ≤ M ≤ n, let R(n, M) be the probability space of all the M-element subsets of [n] equipped with the uniform measure. In the sequel, given 0 < α ≤ 1 and a set R ⊂ [n], write R →_{α} 3 if any A ⊂ R with |A| ≥ α|R| contains a 3-term arithmetic progression. The main result of [27] may then be stated as follows.

Theorem 9. For every constant 0 < α ≤ 1, there exists a constant C = C(α) such that if C\sqrt{n} ≤ M = M(n) ≤ n then the probability that R_{M} ∈ R(n, M) satisfies R_{M} →_{α} 3 tends to 1 as n → ∞. ⊓ ⊔

Note that Theorem 9 is, in a way, close to being best possible: if M = M(n) = ⌊ε\sqrt{n}⌋ for some fixed ε > 0 then the number of 3-term arithmetic progressions in R_{M} ∈ R(n, M) is, with large probability, smaller than 2ε^{2}|R_{M}|, and hence all of them may be destroyed by deleting at most 2ε^{2}|R_{M}| elements from R_{M}; in other words, with large probability the relation R_{M} →_{α} 3 does not hold for α = 1 − 2ε^{2}.

Theorem 9 immediately implies the existence of ‘sparse’ sets S = S_{α} such that S →_{α} 3 for any fixed 0 < α ≤ 1. The following result makes this assertion precise.

Corollary 10. Suppose that s = s(n) = o(n^{1/8}) and g = g(n) = o(log n) as n → ∞. Then, for every fixed α > 0, there exist constants C and N such that for every n ≥ N there exists S ⊂ [n] satisfying S →_{α} 3 for which the following three conditions hold.

(i) For every k ≥ 0 and ℓ ≥ 1 the set {k, k +ℓ, …, k +sℓ} contains at most three elements of S.

(ii) Every set \{k, k+ℓ, …, k+mℓ\} with k ≥ 0, ℓ ≥ 1, and m ≥ \sqrt{n} log n contains

at most Cm/\sqrt{n} elements of S. (iii) If F = F(S) is the 3-uniform hypergraph on the vertex set S whose hyper-

edges are the 3-term arithmetic progressions contained in S, then F has no cycle of length smaller than g. ⊓ ⊔

In words, conditions (i) and (ii) above say that the set S intersects any arithmetic progression in a small number of elements. In particular, S contains no 4-term arithmetic progressions. Condition (iii) is more combinatorial in nature, and says that the 3-term arithmetic progressions contained in S form, locally, a tree-like structure, which makes the property S →_{α} 3 somewhat surprising.

Let us remark that the following extension of Szemerédi’s theorem related to Corollary 10 was proved by Rödl [34], thereby settling a problem raised by Spencer [38]. Let k, g ≥ 3 be fixed integers and 0 < α ≤ 1 a fixed real. Theorem 4.3 in [34] asserts that then, for any large enough n, there exists a k-uniform hypergraph F on [n], all of whose hyperedges are k-term arithmetic progressions, such that F contains no cycle of length smaller than g but each subset A ⊂ [n] with |A| ≥ αn contains a hyperedge of F. For other problems and results in this direction, see Graham and Nešetřil [16], Nešetřil and Rödl [31], and Prömel and Voigt [32]. Note that Corollary 10 strengthens the above result of [34] in the case in which k = 3.

The Rôle of the Regularity Lemma. A weak version of Roth’s theorem [37], namely, a version stating that any sequence of integers with positive upper density contains a 3-term arithmetic progression, may be proved by means of a moreor-less direct application of the regularity lemma, see, e.g., Erdős, Frankl, and Rödl [9] and Graham and Rödl [17]. Since Theorem 9 above deals with sparse sets of integers, a similar approach makes results such as Theorem 2 come into play. The difficulties that arise are, however, quite substantial. We close by mentioning that an application of a variant of Theorem 2 and the proof of Conjecture 8 for H = K^{3} are at the heart of the proof of Theorem 9.

5 Proof of Theorem 1

We now proceed to outline the proof Theorem 1, but, before we proceed, we stress that the argument below follows the one of Szemerédi [40] very closely. In particular, as in [40], the following ‘defect’ form of the Cauchy–Schwarz inequality will be important.

Lemma 11. Let reals y_{1}, …, y_{v} ≥ 0 be given. Suppose 0 ≤ ϱ = u/v < 1 and ∑_{1≤i≤u} y_{i} = αϱ ∑_{1≤i≤v} y_{i}. Then

∑_{1≤i≤v} y_{i}^{2} ≥ \frac{1}{v} (1 + (α − 1)^{2} \frac{ϱ}{1 − ϱ}) \{ ∑_{1≤i≤v} y_{i}\}^{2}.  ⊓ ⊔

We now fix G = G^{n} and put V = V (G). Also, we assume that P_{0} = (V_{i})_{1}^{ℓ} is a fixed partition of V, and that G is (P_{0}, η)-uniform for some 0 ≤ η ≤ 1. Moreover, we let p = p(G) be as in (1). The following ‘continuity’ results for d_{H,G} and d_{H,G}^{2} may be proved in a straightforward manner.

Lemma 12. Let 0 < δ ≤ 10^{−2} be fixed. Let U, W ⊂ V (G) be such that (U, W) ≺ P_{0}, and δ|U|, δ|W | ≥ ηn. If U^{∗} ⊂ U, W^{∗} ⊂ W, |U^{∗}| ≥ (1 − δ)|U|, and |W^{∗}| ≥ (1 − δ)|W |, then

(i) |d_{H,G}(U^{∗}, W^{∗}) − d_{H,G}(U, W)| ≤ 5δ, (ii) |d_{H,G}(U^{∗}, W^{∗})^{2} − d_{H,G}(U, W)^{2}| ≤ 9δ. ⊓ ⊔

In the sequel, a constant 0 < ε ≤ 1/2 and a spanning subgraph H ⊂ G of G is fixed. Also, we let P = (C_{i})_{0}^{k} be an (ε, k)-equitable partition of V = V (G) refining P_{0}, where 4^{k} ≥ ε^{−5}. Moreover, we assume that η ≤ η_{0} = η_{0}(k) = 1/k4^{k+1} and that n = |G| ≥ n_{0} = n_{0}(k) = k4^{1+2k}.

We now define an equitable partition Q = Q(P) of V = V (G) from P as follows. First, for each (ε, H, G)-irregular pair (C_{s}, C_{t}) of P with 1 ≤ s < t ≤ k, we choose X = X(s, t) ⊂ C_{s}, Y = Y (s, t) ⊂ C_{t} such that (i) |X|, |Y | ≥ ε|C_{s}| = ε|C_{t}|, and (ii) |d_{H,G}(X, Y) − d_{H,G}(C_{s}, C_{t})| ≥ ε. For fixed 1 ≤ s ≤ k, the sets X(s, t) in

{X = X(s, t) ⊂ C_{s}: 1 ≤ t ≤ k and (C_{s}, C_{t}) is not (ε, H, G)-regular}

define a natural partition of C_{s} into at most 2^{k−1} blocks. Let us call such blocks the atoms of C_{s}. Now let q = 4^{k} and set m = ⌊|C_{s}|/q⌋ (1 ≤ s ≤ k). Note that ⌊|C_{s}|/m⌋ = q as |C_{s}| ≥ n/2k ≥ 2q^{2}. Moreover, for later use, note that m ≥ ηn. We now let Q′ be a partition of V = V (G) refining P such that (i) C_{0} is a block of Q′, (ii) all other blocks of Q′ have cardinality m, except for possibly one, which has cardinality at most m − 1, (iii) for all 1 ≤ s ≤ k, every atom A ⊂ C_{s} contains exactly ⌊|A|/m⌋ blocks of Q′, (iv) for all 1 ≤ s ≤ k, the set C_{s} contains exactly q = ⌊|C_{s}|/m⌋ blocks of Q′.

Let C′_{0} be the union of the blocks of Q′ that are not contained in any class C_{s} (1 ≤ s ≤ k), and let C′_{i} (1 ≤ i ≤ k′) be the remaining blocks of Q′. We are finally ready to define our equitable partition Q = Q(P): we let Q = (C′_{i})_{0}^{k′}. The following lemma is easy to check.

Lemma 13. The partition Q = Q(P) = (C′_{i})_{0}^{k′} defined from P as above is a k′-equitable partition of V = V (G) refining P, where k′ = kq = k4^{k}, and |C′_{0}| ≤ |C_{0}| + n4^{−k}. ⊓ ⊔

In what follows, for 1 ≤ s ≤ k, we let C_{s}(i) (1 ≤ i ≤ q) be the classes of Q′ that are contained in the class C_{s} of P. Also, for all 1 ≤ s ≤ k, we set C_{s}^{∗} = ⋃_{1≤i≤q} C_{s}(i). Now let 1 ≤ s ≤ k be fixed. Note that |C_{s}^{∗}| ≥ |C_{s}| − (m − 1) ≥ |C_{s}| − q^{−1}|C_{s}| ≥ |C_{s}|(1 − q^{−1}). As q^{−1} ≤ 10^{−2} and q^{−1}|C_{s}| ≥ m ≥ ηn, by Lemma 12 we have, for all 1 ≤ s < t ≤ k,

|d_{H,G}(C_{s}^{∗}, C_{t}^{∗}) − d_{H,G}(C_{s}, C_{t})| ≤ 5q^{−1}  (8)

and

|d_{H,G}(C_{s}^{∗}, C_{t}^{∗})^{2} − d_{H,G}(C_{s}, C_{t})^{2}| ≤ 9q^{−1}.  (9)

As in [40], we define the index ind(R) of an equitable partition R = (V_{i})_{0}^{r} of V = V (G) to be

ind(R) = \frac{2}{r^{2}} ∑_{1≤i<j≤ℓ} d_{H,G}(V_{i}, V_{j})^{2}.

Note that trivially 0 ≤ ind(R) < 1. The next two lemmas show that, for Q = Q(P) defined as above, we have ind(Q) ≥ ind(P)+ε^{5}/100. The proof of the first lemma is based on the Cauchy–Schwarz inequality.

Lemma 14. Suppose 1 ≤ s < t ≤ k. Then

\frac{1}{q^{2}} ∑_{i, j=1}^{q} d_{H,G}(C_{s}(i), C_{t}(j))^{2} ≥ d_{H,G}(C_{s}, C_{t})^{2} − \frac{ε^{5}}{100}.  ⊓ ⊔

The inequality in Lemma 14 may be improved if (C_{s}, C_{t}) is an (ε, H, G)- irregular pair. The following lemma, which is proved by invoking the defect form of the Cauchy–Schwarz inequality, Lemma 11, makes this precise.

Lemma 15. Let 1 ≤ s < t ≤ k be such that (C_{s}, C_{t}) is not (ε, H, G)-regular. Then

\frac{1}{q^{2}} ∑_{i, j=1}^{q} d_{H,G}(C_{s}(i), C_{t}(j))^{2} ≥ d_{H,G}(C_{s}, C_{t})^{2} + \frac{ε^{4}}{40} − \frac{ε^{5}}{100}.  ⊓ ⊔

The following result, which is the main lemma in the proof of Theorem 1, follows from Lemmas 14 and 15.

Lemma 16. Suppose k ≥ 1 and 0 < ε ≤ 1/2 are such that 4^{k} ≥ 1800ε^{−5}. Let G = G^{n} be a (P_{0}, η)-uniform graph of order n ≥ n_{0} = n_{0}(k) = k4^{2k+1}, where P_{0} = (V_{i})_{1}^{ℓ} is a partition of V = V (G), and assume that η ≤ η_{0} = η_{0}(k) = 1/k4^{k+1}. Let H ⊂ G be a spanning subgraph of G. If P = (C_{i})_{0}^{k} is an (ε, H, G)- irregular (ε, k)-equitable partition of V = V (G) refining P_{0}, then there is a k′- equitable partition Q = (C′_{i})_{0}^{k′} of V such that (i) Q refines P, (ii) k′ = k4^{k}, (iii) |C′_{0}| ≤ |C_{0}| + n4^{−k}, and (iv) ind(Q) ≥ ind(P) + ε^{5}/100. ⊓ ⊔

Proof of Theorem 1. (Outline) Let ε > 0, k_{0} ≥ 1, and ℓ ≥ 1 be given. We may assume that ε ≤ 1/2. Pick s ≥ 1 such that 4^{s/4ℓ} ≥ 1800ε^{−5}, s ≥ max{2k_{0}, 3ℓ/ε}, and ε4^{s−1} ≥ 1. Let f(0) = s, and put inductively f(t) = f(t − 1)4^{f(t−1)} (t ≥ 1). Let t_{0} = ⌊100ε^{−5}⌋ and set N = max{n_{0}(f(t)): 0 ≤ t ≤ t_{0}} = f(t_{0})4^{2f(t_{0})+1}, K_{0} = max{6ℓ/ε, N}, and η = η(ε, k_{0}, ℓ) = min{η_{0}(f(t)): 0 ≤ t ≤ t_{0}} = 1/4f(t_{0}+ 1) > 0. It is now straightforward to check that η and K_{0} as defined above will do. As in [40], the proof is simply based on the fact that the index of any partition is bounded, whereas, as stated in Lemma 16(iv), the index increases by a fixed amount every time we suitably refine an irregular partition. We omit the details.

⊓ ⊔

6 Final Remarks and Open Problems

It would be of interest to elucidate the algorithmic aspects of Theorem 1. For instance, can one find the partition guaranteed to exist in that result in time, say, O(n^{2}), if we are concerned with subgraphs H of r-regular η-uniform graphs G = G^{n}, where r is a constant independent of n? If this turns out to be the case, many algorithms developed in [1, 8] may be improved to optimal algorithms.

We hope that the above applications of the regularity lemma for sparse graphs reveal the potential of such variants of Szemerédi’s lemma. The applications also illustrate that the ‘right’ variant has not yet been found, since the successes are somewhat modest when compared with what the original lemma can achieve in the dense case. The problem of finding the ‘right’ variant of Szemerédi’s lemma for the sparse case is certainly of great interest.

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(1):80–109, 1994.

2. B. Bollobás. Extremal Graph Theory. Academic Press, London, 1978.

3. B. Bollobás. Random Graphs. Academic Press, London, 1985.

4. F.R.K. Chung. Regularity lemmas for hypergraphs and quasi-randomness. Random Structures and Algorithms, 2(1):241–252, 1991.

5. F.R.K. Chung and R.L. Graham. Quasi-random set systems. Journal of the American Mathematical Society, 4(1):151–196, 1991.

6. F.R.K. Chung and R.L. Graham. Quasi-random subsets of ℤ_{n}. Journal of Combinatorial Theory, Series A, 61(1):64–86, 1992.

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

8. R.A. Duke, H. Lefmann, and V. Rödl. A fast approximation algorithm for computing the frequencies of subgraphs in a given graph. SIAM Journal on Computing, 24(3):598–620, 1995.

9. 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(2):113–121, 1986.

10. P. Erdős and P. Turán. On some sequences of integers. Journal of the London Mathematical Society, 11(2):261–264, 1936.

11. P. Frankl and V. Rödl. Large triangle-free subgraphs in graphs without K_{4}. Graphs and Combinatorics, 2(2):135–144, 1986.

12. P. Frankl and V. Rödl. The uniformity lemma for hypergraphs. Graphs and Combinatorics, 8(4):309–312, 1992.

13. P. Frankl, V. Rödl, and R.M. Wilson. The number of submatrices of a given type in a Hadamard matrix and related results. Journal of Combinatorial Theory, Series B, 44(3):317–328, 1988.

14. A. Frieze and R. Kannan. The regularity lemma and approximation schemes for dense problems. In Proc. 37th Ann. IEEE Symp. on Foundations of Computer Science. IEEE, October 1996.

15. Z. Füredi. Random Ramsey graphs for the four-cycle. Discrete Mathematics, 126:407–410, 1994.

16. R.L. Graham and J. Nešetřil. Large minimal sets which force long arithmetic progressions. Journal of Combinatorial Theory, Series A, 42(2):270–276, 1986.

17. R.L. Graham and V. Rödl. Numbers in Ramsey theory. In C. Whitehead, editor, Surveys in Combinatorics 1987, volume 123 of London Mathematical Society Lecture Note Series, pages 112–153. Cambridge University Press, Cambridge–New York, 1987.

18. R.L. Graham and J. Spencer. A constructive solution to a tournament problem. Canadian Mathematics Bulletin, 14:45–48, 1971.

19. P.E. Haxell and Y. Kohayakawa. On an anti-Ramsey property of Ramanujan graphs. Random Structures and Algorithms, 6(4):417–431, 1995.

20. P.E. Haxell, Y. Kohayakawa, and T. Łuczak. The induced size-Ramsey number of cycles. Combinatorics, Probability, and Computing, 4(3):217–239, 1995.

21. P.E. Haxell, Y. Kohayakawa, and T. Łuczak. Turán’s extremal problem in random graphs: forbidding even cycles. Journal of Combinatorial Theory, Series B, 64:273– 287, 1995.

22. P.E. Haxell, Y. Kohayakawa, and T. Łuczak. Turán’s extremal problem in random graphs: forbidding odd cycles. Combinatorica, 16(1):107–122, 1996.

23. Y. Kohayakawa. The regularity lemma of Szemerédi for sparse graphs, manuscript, August 1993, 10 pp.

24. Y. Kohayakawa and B. Kreuter. Threshold functions for asymmetric Ramsey properties involving cycles. Random Structures and Algorithms. Submitted, 1996, 34 pp.

25. Y. Kohayakawa, B. Kreuter, and A. Steger. An extremal problem for random graphs and the number of graphs with large even-girth. Combinatorica. Submitted, 1995, 18 pp.

26. Y. Kohayakawa, T. Łuczak, and V. Rödl. On K^{4}-free subgraphs of random graphs. Combinatorica. Submitted, 1995, 35 pp.

27. Y. Kohayakawa, T. Łuczak, and V. Rödl. Arithmetic progressions of length three in subsets of a random set. Acta Arithmetica, LXXV(2):133–163, 1996.

28. Y. Kohayakawa and V. Rödl. Checking pseudorandomness of graphs fast (tentative title). In preparation, 1996.

29. J. Komlós and M. Simonovits. Szemerédi’s regularity lemma and its applications in graph theory. In D. Miklós, V.T. Sós, and T. Szőnyi, editors, Combinatorics— Paul Erdős is eighty, vol. 2, Bolyai Society Mathematical Studies, pages 295–352. János Bolyai Mathematical Society, Budapest, 1996.

30. A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8:261–277, 1988.

31. J. Nešetřil and V. Rödl. Partite construction and Ramseyan theorems for sets, numbers and spaces. Commentationes Mathematicae Universitatis Carolinae, 28(3):569–580, 1987.

32. H.-J. Prömel and B. Voigt. A sparse Graham–Rothschild theorem. Transactions of the American Mathematical Society, 309(1):113–137, 1988.

33. V. Rödl. On universality of graphs with uniformly distributed edges. Discrete Mathematics, 59(1-2):125–134, 1986.

34. V. Rödl. On Ramsey families of sets. Graphs and Combinatorics, 16(2):187–195, 1990.

35. V. Rödl and A. Ruciński. Lower bounds on probability thresholds for Ramsey properties. In D. Miklós, V.T. Sós, and T. Szőnyi, editors, Combinatorics—Paul Erdős is eighty, vol. 1, Bolyai Society Mathematical Studies, pages 317–346. János Bolyai Mathematical Society, Budapest, 1993.

36. V. Rödl and A. Ruciński. Threshold functions for Ramsey properties. Journal of the American Mathematical Society, 8(4):917–942, 1995.

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

38. J. Spencer. Restricted Ramsey configurations. Journal of Combinatorial Theory, Series A, 19(3):278–286, 1975.

39. E. Szemerédi. On sets of integer sets containing no k elements in arithmetic progression. Acta Arithmetica, 27:199–245, 1975.

40. E. Szemerédi. Regular partitions of graphs. In Problèmes Combinatoires et Théorie des Graphes, pages 399–401, Orsay, 1976. Colloques Internationaux CNRS n. 260.

41. A.G. Thomason. Pseudorandom graphs. In Random graphs ’85 (Poznán, 1985), volume 144 of North-Holland Math. Stud., pages 307–331. North-Holland, Amsterdam-New York, 1987.

42. A.G. Thomason. Random graphs, strongly regular graphs pseudorandom graphs. In C. Whitehead, editor, Surveys in Combinatorics 1987, volume 123 of London Mathematical Society Lecture Note Series, pages 173–195. Cambridge University Press, Cambridge–New York, 1987.

This article was processed using the L^{A}TEX macro package with LLNCS style