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

doi:10.1007/978-3-540-73420-8_68

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: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

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	https://doi.org/10.1007/978-3-540-73420-8_68
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/Territory	Poland
City	Wroclaw
Period	7/9/07 → 7/13/07

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Keywords

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

Access to Document

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

Cite this

Alon, N., Coja-Oghlan, A., Hàn, H., Kang, M., Rödl, V., & Schacht, M. (2007). Quasi-randomness and algorithmic regularity for graphs with general degree distributions. In 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

Alon, Noga ; Coja-Oghlan, Amin ; Hàn, Hiêp et al. / Quasi-randomness and algorithmic regularity for graphs with general degree distributions. Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings. Springer Verlag, 2007. pp. 789-800 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3708e7ece45f42dea92d40c6b62e1a2f,

title = "Quasi-randomness and algorithmic regularity for graphs with general degree distributions",

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

keywords = "Grothendieck's inequality, Laplacian eigenvalues, Quasi-random graphs, Regularity lemma, Sparse graphs",

author = "Noga Alon and Amin Coja-Oghlan and Hi{\^e}p H{\`a}n and Mihyun Kang and Vojt{\v e}ch R{\"o}dl and Mathias Schacht",

year = "2007",

doi = "10.1007/978-3-540-73420-8_68",

language = "English (US)",

isbn = "3540734198",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "789--800",

booktitle = "Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings",

address = "Germany",

note = "34th International Colloquium on Automata, Languages and Programming, ICALP 2007 ; Conference date: 09-07-2007 Through 13-07-2007",

}

Alon, N, Coja-Oghlan, A, Hàn, H, Kang, M, Rödl, V & Schacht, M 2007, Quasi-randomness and algorithmic regularity for graphs with general degree distributions. in Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4596 LNCS, Springer Verlag, pp. 789-800, 34th International Colloquium on Automata, Languages and Programming, ICALP 2007, Wroclaw, Poland, 7/9/07. https://doi.org/10.1007/978-3-540-73420-8_68

Quasi-randomness and algorithmic regularity for graphs with general degree distributions. / Alon, Noga; Coja-Oghlan, Amin; Hàn, Hiêp et al.
Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings. Springer Verlag, 2007. p. 789-800 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4596 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

Alon N, Coja-Oghlan A, Hàn H, Kang M, Rödl V, Schacht M. Quasi-randomness and algorithmic regularity for graphs with general degree distributions. In Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings. Springer Verlag. 2007. p. 789-800. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-73420-8_68

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

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this