TY - JOUR

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

AU - Alon, Noga

AU - Coja-Oghlan, Amin

AU - Hàn, Hiêp

AU - Kang, Mihyun

AU - Rödl, Vojtěch

AU - Schacht, Mathias

N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.

PY - 2010

Y1 - 2010

N2 - 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."

AB - 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."

KW - Grothendieck's inequality

KW - Laplacian eigenvalues

KW - Quasi-random graphs

KW - Regularity lemma

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

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

U2 - 10.1137/070709529

DO - 10.1137/070709529

M3 - Article

AN - SCOPUS:77952276186

VL - 39

SP - 2336

EP - 2362

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 6

ER -