Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions

DOI10.1137/070709529MaRDI QIDQ3068635zbMATH OpenOpenAlexWikidataFDO

Authors Noga Alon, Amin Coja-Oghlan, Hiệp Hàn, Mihyun Kang, Vojtěch Rödl, M. Schacht

Publication date 17 January 2011

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://wrap.warwick.ac.uk/3320/3/WRAP_Coja-Oghlan_Quasi_randomness.pdf

zbMATH Keywords

Grothendieck's inequalityLaplacian eigenvaluesquasi-random graphsregular partitionregularity Lemma

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions
• Quasirandomness in Graphs
• Quasi-randomness and the regularity method in hypergraphs
• Hypergraph regularity and quasi-randomness
• Quasi-randomness and the distribution of copies of a fixed graph
• Hypergraphs, quasi-randomness, and conditions for regularity
• Quasi‐random graphs with given degree sequences
• Quasi-random graphs

Cited in

(22)

• Quasi-randomness and the distribution of copies of a fixed graph
• Discrepancy minimizing spectral clustering
• Regularity-based spectral clustering and mapping the Fiedler-carpet
• Average Gromov hyperbolicity and the Parisi ansatz
• A weighted regularity lemma with applications
• Extremal results in sparse pseudorandom graphs
• Modularity spectra, eigen-subspaces, and structure of weighted graphs
• Relating multiway discrepancy and singular values of nonnegative rectangular matrices
• Discrepancy and eigenvalues of Cayley graphs
• Spectra and structure of weighted graphs
• Grothendieck-type inequalities in combinatorial optimization
• Quasi-randomness Is Determined by the Distribution of Copies of a Fixed Graph in Equicardinal Large Sets
• Quasirandom Cayley graphs
• On the KŁR conjecture in random graphs
• Generalized quasirandom properties of expanding graph sequences
• The poset of hypergraph quasirandomness
• A note on even cycles and quasirandom tournaments
• Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• A unified view of graph regularity via matrix decompositions
• Beyond the expanders
• Matrix and discrepancy view of generalized random and quasirandom graphs

This page was built for publication: Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068635)