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

DOI10.1137/070709529zbMath1227.05225OpenAlexW2024428102WikidataQ105584148 ScholiaQ105584148MaRDI QIDQ3068635

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

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

quasi-random graphsLaplacian eigenvaluesregular partitionGrothendieck's inequalityregularity Lemma

Mathematics Subject Classification ID

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

Related Items

Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ Regularity-based spectral clustering and mapping the Fiedler-carpet ⋮ A Note on Even Cycles and Quasirandom Tournaments ⋮ A unified view of graph regularity via matrix decompositions ⋮ Matrix and discrepancy view of generalized random and quasirandom graphs ⋮ Average Gromov hyperbolicity and the Parisi ansatz ⋮ Extremal results in sparse pseudorandom graphs ⋮ On the KŁR conjecture in random graphs ⋮ Beyond the expanders ⋮ Quasirandom Cayley graphs ⋮ Discrepancy minimizing spectral clustering ⋮ A weighted regularity lemma with applications ⋮ Unnamed Item ⋮ Modularity spectra, eigen-subspaces, and structure of weighted graphs ⋮ Generalized quasirandom properties of expanding graph sequences ⋮ Discrepancy and eigenvalues of Cayley graphs ⋮ The poset of hypergraph quasirandomness ⋮ Relating multiway discrepancy and singular values of nonnegative rectangular matrices