Brouwer's Conjecture on Graph Laplacians

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $G=(V,E)$ be a finite simple undirected graph with $n=|V|\ge1$ and $m=|E|$. Its adjacency matrix is $A$, its diagonal degree matrix is $D$, and its combinatorial Laplacian is $L=D-A$. Order the real eigenvalues as $\lambda_1\ge\cdots\ge\lambda_n=0$, counting multiplicity.

Statement recorded in the supplied source.

For every such graph $G$ and every integer $k$ with $1\le k\le n$, is \[ \sum_{i=1}^k\lambda_i\le m+\binom{k+1}{2}? \] [S2]

Short English statement

Is the sum of any k largest graph Laplacian eigenvalues at most the number of edges plus $k(k+1)/2$?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1388 (GRAPH-001). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Joshua N. Cooper, Constraints on Brouwer's Laplacian Spectrum Conjecture (2020), arXiv:2003.03447v1, Section 1, equation (1), pp. 1--2. https://arxiv.org/abs/2003.03447v1.