On the almost eigenvectors of random regular graphs
On the almost eigenvectors of random regular graphs
复制标题
关于随机正则图的近似特征向量
DOI：
10.1214/18-aop1294
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Balázs Szegedy
中科院分区：
文献类型：
--
作者：
Á. Backhausz;Balázs Szegedy
设$d\geq 3$是固定的，$G$是$n$个顶点的随机$d$-正则图。我们证明，如果$n$足够大，则$G$的每个几乎特征向量$v$的项分布（项和为0，并归一化为长度$\sqrt{n}$）接近于弱拓扑中的某个高斯分布$N（0，\sigma）$，其中$0\leq\sigma\leq 1$。我们的定理甚至在更强的意义上保持，当许多条目同时在图的小随机邻域中查看时。此外，当特征值相近时，我们还得到了几个殆特征向量的联合分布的高斯性。我们的证明使用图极限和信息论。我们的结果对i.i.d.因子有影响。无限正则树上的进程。
Let $d\geq 3$ be fixed and $G$ be a large random $d$-regular graph on $n$ vertices. We show that if $n$ is large enough then the entry distribution of every almost eigenvector $v$ of $G$ (with entry sum 0 and normalized to have length $\sqrt{n}$) is close to some Gaussian distribution $N(0,\sigma)$ in the weak topology where $0\leq\sigma\leq 1$. Our theorem holds even in the stronger sense when many entries are looked at simultaneously in small random neighborhoods of the graph. Furthermore, we also get the Gaussianity of the joint distribution of several almost eigenvectors if the corresponding eigenvalues are close. Our proof uses graph limits and information theory. Our results have consequences for factor of i.i.d.\ processes on the infinite regular tree.