Combinatorial Theory

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: 05C35

Keywords: Szemerédi's regularity lemma, degree