A generalized Cheeger inequality

Ioannis Koutis, Gary Miller, Richard Peng

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

The generalized conductance ϕ(G,H) between two weighted graphs G and H on the same vertex set V is defined as the ratio [Formula presented] where capG(S,S¯) is the total weight of the edges crossing from vertex set S⊆V to S¯=V−S. We show that the minimum generalized eigenvalue λ(LG,LH) of the pair of Laplacians LG and LH satisfies ϕ(G,H)≥λ(LG,LH)≥ϕ(G,H)ϕ(G)/16, where ϕ(G) is the standard conductance of G. A generalized cut that meets this bound can be obtained from the generalized eigenvector corresponding to λ(LG,LH).

Original languageEnglish (US)
Pages (from-to)139-152
Number of pages14
JournalLinear Algebra and Its Applications
Volume665
DOIs
StatePublished - May 15 2023
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Keywords

  • Cheeger inequality
  • Generalized cuts
  • Spectral graph theory

Fingerprint

Dive into the research topics of 'A generalized Cheeger inequality'. Together they form a unique fingerprint.

Cite this