TY - GEN

T1 - Can a graph have distinct regular partitions?

AU - Alon, Noga

AU - Shapira, Asaf

AU - Stav, Uri

PY - 2007

Y1 - 2007

N2 - 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 ([11]) and Lovász and Szegedy ([9],[10]), from a previously known variant of the regularity lemma due to Alon et al. [2]. The proof also provides a deterministic polynomial time algorithm for finding such partitions.

AB - 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 ([11]) and Lovász and Szegedy ([9],[10]), from a previously known variant of the regularity lemma due to Alon et al. [2]. The proof also provides a deterministic polynomial time algorithm for finding such partitions.

UR - http://www.scopus.com/inward/record.url?scp=37849014217&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=37849014217&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-73545-8_42

DO - 10.1007/978-3-540-73545-8_42

M3 - Conference contribution

AN - SCOPUS:37849014217

SN - 9783540735441

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 428

EP - 438

BT - Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings

PB - Springer Verlag

T2 - 13th Annual International Computing and Combinatorics Conference, COCOON 2007

Y2 - 16 July 2007 through 19 July 2007

ER -