Circular law for sparse random regular digraphs
Circular law for sparse random regular digraphs
复制标题
稀疏随机正则有向图的循环律
DOI：
10.4171/jems/1015
复制
发表时间：
2018
影响因子：
2.6
通讯作者：
Pierre Youssef
中科院分区：
文献类型：
--
作者：
A. Litvak;A. Lytova;K. Tikhomirov;N. Tomczak;Pierre Youssef
固定一个常量$C\geq 1$，令$d=d(N)$满足$d\leq\ln^{C}n$，对每个大整数$n$。记为$A_n$表示$n$顶点上的一致随机有向$d$-正则图的邻接矩阵。我们证明了，只要有$n$，则适当重新标度的矩阵$A_n$的经验谱分布按概率弱收敛于循环定律。这一结果与Cook早先的工作一起，完全解决了次数趋于无穷的有向$d$-正则环境中经验分布的弱收敛问题。作为我们证明的一个关键元素，我们基于对行空间的随机正规的研究和对矩阵项之间缺乏独立性的乘积结构的构造，发展了一种对$A_n$的中间奇异值进行界的技巧。
Fix a constant $C\geq 1$ and let $d=d(n)$ satisfy $d\leq \ln^{C} n$ for every large integer $n$. Denote by $A_n$ the adjacency matrix of a uniform random directed $d$-regular graph on $n$ vertices. We show that, as long as $d\to\infty$ with $n$, the empirical spectral distribution of appropriately rescaled matrix $A_n$ converges weakly in probability to the circular law. This result, together with an earlier work of Cook, completely settles the problem of weak convergence of the empirical distribution in directed $d$-regular setting with the degree tending to infinity. As a crucial element of our proof, we develop a technique of bounding intermediate singular values of $A_n$ based on studying random normals to rowspaces and on constructing a product structure to deal with the lack of independence between the matrix entries.