{"id":"arxiv/2601.17575","url":"https://arxiv.org/abs/2601.17575","tags":["math.CO"],"score":0,"title":"An approximate version of Brouwer's Laplacian conjecture","domain":"math.CO","source":"arxiv","authors":["Alan Lew"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-24","reactions":{}}