Sharp spectral bounds of several graph parameters using eigenvector norms

DOI10.1016/J.LAA.2016.03.026MaRDI QIDQ286136zbMATH OpenOpenAlexFDO

Authors Franklin 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

spectral graph theorydensest subgraph3-way maximum cutexpander mixing lemmamaximum cut

Mathematics Subject Classification ID

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

Recommendations

• Tighter spectral bounds for the cut size, based on Laplacian eigenvectors
• scientific article; zbMATH DE number 1189239
• A class of spectral bounds for max \(k\)-cut
• Many sparse cuts via higher eigenvalues
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs

Cites work

• scientific article; zbMATH DE number 54139 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• Discrepancy inequalities for directed graphs
• Explicit construction of linear sized tolerant networks
• From quasirandom graphs to graph limits and graphlets
• Hermitian matrices and graphs: Singular values and discrepancy
• Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning
• Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
• Lifts, discrepancy and nearly optimal spectral gap
• Max cut and the smallest eigenvalue
• Some optimal inapproximability results
• The dense \(k\)-subgraph problem
• The dual Cheeger constant and spectra of infinite graphs
• Using discrepancy to control singular values for nonnegative matrices

Cited in

(3)

• A unified framework for the expander mixing lemma for irregular graphs and its applications
• On the sharpness of spectral estimates for graph Laplacians
• Sharp bounds on random walk eigenvalues via spectral embedding

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

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