Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Free, publiclyaccessible full text available June 24, 2025

We prove a new generalization of the higherorder 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 kpartitioning 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 ≤ εP_i. 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 kpartitioning, then for every δ>0, h^{k,ε}_G ≤ O(1)⋅(log k) ⋅λ_{⌊(1+δ)k⌋} / ε, where λ_{⌊(1+δ)k⌋} is the ⌊(1+δ)k⌋th smallest eigenvalue of the normalized Laplacian of G. Our inequality is constructive and avoids the ``squareroot 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 higherorder Cheeger inequalities and another recent Cheegertype inequality by Kwok, Lau, and Lee (2017) involving robust vertex expansion.more » « lessFree, publiclyaccessible full text available January 1, 2025

We prove a new generalization of the higherorder 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 kpartitioning is a partitioning of a graph into disjoint components Pi and buffers Bi, in which the size of buffer Bi for Pi is small relative to the size of Pi: Bi≤εPi. The buffered expansion of a buffered partition is the maximum of buffered expansions of the k sets Pi with buffers Bi. Let hk,εG be the buffered expansion of the optimal εbuffered kpartitioning, then for every δ>0, hk,εG≤Oδ(1)⋅(logkε)⋅λ⌊(1+δ)k⌋, where λ⌊(1+δ)k⌋ is the ⌊(1+δ)k⌋th smallest eigenvalue of the normalized Laplacian of G. Our inequality is constructive and avoids the ``squareroot 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 higherorder Cheeger inequalities and another recent Cheegertype inequality by Kwok, Lau, and Lee (2017) involving robust vertex expansion.more » « lessFree, publiclyaccessible full text available January 1, 2025

Free, publiclyaccessible full text available January 1, 2025