A Schur Complement Cheeger Inequality

DOI10.4230/LIPICS.ITCS.2019.65MaRDI QIDQ6310271arXivFDO

Publication date 27 November 2018

Abstract: Cheeger's inequality shows that any undirected graph

G

with minimum nonzero normalized Laplacian eigenvalue

l a m b d a_{G}

has a cut with conductance at most

O (s q r t l a m b d a_{G})

. Qualitatively, Cheeger's inequality says that if the relaxation time of a graph is high, there is a cut that certifies this. However, there is a gap in this relationship, as cuts can have conductance as low as

T h e t a (l a m b d a_{G})

. To better approximate the relaxation time of a graph, we consider a more general object. Instead of bounding the mixing time with cuts, we bound it with cuts in graphs obtained by Schur complementing out vertices from the graph

G

. Combinatorially, these Schur complements describe random walks in

G

restricted to a subset of its vertices. As a result, all Schur complement cuts have conductance at least

O m e g a (l a m b d a_{G})

. We show that unlike with cuts, this inequality is tight up to a constant factor. Specifically, there is a Schur complement cut with conductance at most

O (l a m b d a_{G})

.

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 Q6310271)