Sums of Laplacian eigenvalues and sums of degrees

Abstract

Let $X$ be a simplicial complex. For $1\le i\le \dim (X)$, let $X(i)$ be the set of $i$-dimensional faces of $X$, and let $f_i(X)=|X(i)|$. For $0\le i\le \dim (X)-1$, let $L_i^{+}(X)$ be the $i$-th upper Laplacian operator of $X$. For $\sigma \in X$ and $1\le r\le \dim (X)$, we denote by ${\text{deg}}_X^{(r)}(\sigma )$ the number of $r$-dimensional faces of $X$ containing $\sigma$. For a symmetric matrix $M\in {\mathbb{R}}^{n\times n}$ and $1\le i\le n$, let ${\lambda }_i(M)$ be the $i$-th largest eigenvalue of $M$. We prove that for every complex $X$, $1\le r\le \dim (X)$, and $1\le k\le f_{r-1}(X)/(r+1)$, \[ \sum_{i=1}^k λ_i(L_{r-1}^+(X)) \le \max \left\{ \sum_{σ\in A} \text{deg}_X^{(r)}(σ) :\, A\subset X(r-1),\, |A|=(r+1)k \right\}. \] This bound is sharp, and it extends a classical result of Anderson and Morley, corresponding to the special case $k=1,r=1$. As a consequence, we show that for all $1\le r\le \dim (X)$ and $1\le k\le f_{r-1}(X)$, \[ \sum_{i=1}^{k} λ_i(L_{r-1}^+(X)) \le f_r(X) + \binom{(r+1)k}{2}. \] In the case $r=1$, we obtain the following improved bound: for every $k\ge 1$ and every graph $G=(V,E)$ with $|V|\ge k$, \[ \sum_{i=1}^k λ_i(L(G)) \leq |E|+k^2, \] where $L(G)=L_0^{+}(G)$ is the Laplacian matrix of $G$. This improves upon previously known bounds for all $k\ge 3$, and may be seen as a further step towards Brouwer's conjecture, which states that ${\sum }_{i=1}^k{\lambda }_i(L(G))\le |E|+\left(\genfrac{}{}{0ex}{}{k+1}{2}\right).$ As an additional application, we show that if $X$ is an $(r+1)$-partite $r$-dimensional simplicial complex on vertex set $V$, and $1\le k\le f_{r-1}(X)$, then \[ \sum_{i=1}^{k} λ_i(L_{r-1}^+(X)) \le \sum_{i=1}^k \left|\{v\in V:\, \text{deg}^{(r)}_X(v)\ge i\}\right|. \] This resolves a special case of a conjecture of Duval and Reiner, which states that the above inequality holds for all simplicial complexes.