TY - JOUR
T1 - Limitations on regularity lemmas for clustering graphs
AU - Alon, Noga
AU - Moshkovitz, Guy
N1 - Publisher Copyright:
© 2020 Elsevier Inc.
PY - 2021/3
Y1 - 2021/3
N2 - Szemerédi'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.
AB - Szemerédi'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.
UR - http://www.scopus.com/inward/record.url?scp=85097244574&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85097244574&partnerID=8YFLogxK
U2 - 10.1016/j.aam.2020.102135
DO - 10.1016/j.aam.2020.102135
M3 - Article
AN - SCOPUS:85097244574
SN - 0196-8858
VL - 124
JO - Advances in Applied Mathematics
JF - Advances in Applied Mathematics
M1 - 102135
ER -