Can a graph have distinct regular partitions?

Noga Alon, Asaf Shapira, Uri Stav

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

The regularity lemma of Szemerédi gives a concise approximate description of a graph via a so-called regular partition of its vertex set. In this paper we address the following problem: Can a graph have two "distinct" regular partitions? It turns out that (as observed by several researchers) for the standard notion of a regular partition, one can construct a graph that has very distinct regular partitions. On the other hand, we show that for the stronger notion of a regular partition that has been recently studied, all such regular partitions of the same graph must be very "similar." En route, we also give a short argument for deriving a recent variant of the regularity lemma obtained independently by Rödl and Schacht and by Lovász and Szegedy from a previously known variant of the regularity lemma due to Alon et al. in 2000. The proof also provides a deterministic polynomial time algorithm for finding such partitions.

Original languageEnglish (US)
Pages (from-to)278-287
Number of pages10
JournalSIAM Journal on Discrete Mathematics
Volume23
Issue number1
DOIs
StatePublished - Dec 1 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Algorithm
  • Isomorphic
  • Regularity lemma

Fingerprint Dive into the research topics of 'Can a graph have distinct regular partitions?'. Together they form a unique fingerprint.

Cite this