Algebraic Graph Theory Seminar - Michael Tait

Title: Two conjectures on the spread of graphs

Abstract:

Given a graph $G$ let $\lambda_1$ and $\lambda_n$ be the maximum and minimum eigenvalues of its adjacency matrix and define the spread of $G$ to be $\lambda_1 - \lambda_n$. In this talk we discuss solutions to a pair of 20 year old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs.

The first, referred to as the spread conjecture, states that over all graphs on $n$ vertices the join of a clique of order $\lfloor 2n/3 \rfloor$ and an independent set of order $\lceil n/3 \rceil$ is the unique graph with maximum spread. The second, referred to as the bipartite spread conjecture, says that for any fixed $e\leq n^2/4$, if $G$ has maximum spread over all $n$-vertex graphs with $e$ edges, then $G$ must be bipartite.

We show that the spread conjecture is true for all sufficiently large $n$, and we prove an asymptotic version of the bipartite spread conjecture. Furthermore, we exhibit an infinite family of counterexamples to the bipartite spread conjecture which shows that our asymptotic solution is tight up to a multiplicative factor in the error term. This is joint work with Jane Breen, Alex Riasanovsky, and John Urschel.