  Szemeredi's regularity lemma is one instance in a family of regularity
lemmas, replacing the definition of density of a graph by a more general
coefficient. Recently, Fan Chung proved another instance, a regularity lemma
for clustering graphs, and asked whether good upper bounds could be derived for
the quantitative estimates it supplies. We answer this question in the
negative, for every generalized regularity lemma.

Combinatorics;Discrete Mathematics