Find in Library

<pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">For graphs there exists a strong connection between spectral and </span><span style="text-decoration: underline; color: #000000;">combinatorial</span><span style="color: #000000;"> expansion properties. This is expressed, e.g., by the discrete </span><span style="text-decoration: underline; color: #000000;">Cheeger</span><span style="color: #000000;"> inequality, the lower bound of which states that </span><span style="color: #008000;">$\lambda(G) \leq h(G)$</span><span style="color: #000000;">, where </span><span style="color: #008000;">$\lambda(G)$</span><span style="color: #000000;"> is the second smallest eigenvalue of the </span><span style="text-decoration: underline; color: #000000;">Laplacian</span><span style="color: #000000;"> of a graph </span><span style="color: #008000;">$G$</span><span style="color: #000000;"> and </span><span style="color: #008000;">$h(G)$</span><span style="color: #000000;"> is the </span><span style="text-decoration: underline; color: #000000;">Cheeger</span><span style="color: #000000;"> constant measuring the edge expansion of </span><span style="color: #008000;">$G$</span><span style="color: #000000;">. We are interested in generalizations of expansion properties to finite simplicial complexes of higher dimension (or uniform </span><span style="text-decoration: underline; color: #000000;">hypergraphs</span><span style="color: #000000;">).</span></pre><pre style="-qt-paragraph-type: empty; -qt-block-indent: 0; text-indent: 0px; margin: 0px;"> </pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">Whereas higher dimensional </span><span style="text-decoration: underline; color: #000000;">Laplacians</span><span style="color: #000000;"> were introduced already in 1945 by </span><span style="text-decoration: underline; color: #000000;">Eckmann</span><span style="color: #000000;">, the generalization of edge expansion to simplicial complexes is not straightforward. </span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">Recently, a topologically motivated notion analogous to edge expansion that is based on </span><span style="color: #008000;">$\mathbb{Z}_2$</span><span style="color: #000000;">-</span><span style="text-decoration: underline; color: #000000;">cohomology</span><span style="color: #000000;"> was introduced by </span><span style="text-decoration: underline; color: #000000;">Gromov</span><span style="color: #000000;"> and independently by Linial, Meshulam and </span><span style="text-decoration: underline; color: #000000;">Wallach</span><span style="color: #000000;">. It is known that for this generalization there is no direct higher dimensional analogue of the lower bound of the </span><span style="text-decoration: underline; color: #000000;">Cheeger</span><span style="color: #000000;"> inequality.</span></pre><pre style="-qt-paragraph-type: empty; -qt-block-indent: 0; text-indent: 0px; margin: 0px;"> </pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">A different, </span><span style="text-decoration: underline; color: #000000;">combinatorially</span><span style="color: #000000;"> motivated generalization of the </span><span style="text-decoration: underline; color: #000000;">Cheeger</span><span style="color: #000000;"> constant, denoted by </span><span style="color: #008000;">$h(X)$</span><span style="color: #000000;">, was studied by </span><span style="text-decoration: underline; color: #000000;">Parzanchevski</span><span style="color: #000000;">, </span><span style="text-decoration: underline; color: #000000;">Rosenthal</span><span style="color: #000000;"> and </span><span style="text-decoration: underline; color: #000000;">Tessler</span><span style="color: #000000;">. They showed that indeed </span><span style="color: #008000;">$\lambda(X) \leq h(X)$</span><span style="color: #000000;">, where </span><span style="color: #008000;">$\lambda(X)$</span><span style="color: #000000;"> is the smallest non-trivial eigenvalue of the (</span><span style="color: #008000;">$(k-1)$</span><span style="color: #000000;">-dimensional upper) </span><span style="text-decoration: underline; color: #000000;">Laplacian</span><span style="color: #000000;">, for the case of </span><span style="color: #008000;">$k$</span><span style="color: #000000;">-dimensional simplicial complexes </span><span style="color: #008000;">$X$</span><span style="color: #000000;"> with complete </span><span style="color: #008000;">$(k-1)$</span><span style="color: #000000;">-skeleton.</span></pre><pre style="-qt-paragraph-type: empty; -qt-block-indent: 0; text-indent: 0px; margin: 0px;"> </pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">Whether this inequality also holds for </span><span style="color: #008000;">$k$</span><span style="color: #000000;">-dimensional complexes with non-com</span><span style="color: #800000;">\-plete</span><span style="color: #008000;">$(k-1)$</span><span style="color: #000000;">-skeleton has been an open question.</span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">We give two proofs of the inequality for arbitrary complexes. The proofs differ strongly in the methods and structures employed,</span></pre><pre style="-qt-block-indent: 0; text-indent: 0px; margin: 0px;"><span style="color: #000000;">and each allows for a different kind of additional strengthening of the original result.</span></pre>