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 floor(2n/3) and an independent set of order ceiling(n/3) is the unique graph with maximum spread. The second, referred to as the bipartite spread conjecture, says that for any fixed e <= 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.
Please email Sean English (senglish@illinois.edu) for Zoom link.
