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, 1949- 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

PDF
WRAP_Coja-Oghlan_Quasi_randomness.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (371Kb)

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
Date:	2010
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.
URI:	http://wrap.warwick.ac.uk/id/eprint/3320