The hypergraph regularity method and its applications

摘要

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 hyper-graphs, for arbitrary k ≥ 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 combinato'rics 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: Roedl and Skokan (based on earlier work of Frankl and Roedl) generalized Szemeredi's regularity lemma to k-uniform hypergraphs, and Nagle, Roedl, and Schacht succeeded in proving a counting lemma accompanying the Roedl-Skokan hypergraph regularity lemma. The counting lemma is proved by reducing the counting problem to a simpler one previously investigated by Kohayakawa, Roedl, and Skokan. Similar results were obtained independently by W. T. Gowers, following a different approach.