Combinatorics, Probability and Computing

Paper

Regular Partitions of Hypergraphs: Regularity Lemmas

VOJTĚCH RÖDLa1 and MATHIAS SCHACHTa2

a1 Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA (e-mail: rodl@mathcs.emory.edu)

a2 Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany (e-mail: schacht@informatik.hu-berlin.de)

Abstract

Szemerédi's regularity lemma for graphs has proved to be a powerful tool with many subsequent applications. The objective of this paper is to extend the techniques developed by Nagle, Skokan, and the authors and obtain a stronger and more ‘user-friendly’ regularity lemma for hypergraphs.

(Received March 25 2005)

(Revised January 14 2007)

Footnotes

Research partially supported by NSF grant DMS 0300529.

Research supported by DFG grant SCHA 1263/1-1.