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

Abstrakt

It is well-known that if (A, B) is an ε/2 -regular pair (in the sense of Szemeredi) then there exist sets A′ ⊆ A and B′ ⊆ B with |A′ | ⩽ ε|A| and |B′ | ⩽ ε|B| so that the degrees of all vertices in A\A′ differ by at most ε|B| and the degrees of all vertices in B\B′ differ by at most ε|A|. We call such a property ε-degularity. This leads to the notion of an ε-degular partition of a graph in the same way as the definition of ε-regular pairs leads to the notion of ε-regular partitions. We show that there exist graphs in which any ε-degular partition requires the number of clusters to be tower(Θ(ε^(−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 Szemeredi’s regularity lemma.