Back to Search
Start Over
CAN A GRAPH HAVE DISTINCT REGULAR PARTITIONS.
- Source :
- SIAM Journal on Discrete Mathematics; 2009, Vol. 23 Issue 1, p278-287, 10p
- Publication Year :
- 2009
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 23
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 36620149
- Full Text :
- https://doi.org/10.1137/070695952