Maximum spread of graphs and bipartite graphs

DOI10.1090/CAMS/14MaRDI QIDQ6052388zbMATH OpenOpenAlexFDO

Authors Jane Breen, Michael Tait, John C. Urschel

Publication date 17 October 2023

Published in Communications of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.03129

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)

Abstract: 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 $lfloor2n/3floor$ and $lceiln/3ceil$ 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 $eleq{n}^2/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.

Recommendations

• The spread of the spectrum of a graph
• Graph Limits and Spectral Extremal Problems for Graphs
• On the maximum spread of planar and outerplanar graphs
• On the spread of outerplanar graphs
• The spread of tetracyclic graphs

Cites work

• A rigorous ODE solver and Smale's 14th problem
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Eigenvalue problems of Nordhaus--Gaddum type
• Extrema of graph eigenvalues
• Gap sets for the spectra of regular graphs with minimum spectral gap
• Graphs with small spectral gap
• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 3660223 (Why is no real title available?)
• scientific article; zbMATH DE number 1789934 (Why is no real title available?)
• scientific article; zbMATH DE number 3349865 (Why is no real title available?)
• Inequalities for Graph Eigenvalues
• Limits of dense graph sequences
• Linear combinations of graph eigenvalues
• Lower bounds for the spread of a matrix
• On the spread of matrices and polynomials
• Proof of a conjecture of V. Nikiforov
• Regular graphs with minimum spectral gap
• Spectra of graphs
• Spectral radius of bipartite graphs
• Szemerédi's lemma for the analyst
• The local density of triangle-free graphs
• The Rotation of Eigenvectors by a Perturbation. III
• The spectral radius of graphs without paths and cycles of specified length
• The spread of a matrix
• The spread of the spectrum of a graph
• The structure of trivalent graphs with minimal eigenvalue gap
• Threshold graphs and related topics
• Upper bounds for the spread of a matrix

Cited in

(12)

• Some results on placing bipartite graphs of maximum degree two
• Maximum spread of \(K_{2,t}\)-minor-free graphs
• Graph Limits and Spectral Extremal Problems for Graphs
• On the maximum spread of planar and outerplanar graphs
• Bounds on the spread and trace norm of the adjacency matrix of a graph
• On the maximum spread of non-negative matrices
• Maximum spectral gaps of graphs
• Maximum spread of graphs without paths of specified length
• Perfect state transfer between real pure states
• Maximum spread of \(K_{s,t}\)-minor-free graphs
• Maximum spread of \(K_r - E(\cup_{i = 1}^\ell P_{k_i})\)-minor-free graphs
• Maximum spread of graphs with the hereditarily bounded property

This page was built for publication: Maximum spread of graphs and bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6052388)