The Cheeger Inequality and Coboundary Expansion: Beyond Constant Coefficients
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910919508885504 |
|---|---|
| author | First, Uriya A. Kaufman, Tali |
| author_facet | First, Uriya A. Kaufman, Tali |
| contents | 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. some) constant sheaf, or equivalently, relative to any `ordinary' coefficient group. We moreover show that sheaves that are close to being constant in a well-defined sense are also good coboundary expanders, provided that their underlying graph is an expander, thus giving the first example of good coboundary expansion in non-cosntant sheaves on sparse graphs. By contrast, we observe that for general sheaves on graphs, it is impossible to relate the expansion of the graph and the coboundary expansion of the sheaf.
We specialize our results to sheaves on (finite) spherical buildings. Specifically, we show that the normalized second eigenvalue of the (weighted) graph underlying a $q$-thick $d$-dimensional spherical building is $O(\frac{1}{\sqrt{q}-3d})$ if $q>9d^2$. Plugging this into our results about coboundary expansion gives explicit lower bounds on the coboundary expansion of some constant and non-constant sheaves on spherical buildings; for a fixed dimension $d$, the bounds approach a constant as the thickness $q$ grows.
Along the way, we prove a new version of the Expander Mixing Lemma for $r$-partite weighted graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_01776 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The Cheeger Inequality and Coboundary Expansion: Beyond Constant Coefficients First, Uriya A. Kaufman, Tali Combinatorics Computational Complexity 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. some) constant sheaf, or equivalently, relative to any `ordinary' coefficient group. We moreover show that sheaves that are close to being constant in a well-defined sense are also good coboundary expanders, provided that their underlying graph is an expander, thus giving the first example of good coboundary expansion in non-cosntant sheaves on sparse graphs. By contrast, we observe that for general sheaves on graphs, it is impossible to relate the expansion of the graph and the coboundary expansion of the sheaf. We specialize our results to sheaves on (finite) spherical buildings. Specifically, we show that the normalized second eigenvalue of the (weighted) graph underlying a $q$-thick $d$-dimensional spherical building is $O(\frac{1}{\sqrt{q}-3d})$ if $q>9d^2$. Plugging this into our results about coboundary expansion gives explicit lower bounds on the coboundary expansion of some constant and non-constant sheaves on spherical buildings; for a fixed dimension $d$, the bounds approach a constant as the thickness $q$ grows. Along the way, we prove a new version of the Expander Mixing Lemma for $r$-partite weighted graphs. |
| title | The Cheeger Inequality and Coboundary Expansion: Beyond Constant Coefficients |
| topic | Combinatorics Computational Complexity |
| url | https://arxiv.org/abs/2208.01776 |