Maximum spread of graphs and bipartite graphs

Abstract:

Given any graph $G$, the spread of $G$ is the maximum difference between any two eigenvalues of the adjacency matrix of $G$. In this paper, we resolve a pair of 20-year-old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs. The first states that for all positive integers $n$, the $n$-vertex graph $G$ that maximizes spread is the join of a clique and an independent set, with $\lfloor 2n/3 \rfloor$ and $\lceil n/3 \rceil$ vertices, respectively. Using techniques from the theory of graph limits and numerical analysis, we prove this claim for all $n$ sufficiently large. As an intermediate step, we prove an analogous result for a family of operators in the Hilbert space over $\mathscr {L}^2[0,1]$. The second conjecture claims that for any fixed $m \leq n^2/4$, if $G$ maximizes spread over all $n$-vertex graphs with $m$ edges, then $G$ is bipartite. We prove an asymptotic version of this conjecture. Furthermore, we construct an infinite family of counterexamples, which shows that our asymptotic solution is tight up to lower-order error terms.