Graphs with high second eigenvalue multiplicity

DOI10.1112/BLMS.12647MaRDI QIDQ6048870zbMATH OpenOpenAlexFDO

Authors Carl Schildkraut, Shengtong Zhang, Yufei Zhao

Publication date 15 September 2023

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2109.13131, https://hdl.handle.net/1721.1/145737

zbMATH Keywords

Cayley graphsconnected bounded degree \(n\)-vertex graph

Mathematics Subject Classification ID

Vertex degrees (05C07) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Jiang, Tidor, Yao, Zhang, and Zhao recently showed that connected bounded degree graphs have sublinear second eigenvalue multiplicity (always referring to the adjacency matrix). This result was a key step in the solution to the problem of equiangular lines with fixed angles. It led to the natural question: what is the maximum second eigenvalue multiplicity of a connected bounded degree $n$-vertex graph? The best known upper bound is $O(n/loglogn)$. The previously known best known lower bound is on the order of $n^{1/3}$ (for infinitely many $n$), coming from Cayley graphs on $extPSL(2,q)$. Here we give constructions showing a lower bound on the order of $sqrtn/logn$. We also construct Cayley graphs with second eigenvalue multiplicity at least $n^{2/5}-1$. Earlier techniques show that there are at most $O(n/loglogn)$ eigenvalues (counting multiplicities) within $O(1/logn)$ of the second eigenvalue. We give a construction showing this upper bound on approximate second eigenvalue multiplicity is tight up to a constant factor. This demonstrates a barrier to earlier techniques for upper bounding eigenvalue multiplicities.

Recommendations

• Multiplicity of  the second‐largest eigenvalue of a planar graph
• On graphs with multiple eigenvalues
• On graphs with second largest eigenvalue less than 1
• Graphs characterized by the second eigenvalue
• Graphs with second largest eigenvalue less than 1/2
• On graphs with an eigenvalue of maximal multiplicity
• On the second eigenvalue of hypergraphs
• Characterization of graphs with an eigenvalue of large multiplicity
• On the second eigenvalue of a graph
• ON THE MULTIPLICITIES OF GRAPH EIGENVALUES

Cites work

• A proof of Alon’s second eigenvalue conjecture and related problems
• Equiangular lines with a fixed angle
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Expander graphs and their applications
• Expander graphs in pure and applied mathematics
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• scientific article; zbMATH DE number 3552764 (Why is no real title available?)
• Ramanujan graphs
• Spherical two-distance sets and eigenvalues of signed graphs
• Support of closed walks and second eigenvalue multiplicity of graphs
• Symmetric Random Walks on Groups
• The expected eigenvalue distribution of a large regular graph

Cited in

(7)

• Multiplicity of  the second‐largest eigenvalue of a planar graph
• Support of closed walks and second eigenvalue multiplicity of graphs
• Graphs for which the second largest distance eigenvalue is less than \(- \frac{1}{2}\)
• Maximal multiplicity of Laplacian eigenvalues in negatively curved surfaces
• Equiangular lines via matrix projection
• Uniacute spherical codes
• Subdivision and graph eigenvalues

This page was built for publication: Graphs with high second eigenvalue multiplicity

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