Szemerédi's lemma for the analyst
type: Item
instance of: scholarly article
title: Szemerédi's lemma for the analyst
zbMATH Open document ID: 1123.46020
author: Balázs Szegedy
author: László Lovász
published in: Geometric and Functional Analysis. GAFA
publication date: 2007-05-14T00:00:00Z
review text: Szemerédi's regularity lemma was first used in his proof of the Erdős--Turán conjecture on arithmetic progressions; cf.\ [\textit{E.\,Szemerédi}, Acta Arith.\ 27, 199--245 (1975; Zbl 0303.10056)]. Roughly speaking, it asserts that every sufficiently large graph can be decomposed into smaller pieces so that the subgraph between them behaves random-like. Here, the authors present various reformulations of the lemma or its variants in the language of analysis. The set-up is the Hilbert space \(L^2[0,1]\) and the (symmetric) kernel operators \[ (Wf)(x) = \int_0^1 w(x,y)f(y)\,dy, \] normed by \[ \| W\| _{\square} = \sup_{S,T\subset [0,1]} \biggl| \int_{S\times T} w(x,y)\,dx\,dy \biggr|. \] For matrices, this last norm is known as the cut-norm. One way to restate the Szemerédi lemma in analytic terms is as follows. For every \(\varepsilon>0\), there is an integer \(k(\varepsilon)>0\) such that, for every symmetric measurable function \(w: [0,1]^2 \to [0,1]\), there is a partition \([0,1]=S_1\cup\dots\cup S_k\) into \(k\leq k(\varepsilon)\) sets of equal measure such that, for every \(R\subset [0,1]^2\) that is a union of at most \(k^2\) measurable rectangles, one has \[ \biggl| \int_R (w-w_{\mathcal P}) \,dx\,dy \biggr| \leq \varepsilon, \] where \(w_{\mathcal P}\) is the conditional expectation of \(w\) for the partition \([0,1]^2 = \bigcup_{i,j=1}^k S_i\times S_j\) of \([0,1]^2\). Other reformulations of Szemerédi's lemma involve a general result on approximation in Hilbert spaces or the compactness of a certain metric space defined by means of the cut-norm or coverings of \([0,1]\) with balls of small diameter for a certain metric. The last section contains two applications, for example, a lower bound on the number of classes in the weak version of the Szemerédi lemma. Reviewer's remark: A related paper is [\textit{T.\,Tao}, Contrib.\ Discrete Math.\ 1, No.\,1, 8--28 (2006; Zbl 1093.05030)] that discusses Szemerédi's lemma from the perspective of probability theory.
reviewed by: Dirk Werner
Mathematics Subject Classification ID: 46C99
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 5152562
zbMATH Keywords: Szemerédi's regularity lemma
zbMATH Keywords: kernel operators on Hilbert spaces
zbMATH Keywords: cut-norm
Wikidata QID: Q105583448
MaRDI profile type: Publication
full work available at URL: s00039-007-0599-6
OpenAlex ID: W2068571612
DOI: 10.1007/S00039-007-0599-6
description: scientific article; zbMATH DE number 5152562