The spectral gap of dense random regular graphs
The spectral gap of dense random regular graphs
复制标题
稠密随机正则图的谱间隙
DOI：
10.1214/18-aop1263
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Pierre Youssef
中科院分区：
文献类型：
--
作者：
K. Tikhomirov;Pierre Youssef
对于任意的$\alpha\in（0，1）$和任意的$n^{\alpha}\leq d\leq n/2$，我们证明了$\lambda（G）\leq C_\alpha \sqrt{d}$的概率至少为$1-\frac{1}{n}$，其中$G$是$n$个顶点上的一致随机$d$-正则图，$\lambda（G）$表示它的第二大特征值（绝对值），$C_\alpha$是一个只依赖于$\alpha$的常数。结合以前的结果在这个方向上覆盖的情况下，稀疏随机图，这完全解决了问题的估计的幅度$\lambda（G）$，直到一个乘法常数，为所有的值$n$和$d$，确认一个猜想Vu。这个结果是作为一个结果的估计的第二大奇异值的随机{\它有向}图的邻接矩阵与预定义的度序列。作为主要的技术工具，我们证明了矩阵空间上任意线性形式的一个集中不等式，其中概率测度由具有给定度序列的随机有向图的邻接矩阵导出。证明是一个非平凡的应用弗里德曼不等式的鞅，结合靴陷阱和张量化参数。我们的方法与Broder，Frieze，Suen和Upfal（1999）所用的方法有很大的不同，他们建立了$\lambda（G）$对于$d=o的上界（\sqrt{n}）$，和库克的论点，Goldstein和约翰逊（2015）导出了线性形式的浓度不等式，并使用大小在d= O（n^{2/3}）范围内估计了$\lambda（G）$，偏置耦合
For any $\alpha\in (0,1)$ and any $n^{\alpha}\leq d\leq n/2$, we show that $\lambda(G)\leq C_\alpha \sqrt{d}$ with probability at least $1-\frac{1}{n}$, where $G$ is the uniform random $d$-regular graph on $n$ vertices, $\lambda(G)$ denotes its second largest eigenvalue (in absolute value) and $C_\alpha$ is a constant depending only on $\alpha$. Combined with earlier results in this direction covering the case of sparse random graphs, this completely settles the problem of estimating the magnitude of $\lambda(G)$, up to a multiplicative constant, for all values of $n$ and $d$, confirming a conjecture of Vu. The result is obtained as a consequence of an estimate for the second largest singular value of adjacency matrices of random {\it directed} graphs with predefined degree sequences. As the main technical tool, we prove a concentration inequality for arbitrary linear forms on the space of matrices, where the probability measure is induced by the adjacency matrix of a random directed graph with prescribed degree sequences. The proof is a non-trivial application of the Freedman inequality for martingales, combined with boots-trapping and tensorization arguments. Our method bears considerable differences compared to the approach used by Broder, Frieze, Suen and Upfal (1999) who established the upper bound for $\lambda(G)$ for $d=o(\sqrt{n})$, and to the argument of Cook, Goldstein and Johnson (2015) who derived a concentration inequality for linear forms and estimated $\lambda(G)$ in the range $d= O(n^{2/3})$ using size-biased couplings.