2021/09/07 by Jane Breen, Breen, Jane, Alex W. N. Riasanovsky +5 · 2 citations
Computer Science · Mathematics · #05C50 #15A18 #15A60 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Spectral Theory in Mathematical Physics
paper · pdf · doi:10.48550/arxiv.2109.03129
openalex publication_date 2021/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given any graph G, the (adjacency) spread of G is the maximum absolute 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 \mathscrL2[0,1]. The second conjecture claims that for any fixed e≤ n2/4, if G maximizes spread over all n-vertex graphs with e edges, then G is bipartite. We prove an asymptotic version of this conjecture. Furthermore, we exhibit an infinite family of counterexamples, which shows that our asymptotic solution is tight up to lower order error terms.