A Cheeger Inequality for Hypergraphs and Its Applications
Abstract
Hypergraphs provide a natural framework for modeling higher-order relationships, but the development of spectral techniques with provable guarantees for general non-uniform hypergraphs remains challenging. Building on Banerjee's normalized adjacency matrix and Spiro's averaging-based diffusion framework, we develop a spectral framework for non-uniform hypergraphs and establish Cheeger's inequality for their conductance. A fundamental result in the spectral theory of hypergraphs asserts that, for every non-covering hypergraph, the second-smallest eigenvalue of its normalized Laplacian is at most one. This spectral characterization yields an improved Cheeger's inequality for non-covering hypergraphs, and we show that the resulting inequality is tight on both sides using cycle and cube hypergraphs. Our framework further yields higher-order Cheeger inequalities and provides theoretical guarantees for Fiedler's spectral partitioning algorithm, all in the setting of hypergraphs. Finally and most notably, we construct a new family of optimal hypergraph expanders that is tight for the Alon--Boppana bound.
Related
- A sharp higher-order Cheeger inequality
- Perfect matchings in hypergraphs and Feige's inequality
- Towards the Erdős matching conjecture for 4‐uniform hypergraphs: Stability and applications
- Choquet-type extensions of set-pair functions, and applications in graph limits, hypergraphs, and metric measure spaces
- The reverse Hölder inequality for 𝒜p(·) weights with applications to matrix weights
BibTeX
@misc{kamal2026cheeger,
title = {{A Cheeger Inequality for Hypergraphs and Its Applications}},
author = {Raj Kamal and Amitabha Bagchi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.16286},
eprint = {2609.16286},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16286},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Cheeger Inequality for Hypergraphs and Its Applications
AU - Raj Kamal
AU - Amitabha Bagchi
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.16286
UR - https://arxiv.org/abs/2609.16286
AB - Hypergraphs provide a natural framework for modeling higher-order relationships, but the development of spectral techniques with provable guarantees for general non-uniform hypergraphs remains challenging. Building on Banerjee's normalized adjacency matrix and Spiro's averaging-based diffusion framework, we develop a spectral framework for non-uniform hypergraphs and establish Cheeger's inequality for their conductance. A fundamental result in the spectral theory of hypergraphs asserts that, for every non-covering hypergraph, the second-smallest eigenvalue of its normalized Laplacian is at most one. This spectral characterization yields an improved Cheeger's inequality for non-covering hypergraphs, and we show that the resulting inequality is tight on both sides using cycle and cube hypergraphs. Our framework further yields higher-order Cheeger inequalities and provides theoretical guarantees for Fiedler's spectral partitioning algorithm, all in the setting of hypergraphs. Finally and most notably, we construct a new family of optimal hypergraph expanders that is tight for the Alon--Boppana bound.
ER -