### 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 ([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.

Original language | English (US) |
---|---|

Title of host publication | Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings |

Pages | 428-438 |

Number of pages | 11 |

State | Published - Dec 1 2007 |

Externally published | Yes |

Event | 13th Annual International Computing and Combinatorics Conference, COCOON 2007 - Banff, Canada Duration: Jul 16 2007 → Jul 19 2007 |

### Publication series

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

Volume | 4598 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

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

Country | Canada |

City | Banff |

Period | 7/16/07 → 7/19/07 |

### All Science Journal Classification (ASJC) codes

- Biochemistry, Genetics and Molecular Biology(all)
- Computer Science(all)
- Theoretical Computer Science

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

## Cite this

*Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings*(pp. 428-438). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4598 LNCS).