Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-22T00:26:01.324Z Has data issue: false hasContentIssue false

Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs

Published online by Cambridge University Press:  03 January 2006

W. T. GOWERS
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: [email protected])

Abstract

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 prove 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.

Type
Paper
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)