论文标题
关于随机常规图的跟踪方法的注释
A Note on the Trace Method for Random Regular Graphs
论文作者
论文摘要
该注释的主要目标是说明分析常规图而不是普通频谱的非背带频谱的优势。我们表明，通过切换到非折线频谱，[Puder 2015，Arxiv :: 1212.5216]中使用的证明方法产生的限制为$ 2 \ sqrt {d-1}+\ frac {2} {2} {\ sqrt {\ sqrt {d-1}} $而不是原始$ 2} $ 2}随机$ d $ regular Graph的特征值。
The main goal of this note is to illustrate the advantage of analyzing the non-backtracking spectrum of a regular graph rather than the ordinary spectrum. We show that by switching to non-backtracking spectrum, the method of proof used in [Puder 2015, arXiv::1212.5216] yields a bound of $2\sqrt{d-1}+\frac{2}{\sqrt{d-1}}$ instead of the original $2\sqrt{d-1}+1$ on the second largest eigenvalue of a random $d$-regular graph.
