Support of closed walks and second eigenvalue multiplicity of graphs
Support of closed walks and second eigenvalue multiplicity of graphs
复制标题
图的封闭游走和第二特征值重数的支持
DOI：
10.1145/3406325.3451129
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Srivastava, Nikhil
中科院分区：
文献类型：
--
作者：
McKenzie, Theo;Rasmussen, Peter Michael;Srivastava, Nikhil
我们证明，对于任何 Δ，任何最大度 Δ 的连通图的第二归一化邻接矩阵特征值的重数都以 O(nΔ7/5/log1/5−o(1)n) 为界，并且当 d≥ log1/4n 时，对于简单正则图，将其改进为 O(nlog1/2d/log1/4−o(1)n)。事实上，相同的界限对于包含第二特征值 λ2 的任何宽度 λ2/logΔ1−o(1)n 的区间中的特征值的数量都成立。证明中的主要成分是任何连通图长度为 2kin 的闭合随机游走的典型支持的多项式（墨水）下界，而该下界又依赖于归一化邻接矩阵的子矩阵的 Perron 特征向量条目的新下界。
We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree Δ is bounded byO(nΔ7/5/log1/5−o(1)n) for any Δ, and improve this toO(nlog1/2d/log1/4−o(1)n) for simpled-regular graphs whend≥ log1/4n. In fact, the same bounds hold for the number of eigenvalues in any interval of width λ2/logΔ1−o(1)ncontaining the second eigenvalue λ2. The main ingredient in the proof is a polynomial (ink) lower bound on the typical support of a closed random walk of length 2kin any connected graph, which in turn relies on new lower bounds for the entries of the Perron eigenvector of submatrices of the normalized adjacency matrix.
登录
查看更多内容
影响因子：
4.9
作者：
Zilin Jiang;Jonathan Tidor;Yuan Yao;Shengtong Zhang;Yufei Zhao
通讯作者：
Zilin Jiang;Jonathan Tidor;Yuan Yao;Shengtong Zhang;Yufei Zhao
通过全局相关性舍入半定编程层次结构
DOI：
10.1109/focs.2011.95
发表时间：
2011
期刊：
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
B. Barak;P. Raghavendra;David Steurer
通讯作者：
David Steurer
独特游戏的谱算法
DOI：
--
发表时间：
2010
期刊：
2010 IEEE 25th Annual Conference on Computational Complexity
影响因子：
--
作者：
A. Kolla
通讯作者：
A. Kolla
通过谱嵌入实现随机游走特征值的锐界
DOI：
--
发表时间：
2012
期刊：
arXiv.org
影响因子：
--
作者：
R. Lyons;S. Gharan
通讯作者：
S. Gharan
低阈值秩图的新正则引理和更快的逼近算法
DOI：
10.1007/978-3-642-40328-6_22
发表时间：
2012
期刊：
ArXiv
影响因子：
--
作者：
S. Gharan;L. Trevisan
通讯作者：
L. Trevisan