Szemerédi’s lemma for the analyst. (English) Zbl 1123.46020

Lovász, László; Szegedy, Balász

Geom. Funct. Anal. 17, No. 1, 252-270 (2007).

Szemerédi’s regularity lemma was first used in his proof of the Erdős–Turán conjecture on arithmetic progressions; cf. [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 [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.

Reviewer: Dirk Werner (Berlin)

MSC:

46C99	Inner product spaces and their generalizations, Hilbert spaces
05C80	Random graphs (graph-theoretic aspects)

Keywords:

Szemerédi’s regularity lemma; kernel operators on Hilbert spaces; cut-norm

Citations:

Zbl 0303.10056; Zbl 1093.05030