Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-25T18:51:31.665Z Has data issue: false hasContentIssue false
  • English
  • Français

Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs

Published online by Cambridge University Press:  03 January 2006

W. T. GOWERS
W. T. GOWERS
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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
Information
Combinatorics, Probability and Computing , Volume 15 , Issue 1-2 , January 2006 , pp. 143 - 184
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.)