Information-Theoretic Cheeger Inequalities

  • Peter Gmeiner (Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany)
A3 01 (Sophus-Lie room)


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.


Special Seminar

Universität Leipzig Felix-Klein-Hörsaal

Katharina Matschke

MPI for Mathematics in the Sciences Contact via Mail

Upcoming Events of this Seminar