Regularity, uniformity, and quasirandomness

Graph Regularity

Graph regularity was first introduced by Szemerédi (3), who used it to prove his celebrated theorem that every dense subset of integers contains arbitrary long arithmetic progressions. Today, one of the main tools in extremal graph theory is Szemerédi's regularity lemma (4), which makes arbitrary (usually large and dense) graphs manageable.‡ It was widely expected that hypergraph regularity could provide a similarly useful tool to deal with hypergraphs. The problem is that one can easily formulate fake hypergraph regularity lemmas by simply generalizing the original regularity lemma. The question was if one can find the “right” hypergraph lemma that can be used to prove theorems that do not follow from an application of the ordinary regularity lemma. Chung (5) was the first to come up with generalizations of regularity; however, her result had certain limitations. Her findings were not strong enough for applications to Szemerédi-type theorems, but still they formed a significant precursor to the more modern hypergraph regularity lemmas. After several years of hard work, Rödl and his students (1) have devised a solution providing a right notation of hypergraph regularity and proving the corresponding theorems using purely combinatorial tools. Gowers' approach (2) is somehow different, more analytic. The notations and proofs are related to his earlier proof of Szemerédi's theorem using Fourier analysis (6). One should mention here that the Cauchy–Schwarz-type arguments Gowers uses in his counting lemma were very influential in the recent results of Green and Tao (7) on long arithmetic progressions in the primes.

An Important Corollary

Graphs and hypergraphs are general combinatorial objects. A graph G is given by its vertex set V (G) and the edge set E(G), a list of vertex pairs that are connected by an edge. The notation of a hypergraph is similar. Given a set S as the vertex set, a family of the subsets of S will define the hyperedges. In this paper, we will focus on k-uniform hypergraphs, on hypergraphs where all the edges have the same size, k. With this notation, the two uniform hypergraphs are the ordinary graphs.

Given a k-uniform hypergraph, , on an n-element vertex set, a clique, K_{k +1}, is a k+1-element subset of such that any k-tuple of K_{k +1} is an edge of the hypergraph . Two cliques are said to be edge-disjoint if they don't have a common edge. Any set of pair-wise edge-disjoint cliques in has cardinality at most because every clique has k + 1 edges. The main result of ref. 1 is that if a hypergraph contains a large set, S, of pairwise edge-disjoint cliques, then it contains many cliques. In particular, the hypergraph contains at least one clique that is not in S. We will refer to the result below as the Removal Lemma for k-uniform hypergraphs. The reason why it is called Removal Lemma is that one can formulate the statement in the following equivalent way. If a hypergraph contains few cliques, then after removing only few edges from the hypergraph, the remaining hypergraph will not contain cliques at all.

Removal Lemma.

For any c > 0 real number and k ≥ 2 integer, there is a δ > 0 that depends on c and k only, such that the following is true. If contains a set, S, of pairwise edge-disjoint cliques with cardinality , then contains at least cliques.

A typical application of the result would be as follows. We want to prove that a given hypergraph contains two cliques sharing an edge. If we can show that there is a large set of pairwise edge-disjoint cliques, then we are done. To illustrate the method, we prove a generalization of Roth's theorem (8) about three-term arithmetic progressions in dense subsets of integers. We will show that if S is a dense subset of a large N × N integer grid, then S contains an isosceles equilateral triangle, three points with coordinates (x, y), (x + d, y), and (x, y + d), where d is a non-zero integer. It is easy to see that the statement implies Roth's theorem (Fig. 1).

The very same trick can be applied for higher dimensional grids, hyper-planes, and hypergraphs. This calculation leads us to a combinatorial proof of the so-called multidimensional Szemerédi theorem, which was proved by Fürstenberg and Katznelson (9) using ergodic theory.

It is not known how δ depends on c. Even in the simplest case, k = 2, the gap between the best known upper and lower bounds is huge. When n is large enough, is larger than , so there is at least one clique in that is not in S. It is surprising that this seemingly weak statement needs such heavy machinery. In most of the applications, all we need is to show that in a hypergraph there are two cliques that have a common edge. Random hypergraphs almost surely have such a pair of cliques. Therefore, if one can show that a given hypergraph is somehow similar to the random hypergraph, then this could lead to the proof. What we want from a hypergraph regularity lemma is to find for a given hypergraph, a partition of the one-, two-, three-,..., (k–1)-element subsets of into few classes such that the subgraphs, spanned by the classes, behave in a random-like way with only few exceptions. Also, one should come up with the right definition of “random-like.” This plan is nice, but unfortunately for k > 2 the solution is quite complicated. In 1978, for k = 2, Ruzsa and Szemerédi (10) proved that graph regularity implies the Removal Lemma for graphs. What Ruzsa and Szemerédi proved by using the regularity lemma for graphs is the following.

Triangle Removal Lemma.

If a graph on n vertices contains at least cn _· ² edge disjoint triangles, then it contains at least δn³ triangles.

It was 25 years later when Frankl and Rödl (11) published the k = 3 case. This shows how difficult it was to find the right generalization of graph regularity to hypergraphs. There is a test to decide whether a hypergraph regularity is useful or not. Does it imply the Removal Lemma? If the answer is yes, then it is a correct concept of regularity indeed. On the contrary, applications of the hypergraph regularity could go beyond the Removal Lemma. There are already examples for which the hypergraph regularity method, combined with ergodic theory, analysis, and number theory, are used efficiently to solve difficult problems in mathematics.