Higher-Order Cheeger Inequality for Partitioning with Buffers

Understand

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 \subseteq V$ with a buffer $B \subseteq V \setminus S$ is the edge expansion of $S$ after removing all the edges from set $S$ to its buffer $B$.
• An $\varepsilon$-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 $P_i$: $|B_i| \le \varepsilon |P_i|$.