The Library

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

Tools

Alon, Noga, Coja-Oghlan, Amin, Hàn, Hiêp, Kang, Mihyun, Rödl, Vojtěch and Schacht, Mathias. (2010) Quasi-randomness and algorithmic regularity for graphs with general degree distributions. SIAM Journal on Computing, Vol.39 (No.6). pp. 2336-2362. ISSN 0097-5397

Preview

Text
WRAP_Coja-Oghlan_Quasi_randomness.pdf - Published Version
Download (530Kb) | Preview

Official URL: http://dx.doi.org/10.1137/070709529

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

Item Type:

Journal Article

Subjects:

Q Science > QA Mathematics

Divisions:

Faculty of Science > Mathematics

Library of Congress Subject Headings (LCSH):

Random graphs, Partitions (Mathematics)

Journal or Publication Title:

SIAM Journal on Computing

Publisher:

Society for Industrial and Applied Mathematics

ISSN:

0097-5397

Official Date:

2010

Dates:

Date	Event
2010	Published

Volume:

Vol.39

Number:

No.6

Page Range:

pp. 2336-2362

Identification Number:

10.1137/070709529

Status:

Peer Reviewed

Publication Status:

Published

Access rights to Published version:

Open Access

Funder:

European Research Council (ERC), Universiṭat Tel-Aviv. Hermann Minkowski Minerva Center for Geometry, Deutsche Forschungsgemeinschaft (DFG), National Science Foundation (U.S.) (NSF), German-Israeli Foundation for Scientific Research and Development, Israel Science Foundation (ISF)

Grant number:

CO 646 (DFG), PR 296/7- 3 (DFG), KA 2748/2-1 (DFG), DMS 0300529 (NSF), DMS 0800070 (NSF), SCHA 1263/1- 1 (DFG), 889/05 (GIF)

References:

[1] R. Albert and A. L. Barab´asi, Statistical mechanics of complex networks, Rev. Modern
Phys., 74 (2002), pp. 47–97.
[2] F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial
optimization, SIAM J. Optim., 5 (1995), pp. 13–51.
[3] N. Alon, R. A. Duke, V. R¨odl, and R. Yuster, The algorithmic aspects of the regularity
lemma, J. Algorithms, 16 (1994), pp. 80–109.
[4] N. Alon and A. Naor, Approximating the cut-norm via Grothendieck’s inequality, in Proceedings
of the 36th ACM Symposium on Theory of Computing, Chicago, IL, ACM, New
York, 2004, pp. 72–80.
[5] R. Bellman, Introduction to Matrix Analysis, 2nd ed., Classics in Appl. Math. 19, SIAM,
Philadelphia, 1997.
[6] Y. Bilu and N. Linial, Lifts, discrepancy, and nearly optimal spectral gap, Combinatorica, 26
(2006), pp. 495–519.
[7] B. Bollob´as and V. Nikiforov, Graphs and Hermitian matrices: Discrepancy and singular
values, Discrete Math., 285 (2004), pp. 17–32.
[8] S. Butler, Using discrepancy to control singular values for nonnegative matrices, Linear Algebra
Appl., 419 (2006), pp. 486–493.
[9] F. Chung, Spectral Graph Theory, American Mathematical Society, Providence, RI, 1997.
[10] F. Chung and R. Graham, Quasi-random graphs with given degree sequences, Random Structures
Algorithms, 32 (2008), pp. 1–19.
[11] F. Chung and R. Graham, Sparse quasi-random graphs, Combinatorica, 22 (2002), pp. 217–
244.
[12] F. Chung, R. Graham, and R. M. Wilson, Quasi-random graphs, Combinatorica, 9 (1989),
pp. 345–362.
[13] A. Frieze and R. Kannan, Quick approximation to matrices and applications, Combinatorica,
19 (1999), pp. 175–200.
[14] Z. F¨uredi and J. Komlo´s, The eigenvalues of random symmetric matrices, Combinatorica, 1
(1981), pp. 233–241.
[15] S. Gerke and A. Steger, The sparse regularity lemma and its applications, in Proceedings
of the 20th British Combinatorial Conference, Surveys in Combinatorics, London Math.
Soc. Lecture Note Ser. 327, B. S. Webb, ed., Cambridge University Press, Cambridge, UK,
2005, pp. 227–258.
[16] S. Gerke and A. Steger, A characterization for sparse ε-regular pairs, Electron. J. Combin.,
14 (2007), paper R4.
[17] A. Grothendieck, R´esum´e de la th´eorie m´etrique des produits tensoriels topologiques, Bol.
Soc. Mat. Sao Paulo, 8 (1953), pp. 1–79.
[18] M. Gr¨otschel, L. Lov´asz, and A. Schrijver, Geometric Algorithms and Combinatorial
Optimization, Springer, New York, 1988.
[19] J. H°astad, Some optimal inapproximability results, J. ACM, 48 (2001), pp. 798–859.
[20] C. Helmberg, Semidefinite Programming for Combinatorial Optimization, Habilitation thesis,
Report ZR-00-34, Zuse Institute, Berlin, 2000.
[21] Y. Kohayakawa, Szemer´edi’s regularity lemma for sparse graphs, in Foundations of Computational
Mathematics, F. Cucker and M. Shub, eds., Springer, New York, 1997, pp. 216–230.
[22] Y. Kohayakawa, V. R¨odl, and L. Thoma, An optimal algorithm for checking regularity,
SIAM J. Comput., 32 (2003), pp. 1210–1235.
[23] E. Szemer´edi, Regular partitions of graphs, in Probl´emes Combinatoires et Th´eorie des
Graphes, Colloq. Internat. CNRS 260, CNRS, Paris, 1978, pp. 399–401.
[24] L. Trevisan, G. B. Sorkin, M. Sudan, and D. P. Williamson, Gadgets, approximation, and
linear programming, SIAM J. Comput., 29 (2000), pp. 2074–2097.