TY - JOUR
T1 - Limitations on regularity lemmas for clustering graphs
AU - Alon, Noga
AU - Moshkovitz, Guy
N1 - Funding Information:
Research supported in part by NSF grant DMS-1855464, ISF grant 281/17, BSF grant 2018267 and the Simons Foundation.Part of this work was done at the Institute for Advanced Study, enabled through support from NSF grant CCF-1412958, and at DIMACS, enabled through support from NSF grant CCF-1445755.
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 -