IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Around the Brouwer Conjecture

  • Feb. 7, 2020
  • 2:30 p.m.

Abstract

We discuss the Brouwer Conjecture ("BC"), which says that, for $k = 1$ to $n$, the sum of the $k$ largest (combinatorial) Laplacian eigenvalues of any graph is at most its number of edges plus $\binom{k+1}{2}$. Some large classes of graphs are known to satisfy BC, and $k$-BC is known for $k=1,2,n-1,n$. We show that BC is true of any not-too-irregular graph, that $k$-BC is true of planar graphs for $k \geq 11$, that $k$-BC is true for $k = \Omega(\sqrt{n})$ in bipartite graphs, that a violation of the upper bound could occur by at most $O(n^{5/4})$ for any graph on $n$ vertices, and that the set of $k$ for which a graph violates $k$-BC lies in an interval of length $O(n^{3/8})$. We also show, strangely, that a close variant of BC is false: the conjectural upper bound is exceeded a.a.s. by $\Omega(n)$ in a random signed complete graph.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC