Sharp spectral bounds of several graph parameters using eigenvector norms

DOI10.1016/j.laa.2016.03.026zbMath1338.05163OpenAlexW2329875035MaRDI QIDQ286136

Franklin H. J. Kenter

Publication date: 20 May 2016

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.laa.2016.03.026

zbMATH Keywords

maximum cutspectral graph theory3-way maximum cutdensest subgraphexpander mixing lemma

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Inequalities involving eigenvalues and eigenvectors (15A42)

Cites Work

• From quasirandom graphs to graph limits and graphlets
• Discrepancy inequalities for directed graphs
• Using discrepancy to control singular values for nonnegative matrices
• Lifts, discrepancy and nearly optimal spectral gap
• Explicit construction of linear sized tolerant networks
• Hermitian matrices and graphs: Singular values and discrepancy
• The dual Cheeger constant and spectra of infinite graphs
• Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• Max Cut and the Smallest Eigenvalue
• Some optimal inapproximability results
• The dense \(k\)-subgraph problem
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Sharp spectral bounds of several graph parameters using eigenvector norms