Higher-Order Cheeger Inequality for Partitioning with Buffers

We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a graph G = (V, E). The buffered expansion of a set S ⊆ V with a buffer B ⊆ V S is the edge expansion of S after removing all the edges from set S to its buffer B. An ε-buffered k-partitioning is a partitioning of a graph into disjoint components P i and buffers B i , in which the size of buffer B i for P i is small relative to the size of

The buffered expansion of a buffered partition is the maximum of buffered expansions of the k sets P i with buffers B i . Let h k,ε G be the buffered expansion of the optimal ε-buffered k-partitioning, then for every δ > 0,

where λ ⌊(1+δ)k⌋ is the ⌊(1 + δ)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, and a novel generalization to the setting with arbitrary vertex weights and edge costs. 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.