A Schur complement Cheeger inequality

DOI10.4230/LIPICS.ITCS.2019.65MaRDI QIDQ5090445FDOQ5090445

Authors: Aaron Schild 

Publication date: 18 July 2022

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

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

zbMATH Keywords

mixing timeconductanceelectrical networksSchur complementsCheeger's inequality

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (5)

• 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 Cheeger-Buser-type inequality on CW complexes

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)