Proc Natl Acad Sci U S A. 2005 Jun 07;102(23):8109-13. doi: 10.1073/pnas.0502771102. Epub 2005 May 26.

The hypergraph regularity method and its applications.

Proceedings of the National Academy of Sciences of the United States of America

V Rödl, B Nagle, J Skokan, M Schacht, Y Kohayakawa

PMID: 15919821 PMCID: PMC1149431 DOI: 10.1073/pnas.0502771102

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.

References

1. Proc Natl Acad Sci U S A. 1989 Nov;86(21):8175-7 - PubMed

Publication Types

• Journal Article