### Abstract

We deal with two very related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to measure how much a given graph "resembles" a random one. Moreover, a regular partition approximates a given graph by a bounded number of quasi-random graphs. Regarding quasi-randomness, we present a new spectral characterization of low discrepancy, which extends to sparse graphs. Concerning regular partitions, we present a novel concept of regularity that takes into account the graph's degree distribution, and show that if G = (V, E) satisfies a certain boundedness condition, then G admits a regular partition. In addition, building on the work of Alon and Naor [4], we provide an algorithm that computes a regular partition of a given (possibly sparse) graph G in polynomial time.

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

Title of host publication | Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings |

Publisher | Springer Verlag |

Pages | 789-800 |

Number of pages | 12 |

ISBN (Print) | 3540734198, 9783540734192 |

DOIs | |

State | Published - 2007 |

Externally published | Yes |

Event | 34th International Colloquium on Automata, Languages and Programming, ICALP 2007 - Wroclaw, Poland Duration: Jul 9 2007 → Jul 13 2007 |

### Publication series

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

Volume | 4596 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 34th International Colloquium on Automata, Languages and Programming, ICALP 2007 |
---|---|

Country | Poland |

City | Wroclaw |

Period | 7/9/07 → 7/13/07 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

### Keywords

- Grothendieck's inequality
- Laplacian eigenvalues
- Quasi-random graphs
- Regularity lemma
- Sparse graphs

## Fingerprint Dive into the research topics of 'Quasi-randomness and algorithmic regularity for graphs with general degree distributions'. Together they form a unique fingerprint.

## Cite this

*Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings*(pp. 789-800). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4596 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-73420-8_68