Laplacian eigenvalues of independence complexes via additive compound matrices

Abstract

The independence complex of a graph $G=(V,E)$ is the simplicial complex $I(G)$ on vertex set $V$ whose simplices are the independent sets in $G$. We present new lower bounds on the eigenvalues of the $k$-dimensional Laplacian $L_k(I(G))$ in terms of the eigenvalues of the graph Laplacian $L(G)$. As a consequence, we show that for all $k\ge 0$, the dimension of the $k$-th reduced homology group (with real coefficients) of $I(G)$ is at most \[ \left| \left\{ 1\leq i_1<\cdots<i_{k+1}\leq |V| : \, λ_{i_1}+λ_{i_2}+\cdots+λ_{i_{k+1}} \geq |V|\right\}\right|,\] where $\hat{I}{»}_1\ge \hat{I}{»}_2\ge \cdots \ge \hat{I}{»}_{|V|}=0$ are the eigenvalues of $L(G)$. In particular, if $k$ is the minimal number such that the sum of the $k$ largest eigenvalues of $L(G)$ is at least $|V|$, then ${\tilde{H}}_i(I(G);\mathbb{R})=0$ for all $i\le k-2$. This extends previous results by Aharoni, Berger and Meshulam. Our proof relies on a relation between the $k$-dimensional Laplacian $L_k(I(G))$ and the $(k+1)$-th additive compound matrix of $L_0(I(G))$, which is an $\left(\genfrac{}{}{0ex}{}{n}{k+1}\right)\times \left(\genfrac{}{}{0ex}{}{n}{k+1}\right)$ matrix whose eigenvalues are all the possible sums of $k+1$ eigenvalues of the $0$-dimensional Laplacian. Our results apply also in the more general setting of vertex-weighted Laplacian matrices.