Maximum spread of graphs and bipartite graphs
Communications of the American Mathematical Society · 2022
DOI: 10.1090/cams/14 ↗Kurz gefasst
Fachartikel in der Zeitschrift Communications of the American Mathematical Society, 2022. Verfasst von Jane Breen und 3 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 33 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC 3.0). Gefördert von: Natural Sciences and Engineering Research Council of Canada, National Science Foundation.
Abstract (Originalsprache)
Given any graph G G , the spread of G G is the maximum difference between any two eigenvalues of the adjacency matrix of G 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 n , the n n -vertex graph G G that maximizes spread is the join of a clique and an independent set, with ⌊ 2 n / 3 ⌋ \lfloor 2n/3 \rfloor and ⌈ n / 3 ⌉ \lceil n/3 \rceil vertices, respectively. Using techniques from the theory of graph limits and numerical analysis, we prove this claim for all n n sufficiently large. As an intermediate step, we prove an analogous result for a family of operators in the Hilbert space over L 2 [ 0 , 1 ] \mathscr {L}^2[0,1] . The second conjecture claims that for any fixed m ≤ n 2 / 4 m \leq n^2/4 , if G G maximizes spread over all n n -vertex graphs with m m edges, then G 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.
Förderung
- Natural Sciences and Engineering Research Council of Canada
- National Science Foundation
Zitieren
APA
Breen, J., Riasanovsky, A. W. N., Tait, M., & Urschel, J. (2022). Maximum spread of graphs and bipartite graphs. Communications of the American Mathematical Society. https://doi.org/10.1090/cams/14
Vancouver
Breen J, Riasanovsky AWN, Tait M, Urschel J. Maximum spread of graphs and bipartite graphs. Communications of the American Mathematical Society. 2022. doi:10.1090/cams/14
BibTeX
@article{Breen2022,
author = {Breen, Jane and Riasanovsky, Alex W. N. and Tait, Michael and Urschel, John},
title = {Maximum spread of graphs and bipartite graphs},
journal = {Communications of the American Mathematical Society},
year = {2022},
doi = {10.1090/cams/14}
}
EUVIMED