A generalized Cheeger inequality

DOI10.1016/J.LAA.2023.01.014MaRDI QIDQ2693705zbMATH OpenOpenAlexFDO

Authors Ioannis Koutis, Richard Peng, Gary L. Miller

Publication date 24 March 2023

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

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

zbMATH Keywords

spectral graph theoryCheeger inequalitygeneralized cuts

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Inequalities involving eigenvalues and eigenvectors (15A42) Signed and weighted graphs (05C22)

Recommendations

• A Cheeger cut for uniform hypergraphs
• Many sparse cuts via higher eigenvalues
• Algorithmic extensions of Cheeger's inequality to higher eigenvalues and partitions
• Weighted graph Laplacians and isoperimetric inequalities
• scientific article; zbMATH DE number 878889

Cites work

• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Eigenvalues and expanders
• Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
• Isoperimetric inequalities and transient random walks on graphs
• Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
• On Cheeger inequalities of a graph
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(8)

• scientific article; zbMATH DE number 5224582 (Why is no real title available?)
• A Cheeger cut for uniform hypergraphs
• Cheeger inequalities for general edge-weighted directed graphs
• Higher dimensional discrete Cheeger inequalities
• Higher Dimensional Cheeger Inequalities
• scientific article; zbMATH DE number 2206791 (Why is no real title available?)
• A Schur complement Cheeger inequality
• On a class of Cheeger inequalities

This page was built for publication: A generalized Cheeger inequality

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