Quasi-randomness and algorithmic regularity for graphs with general degree distributions

Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Mihyun Kang, Vojtěch Rödl, Mathias Schacht

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

We deal with two intimately related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to express 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 introduce a concept of regularity that takes into account vertex weights, 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 [Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), Chicago, IL, ACM, New York, 2004, pp. 72-80], we provide an algorithm that computes a regular partition of a given (possibly sparse) graph G in polynomial time. As an application, we present a polynomial time approximation scheme for MAX CUT on (sparse) graphs without "dense spots."

Original languageEnglish (US)
Pages (from-to)2336-2362
Number of pages27
JournalSIAM Journal on Computing
Volume39
Issue number6
DOIs
StatePublished - 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics

Keywords

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

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