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

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.

### MSC:

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

### Citations:

Zbl 0303.10056; Zbl 1093.05030
Full Text: