The spectrum of random lifts
The spectrum of random lifts
复制标题
随机提升的频谱
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Simon Griffiths
中科院分区：
文献类型：
--
作者：
L. Addario;Simon Griffiths
对于固定的d正则图H，通过将H的每个顶点v替换为包含n个顶点的“纤维”，然后在H的相邻顶点对应的纤维之间放置均匀随机匹配，从而获得随机n-lift。我们证明，在极高的概率下，所有不是H的特征值的lift的特征值都具有O阶（sqrt(d)）。特别地，如果H是拉马努金，那么它的n-升程大概率接近拉马努金。我们还证明了n升力的任何异常大的特征值，而不是H的特征值，极有可能是由大小为O（b| E(H)|）的密集子图引起的。
For a fixed d-regular graph H, a random n-lift is obtained by replacing each vertex v of H by a "fibre" containing n vertices, then placing a uniformly random matching between fibres corresponding to adjacent vertices of H. We show that with extremely high probability, all eigenvalues of the lift that are not eigenvalues of H, have order O(sqrt(d)). In particular, if H is Ramanujan then its n-lift is with high probability nearly Ramanujan. We also show that any exceptionally large eigenvalues of the n-lift that are not eigenvalues of H, are overwhelmingly likely to have been caused by a dense subgraph of size O(|E(H)|).