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.
Algebraic Topology and Information Theory
Photos by : ASA Goddard Space Flight Center