论文标题
在密集的随机几何图上
On the Spectrum of Dense Random Geometric Graphs
论文作者
论文摘要
在本文中，我们研究了图形密集且高度连接的状态下，随机几何图$ g（n，r）$的光谱。在\ erdren $ g（n，p）$随机图中，众所周知，在连通性时，标准化图Laplacian的光谱集中在$ 1 $左右。我们表明，即使图形密集并且几乎是完整的图，也不会在$ g（n，r）$ case中发生这种浓度。特别是，我们表明限制频谱差距严格小于$ 1 $。在特殊情况下，顶点均匀分布在单位立方体和$ r = 1 $的情况下，我们表明，每$ 0 \ le k \ le d $每至少$ \ binom {d} {k} $ eigenvalues接近$ 1-2^{ - k} $，并且有限频谱差距$ 1/2 $。我们还表明，在这种情况下，相应的特征函数与点的几何配置密切相关。
In this paper we study the spectrum of the random geometric graph $G(n,r)$, in a regime where the graph is dense and highly connected. In the \erdren $G(n,p)$ random graph it is well known that upon connectivity the spectrum of the normalized graph Laplacian is concentrated around $1$. We show that such concentration does not occur in the $G(n,r)$ case, even when the graph is dense and almost a complete graph. In particular, we show that the limiting spectral gap is strictly smaller than $1$. In the special case where the vertices are distributed uniformly in the unit cube and $r=1$, we show that for every $0\le k \le d$ there are at least $\binom{d}{k}$ eigenvalues near $1-2^{-k}$, and the limiting spectral gap is exactly $1/2$. We also show that the corresponding eigenfunctions in this case are tightly related to the geometric configuration of the points.
