The Cheeger Inequality and Coboundary Expansion: Beyond Constant Coefficients

Understand

The Cheeger constant of a graph, or equivalently its coboundary expansion, quantifies the expansion of the graph.

• This notion assumes an implicit choice of a coefficient group, namely, $\mathbb{F}_2$.
• In this paper, we study Cheeger-type inequalities for graphs endowed with a generalized coefficient group, called a sheaf; this is motivated by applications to cosystolic expansion and locally testable codes.
• We prove that a graph is a good spectral expander if and only if it has good coboundary expansion relative to any (resp.