TY - GEN

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

PY - 2007

Y1 - 2007

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

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

KW - Grothendieck's inequality

KW - Laplacian eigenvalues

KW - Quasi-random graphs

KW - Regularity lemma

KW - Sparse graphs

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

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

U2 - 10.1007/978-3-540-73420-8_68

DO - 10.1007/978-3-540-73420-8_68

M3 - Conference contribution

AN - SCOPUS:38149015463

SN - 3540734198

SN - 9783540734192

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

SP - 789

EP - 800

BT - Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings

PB - Springer Verlag

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

Y2 - 9 July 2007 through 13 July 2007

ER -