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 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 
Official 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 
URI:  http://wrap.warwick.ac.uk/id/eprint/3320 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 
Downloads
Downloads per month over past year