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

Abstract

It is well-known that if $(A,B)$ is an $\frac{\epsilon }{2}$-regular pair (in the sense of Szemerédi) then there exist sets $A^{\prime }\subset A$ and $B^{\prime }\subset B^{\prime }$ with $|A^{\prime }|\le \epsilon |A|$ and $|B^{\prime }|\le \epsilon |B|$ so that the degrees of all vertices in $A\setminus A^{\prime }$ differ by at most $\epsilon |B|$ and the degrees of all vertices in $B\setminus B^{\prime }$ differ by at most $\epsilon |A|$. We call such a property "$\epsilon$-degularity". This leads to the notion of an "$\epsilon$-degular" partition of a graph in the same way as the definition of $\epsilon$-regular pairs leads to the notion of $\epsilon$-regular partitions. We show that there exist graphs in which any $\epsilon$-degular partition requires the number of clusters to be $\mathrm{tower}(\Theta ({\epsilon }^{-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.

13 pages, 1 figure