Combinatorics, Probability and Computing

Table of Contents - 2007 - Volume 16, Issue 06  

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.