×

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
PDF BibTeX XML Cite
Full Text: DOI arXiv