Szemerédi's lemma for the analyst (Q879618)

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.