ON THE SPECTRUM OF DENSE RANDOM GEOMETRIC GRAPHS

• 成果类型: Article
• 署名作者: Adhikari, Kartick; Adler, Robert J.; Bobrowski, Omer; Rosenthal, Ron
• 署名单位: Technion Israel Institute of Technology; Technion Israel Institute of Technology
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/21-AAP1720
• 发表日期: 2022
• 页码: 1734-1773
• 关键词: eigenvalues; COHOMOLOGY; statistics

摘要

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 Erdos-Renyi 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 <= k <= d there are at least ((k)d) 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.