Liren Shan: Higher-Order Cheeger Inequality for Partitioning with Buffers

PASSCODE: 728726

We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a d-regular graph G=(V,E). The buffered expansion of a set S, a subset of V, with a buffer B, a subset of V\S, is the edge expansion of S after removing all the edges from set S to its buffer B. An epsilon-buffered k-partitioning is a partitioning of a graph into components Pi and buffers Bi, in which the size of buffer Bi for Pi is small relative to the size of Pi: |Bi| <= epsilon*|Pi|; all sets Pi are disjoint but buffers Bi may overlap.

The buffered expansion of a buffered partition is the maximum of buffered expansions of the k sets Pi with buffers Bi. Let h_G^{k,epsilon} be the buffered expansion of the optimal epsilon-buffered k-partitioning, then for every delta>0,
h_G^{k,epsilon} <= O_delta( logk / epsilon ) * lambda_{(1+\delta)k},
where lambda_{(1+delta)k} is the (1+delta)k -th smallest eigenvalue of the normalized Laplacian of G.

Our inequality is constructive and avoids the “square-root loss” that is present in the standard Cheeger inequalities (even for k=2). We also provide a complementary lower bound. Moreover our result implies and generalizes the standard higher-order Cheeger inequalities and another recent Cheeger-type inequality by Kwok, Lau, and Lee (2017) involving robust vertex expansion.