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

Laplacian eigenvaluesregular partitionGrothendieck's inequalityregularity Lemmaquasi-random graphs

Mathematics Subject Classification ID

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

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