A linear Cheeger inequality using eigenvector norms

DOI10.4310/JOC.2015.V6.N3.A2MaRDI QIDQ746827zbMATH OpenFDO

Authors Franklin Kenter

Publication date 20 October 2015

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.3195

zbMATH Keywords

Cheeger constantgraph Laplaciangraph partitioningspectral graph theory

Mathematics Subject Classification ID

Connectivity (05C40) 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)

Abstract: The Cheeger constant, $h_G$, is a measure of expansion within a graph. The classical Cheeger Inequality states: $lambd{a}_1/2le{h}_{G}lesqrt2lambd{a}_1$ where $lambd{a}_1$ is the first nontrivial eigenvalue of the normalized Laplacian matrix. Hence, $h_G$ is tightly controlled by $lambd{a}_1$ to within a quadratic factor. We give an alternative Cheeger Inequality where we consider the $infty$-norm of the corresponding eigenvector in addition to $lambd{a}_1$. This inequality controls $h_G$ to within a linear factor of $lambd{a}_1$ thereby providing an improvement to the previous quadratic bounds. An additional advantage of our result is that while the original Cheeger constant makes it clear that $h_{G}o0$ as $lambd{a}_{1}o0$, our result shows that $h_{G}o1/2$ as $lambd{a}_{1}o1$.

Recommendations

• scientific article; zbMATH DE number 878889
• The first two largest eigenvalues of Laplacian, spectral gap problem and Cheeger constant of graphs
• scientific article; zbMATH DE number 475374
• Higher Dimensional Cheeger Inequalities
• Cheeger‐like inequalities for the largest eigenvalue of the graph Laplace operator

Cited in

(1)

• scientific article; zbMATH DE number 878889 (Why is no real title available?)

This page was built for publication: A linear Cheeger inequality using eigenvector norms

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