Hermitian matrices and graphs: Singular values and discrepancy

DOI10.1016/j.disc.2004.05.006zbMath1050.05082OpenAlexW2092642948MaRDI QIDQ1877646

Vladimir Nikiforov, Béla Bollobás

Publication date: 19 August 2004

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2004.05.006

zbMATH Keywords

DiscrepancyGraph eigenvaluesPseudo-random graphsQuasi-random graphsSecond singular value

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Hermitian, skew-Hermitian, and related matrices (15B57)

Related Items

Sharp spectral bounds of several graph parameters using eigenvector norms ⋮ Regularity-based spectral clustering and mapping the Fiedler-carpet ⋮ Using discrepancy to control singular values for nonnegative matrices ⋮ From quasirandom graphs to graph limits and graphlets ⋮ SVD, discrepancy, and regular structure of contingency tables ⋮ Discrepancy inequalities for directed graphs ⋮ Matrix and discrepancy view of generalized random and quasirandom graphs ⋮ Quasirandom Groups ⋮ Discrete norms of a matrix and the converse to the expander mixing lemma ⋮ Quasirandom Cayley graphs ⋮ A NOTE ON THE WEISS CONJECTURE ⋮ Discrepancy minimizing spectral clustering ⋮ Relating multiway discrepancy and singular values of nonnegative rectangular matrices

Cites Work

• Sparse quasi-random graphs
• Dense expanders and pseudo-random bipartite graphs
• On Character Sums and Primitive Roots^†
• Matrix Analysis
• An Extremal Problem of Graphs with Diameter 2
• Quasi-random graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item