Graphs with high second eigenvalue multiplicity
Graphs with high second eigenvalue multiplicity
复制标题
具有高第二特征值重数的图
DOI：
10.1112/blms.12647
复制
发表时间：
2022
影响因子：
0.9
通讯作者：
Zhao, Yufei
中科院分区：
文献类型：
--
作者：
Haiman, Milan;Schildkraut, Carl;Zhang, Shengtong;Zhao, Yufei
Jiang，Tidor，Yao，Zhang和Zhao最近证明了连通有界度图具有次线性第二特征值重数（总是指邻接矩阵）。这一结果是解决固定角度等角线问题的关键一步。这就引出了一个很自然的问题：连通有界度n$n$-顶点图的最大第二特征值重数是多少？时间复杂度为O（n/loglogn）$O（n/logn）$。以前已知的最著名的下界是n1/3$n^{1/3}$（对于无穷多个n$n$），来自PSL（2，q）$\operatorname{PSL}（2，q）$上的Cayley图。在这里，我们给出一个结构，显示了一个下界的n/log2n$\sqrt {n/\log_2 n}$。我们还构造了第二特征值重数至少为n2/5−1$n^{2/5}-1$的凯莱图。早期的技术表明，最多有O（n/loglogn）$O（n/\log \log n）$特征值（计数多重性）在O（1/logn）$O（1/\log n）$第二特征值。我们给出了一个结构，表明这个上界的近似第二特征值重数是紧到一个常数因子。这表明了对上界本征值多重性的早期技术的障碍。
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$n$‐vertex graph? The best‐known upper bound is O(n/loglogn)$O(n/\log \log n)$. The previously known best‐known lower bound is on the order of n1/3$n^{1/3}$ (for infinitely many n$n$), coming from Cayley graphs on PSL(2,q)$\operatorname{PSL}(2,q)$. Here we give a construction showing a lower bound of n/log2n$\sqrt {n/\log _2 n}$. We also construct Cayley graphs with second eigenvalue multiplicity at least n2/5−1$n^{2/5}-1$. Earlier techniques show that there are at most O(n/loglogn)$O(n/\log \log n)$ eigenvalues (counting multiplicities) within O(1/logn)$O(1/\log n)$ 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.
影响因子：
4.9
作者：
Zilin Jiang;Jonathan Tidor;Yuan Yao;Shengtong Zhang;Yufei Zhao
通讯作者：
Zilin Jiang;Jonathan Tidor;Yuan Yao;Shengtong Zhang;Yufei Zhao
球面二距离集和有符号图的特征值
影响因子：
1.1
作者：
Zilin Jiang;Jonathan Tidor;Yuan Yao;Shengtong Zhang;Yufei Zhao
通讯作者：
Yufei Zhao
影响因子：
2.2
作者：
Gilbert, Seth;Lynch, Nancy A.
通讯作者：
Lynch, Nancy A.