Quasirandomness, counting and regularity for 3-uniform hypergraphs. (English) Zbl 1082.05081

Summary: The main results of this paper are regularity and counting lemmas for 3-uniform hypergraphs. A combination of these two results gives a new proof of a theorem of Frankl and Rödl, of which Szemerédi’s theorem for arithmetic progressions of length 4 is a notable consequence. Frankl and Rödl also proved regularity and counting lemmas, but the proofs here, and even the statements, are significantly different. Also included in this paper is a proof of Szemerédi’s regularity lemma, some basic facts about quasirandomness for graphs and hypergraphs, and detailed explanations of the motivation for the definitions used.


05C80 Random graphs (graph-theoretic aspects)
05C65 Hypergraphs
60C05 Combinatorial probability
05C35 Extremal problems in graph theory
Full Text: DOI