Laplacian eigenvalues of independence complexes via additive compound matrices

Laplacian eigenvalues of independence complexes via additive compound matrices, Discrete Analysis 2024:15, 17 pp.

The (Laplacian) spectral gap of a graph, defined as the second smallest eigenvalue of the graph’s Laplacian matrix, is an important parameter that in some sense measures how well connected the graph is.

An important paper of Garland from 1973 relates spectral gaps of graphs to topological properties of simplicial complexes. Roughly what it shows is that if \(X\) is a pure \(d\)-dimensional simplicial complex with \(d\geq k+1\), and if for every \((k-1)\)-simplex \(S\) in \(X\) the 1-skeleton of the link of \(S\) (that is, the simplicial complex that consists of all simplices \(T\) disjoint from \(S\) with \(S\cup T\in X\)) has a sufficiently large spectral gap, then the \(k\)th cohomology group \(\tilde H^k(X,\mathbb R)\) vanishes.

The condition that every single link graph has a large spectral gap is quite strong. In 2003, Aharoni, Berger and Meshulam showed that a different and more global condition suffices when \(X\) is the flag complex of a graph \(G\) – that is, the simplicial complex consisting of all sets of vertices of \(G\) that span a clique. A consequence of their result is that \(\tilde H^k(X,\mathbb R)\) vanishes if the spectral gap of \(G\) is greater than \(nk/(k+1)\). They obtain this bound by defining for each \(k\) a \(k\)-dimensional Laplacian operator and bounding its smallest eigenvalue in terms of that of the \((k-1)\)-dimensional Laplacian.

From their result one can deduce corresponding conditions for the vanishing of cohomology for the independence complex, which is just the complex of sets of vertices that span independent sets. This paper generalizes the work of Aharoni, Berger and Meshulam, yielding a stronger result for independence complexes that takes into account not just the second eigenvalue of the Laplacian, but also other eigenvalues (in fact, sums of eigenvalues). As an application, two bounds are given using fractional domination and packing parameters – one on the rank below which the cohomology vanishes and one of the size of cohomology.

The technique that is used for proving the main theorem is to bound the eigenvalues of the \(k\)th Laplacian of the independence complex by relating them to eigenvalues of so-called additive compound matrices. If \(V\) is a vector space and \(M\) is a linear map from \(V\) to \(V\), then the \(k\)th additive compound \(M^{[k]}\) of \(M\) maps \(\Lambda^kV\) to \(\Lambda^kV\), taking \(v_1\wedge\dots\wedge v_k\) to \(\sum_{i=1}^k v_1\wedge\dots\wedge v_{i-1}\wedge Mv_i\wedge v_{i+1}\wedge\dots\wedge v_k\). It can be shown that the eigenvalues of \(M^{[k]}\) are all possible sums of distinct eigenvalues of \(M\).