2006 | OriginalPaper | Chapter
Extremal Hypergraph Problems and the Regularity Method
Authors: Brendan Nagle, Vojtěch Rödl, Mathias Schacht
Publisher: Springer Berlin Heidelberg
Szemerédi’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.
Recently, the graph regularity method was extended to hypergraphs by Gowers and by Skokan and the authors. The
hypergraph regularity method
has been successfully employed in a handful of combinatorial applications, including alternative proofs to well-known density theorems of Szemerédi and of Purstenberg and Katznel-son. In this paper, we apply the hypergraph regularity method to a few extremal hypergraph problems of Ramsey and Turán flavor.
