A Schur complement Cheeger inequality

DOI10.4230/LIPICS.ITCS.2019.65MaRDI QIDQ5090445zbMATH OpenFDO

Authors Aaron Schild

Publication date 18 July 2022

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

zbMATH Keywords

mixing timeconductanceelectrical networksSchur complementsCheeger's inequality

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• A generalized Cheeger inequality
• Laplacians and the Cheeger inequality for directed graphs
• Random walks and local cuts in graphs
• Finding Cheeger cuts in hypergraphs via heat equation
• Many sparse cuts via higher eigenvalues

Cites work

• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• A Cheeger Inequality for the Graph Connection Laplacian
• A semidefinite bound for mixing rates of Markov chains
• Fast generation of random spanning trees and the effective resistance metric
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
• Many sparse cuts via higher eigenvalues
• Metric uniformization and spectral bounds for graphs
• Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
• The electrical resistance of a graph captures its commute and cover times
• Unranking and ranking spanning trees of a graph

Cited in

(6)

• A Cheeger-Buser-type inequality on CW complexes
• Random walks, conductance, and resistance for the connection graph Laplacian
• Refining schur's inequality using schur complements
• The invisible hand of Laplace: the role of market structure in price convergence and oscillation
• A matrix inequality on Schur complements
• A Schur Complement Cheeger Inequality

This page was built for publication: A Schur complement Cheeger inequality

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