A Generalized Cheeger Inequality

2014/10/22 by Koutis, Ioannis, Miller, Gary, Peng, Richard
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1412.6075

Abstract

The generalized conductance ϕ(G,H) between two graphs G and H on the same vertex set V is defined as the ratio ϕ(G,H) = min_{S⊆ V} \fraccap_G(S,S) cap_H(S,S), where cap_G(S,S) is the total weight of the edges crossing from S to S=V-S. We show that the minimum generalized eigenvalue λ(L_G,L_H) of the pair of Laplacians L_G and L_H satisfies λ(L_G,L_H) ≥ ϕ(G,H) ϕ(G)/8, where ϕ(G) is the usual conductance of G. A generalized cut that meets this bound can be obtained from the generalized eigenvector corresponding to λ(L_G,L_H). The inequality complements a recent proof that ϕ(G) cannot be replaced by Θ(ϕ(G,H)) in the above inequality, unless the Unique Games Conjecture is false.

Related

• A Schur Complement Cheeger Inequality
• Finding Cheeger Cuts in Hypergraphs via Heat Equation
• Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues
• A Cheeger Inequality for Size-Specific Conductance
• A linear k-fold Cheeger inequality