A tower lower bound for the degree relaxation of the Regularity Lemma

It is well-known that if \((A,B)\) is an \(\tfrac{\varepsilon}{2}\)-regular pair (in the sense of Szemerédi) then there exist sets \(A'\subset A\) and \(B'\subset B\) with \(|A'|\le \varepsilon|A|\) and \(|B'|\le \varepsilon|B|\) so that the degrees of all vertices in \(A\setminus A'\) differ by at most \(\varepsilon|B|\) and the degrees of all vertices in \(B\setminus B'\) differ by at most \(\varepsilon|A|\). We call such a property \(\varepsilon\)-degularity. This leads to the notion of an \(\varepsilon\)-degular partition of a graph in the same way as the definition of \(\varepsilon\)-regular pairs leads to the notion of \(\varepsilon\)-regular partitions.We show that there exist graphs in which any \(\varepsilon\)-degular partition requires the number of clusters to be \(\mathrm{tower}(\Theta(\varepsilon^{-1/3}))\). That is, even though degularity is a substantial relaxation of regularity, in general one cannot improve much on the bounds that come with Szemerédi's regularity lemma.Mathematics Subject Classifications: 05C35Keywords: Szemerédi's regularity lemma, degree