The Library
Quasirandomness and algorithmic regularity for graphs with general degree distributions
Tools
Alon, Noga, CojaOghlan, Amin, Hàn, Hiêp, Kang, Mihyun, Rödl, Vojtěch, 1949 and Schacht, Mathias. (2010) Quasirandomness and algorithmic regularity for graphs with general degree distributions. SIAM Journal on Computing, Vol.39 (No.6). pp. 23362362. ISSN 00975397

Text
WRAP_CojaOghlan_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: quasirandomness and regular partitions. The purpose of the concept of quasirandomness 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 quasirandom graphs. Regarding quasirandomness, 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:  00975397 
Date:  2010 
Volume:  Vol.39 
Number:  No.6 
Page Range:  pp. 23362362 
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 TelAviv. Hermann Minkowski Minerva Center for Geometry, Deutsche Forschungsgemeinschaft (DFG), National Science Foundation (U.S.) (NSF), GermanIsraeli Foundation for Scientific Research and Development, Israel Science Foundation (ISF) 
Grant number:  CO 646 (DFG), PR 296/7 3 (DFG), KA 2748/21 (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 cutnorm 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, Quasirandom graphs with given degree sequences, Random Structures Algorithms, 32 (2008), pp. 1–19. [11] F. Chung and R. Graham, Sparse quasirandom graphs, Combinatorica, 22 (2002), pp. 217– 244. [12] F. Chung, R. Graham, and R. M. Wilson, Quasirandom 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 ZR0034, 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 
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
View Item 