An approximate version of Brouwer's Laplacian conjecture
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914277770657792 |
|---|---|
| author | Lew, Alan |
| author_facet | Lew, Alan |
| contents | Let $G=(V,E)$ be an $n$-vertex graph, $L(G)\in \mathbb{R}^{n\times n}$ its Laplacian matrix, and let $λ_1(L(G))\ge λ_2(L(G))\ge \cdots\ge λ_n(L(G))=0$ denote its eigenvalues. For $1\le k\le n$, let $\varepsilon_k(G)= \sum_{i=1}^k λ_i(L(G)) -|E|$. We show that for every $1\le k\le n$, \[
\varepsilon_k(G) \le \max_{U\subset V,\, |U|=k} |E_G(U)| + (4k-2)\sqrt{k}, \] where $E_G(U)$ is the set of edges of $G$ contained in $U$. As an immediate consequence, we obtain that $\varepsilon_k(G)\le \binom{k}{2}+(4k-2)\sqrt{k}$. This improves upon previously known bounds for large values of $k$, and may be seen as an approximate version of a conjecture of Brouwer, stating that $\varepsilon_k(G)\le \binom{k+1}{2}$ for every graph $G$. Moreover, for every $r\ge 2$, if $G$ is a $K_{r+1}$-free graph, we obtain that $\varepsilon_k(G)\le (1-1/r)k^2/2 + (4k-2)\sqrt{k}$, which is tight up to the sub-quadratic term.
Our arguments rely on the study of the largest eigenvalue of a matrix obtained by performing a certain diagonal perturbation on the $k$-th additive compound matrix of $L(G)$. Using similar methods, we show that the largest Laplacian eigenvalue of the $k$-th token graph of a graph $G=(V,E)$ is bounded from above by $|E|+4k-2$, obtaining a weak version of a conjecture of Apte, Parekh, and Sud, which predicts that an upper bound of $|E|+k$ should hold. All our results also hold, with essentially the same proofs, when the Laplacian matrix is replaced by the signless Laplacian of the graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_17575 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An approximate version of Brouwer's Laplacian conjecture Lew, Alan Combinatorics Let $G=(V,E)$ be an $n$-vertex graph, $L(G)\in \mathbb{R}^{n\times n}$ its Laplacian matrix, and let $λ_1(L(G))\ge λ_2(L(G))\ge \cdots\ge λ_n(L(G))=0$ denote its eigenvalues. For $1\le k\le n$, let $\varepsilon_k(G)= \sum_{i=1}^k λ_i(L(G)) -|E|$. We show that for every $1\le k\le n$, \[ \varepsilon_k(G) \le \max_{U\subset V,\, |U|=k} |E_G(U)| + (4k-2)\sqrt{k}, \] where $E_G(U)$ is the set of edges of $G$ contained in $U$. As an immediate consequence, we obtain that $\varepsilon_k(G)\le \binom{k}{2}+(4k-2)\sqrt{k}$. This improves upon previously known bounds for large values of $k$, and may be seen as an approximate version of a conjecture of Brouwer, stating that $\varepsilon_k(G)\le \binom{k+1}{2}$ for every graph $G$. Moreover, for every $r\ge 2$, if $G$ is a $K_{r+1}$-free graph, we obtain that $\varepsilon_k(G)\le (1-1/r)k^2/2 + (4k-2)\sqrt{k}$, which is tight up to the sub-quadratic term. Our arguments rely on the study of the largest eigenvalue of a matrix obtained by performing a certain diagonal perturbation on the $k$-th additive compound matrix of $L(G)$. Using similar methods, we show that the largest Laplacian eigenvalue of the $k$-th token graph of a graph $G=(V,E)$ is bounded from above by $|E|+4k-2$, obtaining a weak version of a conjecture of Apte, Parekh, and Sud, which predicts that an upper bound of $|E|+k$ should hold. All our results also hold, with essentially the same proofs, when the Laplacian matrix is replaced by the signless Laplacian of the graph. |
| title | An approximate version of Brouwer's Laplacian conjecture |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2601.17575 |