The hypergraph regularity method and its applications.

Abstract

Szemeredi's regularity lemma asserts that every graph can be decomposed into relatively few random-like subgraphs. This random-like behavior enables one to find and enumerate subgraphs of a given isomorphism type, yielding the so-called counting lemma for graphs. The combined application of these two lemmas is known as the regularity method for graphs and has proved useful in graph theory, combinatorial geometry, combinatorial number theory, and theoretical computer science. Here, we report on recent advances in the regularity method for k-uniform hypergraphs, for arbitrary k > or = 2. This method, purely combinatorial in nature, gives alternative proofs of density theorems originally due to E. Szemeredi, H. Furstenberg, and Y. Katznelson. Further results in extremal combinatorics also have been obtained with this approach. The two main components of the regularity method for k-uniform hypergraphs, the regularity lemma and the counting lemma, have been obtained recently: Rodl and Skokan (based on earlier work of Frankl and Rodl) generalized Szemeredi's regularity lemma to k-uniform hypergraphs, and Nagle, Rodl, and Schacht succeeded in proving a counting lemma accompanying the Rodl-Skokan hypergraph regularity lemma. The counting lemma is proved by reducing the counting problem to a simpler one previously investigated by Kohayakawa, Rodl, and Skokan. Similar results were obtained independently by W. T. Gowers, following a different approach.