Combinatorial Cheeger inequalities for a graph relate a combinatorial Cheeger constant with the spectral gap of the graph. Some of these isoperimetric inequalities can also be generalized to hypergraphs or simplicial complexes. We present an information-theoretic version of such inequalities for graphs and simplicial complexes by introducing information-theoretic Cheeger constants. For this we use the Kullback-Leibler divergence between corresponding hierarchical models

as an information measure between different simplicial complexes and derive upper and lower bounds for this information measure. Finally we can relate the information-theoretic Cheeger constants with the spectral gap of simplicial complexes.

## Authors

## Algebraic Topology and Information Theory

## Keywords

Tags: combinatorial cheeger inequality, exponential family, Graph theory, hierarchical model, information theory, kullback-leibler divergence, probability theory, simplicial complex, undirected graph

Photos by : ASA Goddard Space Flight Center