论文标题
封闭步行和第二个特征值多样性的支持
Support of Closed Walks and Second Eigenvalue Multiplicity of the Normalized Adjacency Matrix
论文作者
论文摘要
我们表明，任何连接的最大程度连接图$δ$的第二个标准化邻接矩阵特征值均由$ o（nδ^^^7/5}/\ log^{1/5-o（1/5-o（1）} n）$ to $δ$，以及任何$δ$ $ o（n \ log^{1/2} d/\ log^{1/4-o（1）} n）$对于简单$ d $ - regargular Graph当$ d \ ge \ ge \ log^{1/4} n $时。实际上，在任何宽度的间隔$λ_2/\log_Δ^{1-o（1）} n $中，含有第二个特征值$λ_2$的任何间隔都保持相同的界限。证明中的主要成分是在任何连接的图中的闭合随机步行$ 2K $的典型支持的多项式（以$ k $为单位），这反过来又依赖于perron eigentires of perron eigenties of perron eigentires of perron eigentires of formen formentive sublix sublix subligentized邻接矩阵的参赛作品。
We show that the multiplicity of the second normalized adjacency matrix eigenvalue of any connected graph of maximum degree $Δ$ is bounded by $O(n Δ^{7/5}/\log^{1/5-o(1)}n)$ for any $Δ$, and by $O(n\log^{1/2}d/\log^{1/4-o(1)}n)$ for simple $d$-regular graphs when $d\ge \log^{1/4}n$. In fact, the same bounds hold for the number of eigenvalues in any interval of width $λ_2/\log_Δ^{1-o(1)}n$ containing the second eigenvalue $λ_2$. The main ingredient in the proof is a polynomial (in $k$) lower bound on the typical support of a closed random walk of length $2k$ in 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.
