A short proof of Gowers' lower bound for the regularity lemma (Q682130)

Let \(A\) and \(B\) be two vertex sets in a graph \(G\) and let \(e(A,B)\) be the number of edges \(uv\) such that \(u \in A\) and \(v \in B\). Define \(d_G(A,B)=e(A,B)/| A| | B| \). The pair \((A,B)\) is said to be \(\varepsilon\)-regular if \(| d_G(A,B)-d_G(A',B')| \leq \varepsilon\) for all \(A' \subseteq A\) and \(B' \subseteq B\) satisfying \(| A'| \geq \varepsilon | A| \) and \(| B'| \geq \varepsilon | B| \). A partition \(\mathbb{Z} = \{\mathbb{Z}_1, \ldots,\mathbb{Z}_k\}\) of the vertex set of a graph is called an equipartition of order \(k\) if all the sizes of the sets \(\mathbb{Z}_i\) differ by at most 1. Szemerédi's regularity lemma asserts that, for every \(\varepsilon > 0\), there is \(M=M(\varepsilon)\) such that every graph has an \(\varepsilon\)-regular equipartition of order at most \(M\). The original proof only showed that \(M(\varepsilon) \leq \mathrm{twr}(O(1/\varepsilon^5))\), where twr\((x)\) is a tower of exponents of height \(x\). In [\textit{T. Gowers}, Geom. Funct. Anal. 7, No. 2, 322--337 (1997; Zbl 0876.05053)], two lower bounds were given. The first bound \(M(\varepsilon) \geq \mathrm{twr}(\frac{1}{4}\log (1/\varepsilon))\) was obtained by an inductive construction. The second bound \(M(\varepsilon)\geq \mathrm{twr}(1/\varepsilon^c)\), where \(c=1/16\), was established with more complicated construction and significantly involved proof of correctness. The main contribution of this paper is a new proof of the second bound, with \(c= 1/6\), using an inductive approach very similar to the proof of the first bound of Gowers. The proofs differ in several subtle aspects so that the inductive argument can be executed \(1/\varepsilon^c\) times instead of \(\log (1/\varepsilon)\) times.