论文标题
随机常规图的光谱间隙
The spectral gap of random regular graphs
论文作者
论文摘要
我们使用基于傅立叶分析的新方法来绑定随机$ d $等级图的第二个特征值。令$ g_ {n，d} $为$ n $ vertices上的统一随机$ d $ regular Graph，让$λ（g_ {n，d}）$是其绝对值的第二大特征值。对于某些常数$ c> 0 $和任何度$ d $，带有$ \ log^{10} n \ ll d \ leq c n $，我们表明$λ（g_ {n，d}）=（2 + o（2 + o（2 + o（1））\ sqrt {d（n -d） / n} $几乎是近距离的。结合涵盖稀疏随机图的较早结果，这完全确定了所有$ d \ leq c n $的$λ（g_ {n，d}）$的渐近值。为了实现这一目标，我们引入了使用离散傅立叶分析中的机制的新方法，并将它们与现有的工具和估算值结合使用，尤其是Liebenau和Wormald的$ D $“随机图）。
We bound the second eigenvalue of random $d$-regular graphs, for a wide range of degrees $d$, using a novel approach based on Fourier analysis. Let $G_{n, d}$ be a uniform random $d$-regular graph on $n$ vertices, and let $λ(G_{n, d})$ be its second largest eigenvalue by absolute value. For some constant $c > 0$ and any degree $d$ with $\log^{10} n \ll d \leq c n$, we show that $λ(G_{n, d}) = (2 + o(1)) \sqrt{d (n - d) / n}$ asymptotically almost surely. Combined with earlier results that cover the case of sparse random graphs, this fully determines the asymptotic value of $λ(G_{n, d})$ for all $d \leq c n$. To achieve this, we introduce new methods that use mechanisms from discrete Fourier analysis, and combine them with existing tools and estimates on $d$-regular random graphs - especially those of Liebenau and Wormald.
