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

Gowers, W. T.

Comb. Probab. Comput. 15, No. 1-2, 143-184 (2006).

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.

MSC:

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

Keywords:

theorem of Frankl and Rödl; Szemerédi’s theorem for arithmetic progressions; Szemerédi’s regularity lemma