Brouwers Conjecture states that, for any graph $G$, the sum of the $k$ largest (combinatorial) Laplacian eigenvalues of $G$ is at most $|E(G)| + binom{k+1}{2}$, $1 leq k leq n$. We present several interrelated results establishing Brouwers conjecture $text{BC}_k(G)$ for a wide range of graphs $G$ and parameters $k$. In particular, we show that (1) $text{BC}_k(G)$ is true for low-arboricity graphs, and in particular for planar $G$ when $k geq 11$; (2) $text{BC}_k(G)$ is true whenever the variance of the degree sequence is not very high, generalizing previous results for $G$ regular or random; (3) $text{BC}_k(G)$ is true if $G$ belongs to a hereditarily spectrally-bounded class and $k$ is sufficiently large as a function of $k$, in particular $k geq sqrt{32n}$ for bipartite graphs; (4) $text{BC}_k(G)$ holds unless $G$ has edge-edit distance $< k sqrt{2n} = O(n^{3/2})$ from a split graph; (5) no $G$ violates the conjectured upper bound by more than $O(n^{5/4})$, and bipartite $G$ by no more than $O(n)$; and (6) $text{BC}_k(G)$ holds for all $k$ outside an interval of length $O(n^{3/4})$. Furthermore, we present a surprising negative result: asymptotically almost surely, a uniform random signed complete graph violates the conjectured bound by $Omega(n)$.
Download