Limitations on regularity lemmas for clustering graphs

Noga Alon, Guy Moshkovitz

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Article number102135
JournalAdvances in Applied Mathematics
Volume124
DOIs
StatePublished - Mar 2021

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Fingerprint Dive into the research topics of 'Limitations on regularity lemmas for clustering graphs'. Together they form a unique fingerprint.

Cite this