# zbMATH — the first resource for mathematics

Higher dimensional discrete Cheeger inequalities. (English) Zbl 1405.05101
Summary: For graphs there exists a strong connection between spectral and combinatorial expansion properties. This is expressed, e.g., by the discrete Cheeger inequality, the lower bound of which states that $$\lambda(G)\leq h(G)$$, where $$\lambda(G)$$ is the second smallest eigenvalue of the Laplacian of a graph $$G$$ and $$h(G)$$ is the Cheeger constant measuring the edge expansion of $$G$$. We are interested in generalizations of expansion properties to finite simplicial complexes of higher dimension (or uniform hypergraphs).
Whereas higher dimensional Laplacians were introduced already in 1945 by B. Eckmann [Comment. Math. Helv. 17, 240–255 (1945; Zbl 0061.41106)], the generalization of edge expansion to simplicial complexes is not straightforward. Recently, a topologically motivated notion analogous to edge expansion that is based on $$\mathbb{Z}_2$$-cohomology was introduced by M. Gromov [Geom. Funct. Anal. 19, No. 3, 743–841 (2009; Zbl 1195.58010)] and independently by N. Linial and R. Meshulam [Combinatorica 26, No. 4, 475–487 (2006; Zbl 1121.55013)] and R. Meshulam and N. Wallach [Random Struct. Algorithms 34, No. 3, 408–417 (2009; Zbl 1177.55011)] and by I. Newman and Y. Rabinovich [SIAM J. Comput. 42, No. 3, 855–883 (2013; Zbl 1281.28006)]. It is known that for this generalization there is no higher dimensional analogue of the lower bound of the Cheeger inequality.
A different, combinatorially motivated generalization of the Cheeger constant, denoted by $$h(X)$$, was studied by O. Parzanchevski et al. [Combinatorica 36, No. 2, 195–227 (2016; Zbl 1389.05174)]. They showed that indeed $$\lambda(X)\leq h(X)$$, where $$\lambda(X)$$ is the smallest non-trivial eigenvalue of the ($$(k-1)$$-dimensional upper) Laplacian, for the case of $$k$$-dimensional simplicial complexes $$X$$ with complete $$(k-1)$$-skeleton.
Whether this inequality also holds for $$k$$-dimensional complexes with non-complete $$(k-1)$$-skeleton has been an open question. We give two proofs of the inequality for arbitrary complexes. The proofs differ strongly in the methods and structures employed, and each allows for a different kind of additional strengthening of the original result.

##### MSC:
 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C65 Hypergraphs 05E45 Combinatorial aspects of simplicial complexes
Full Text: