On the spectrum of dense random geometric graphs

DOI10.1214/21-AAP1720zbMATH Open1503.05106arXiv2004.04967MaRDI QIDQ2170358FDOQ2170358

Robert J. Adler, Omer Bobrowski, Ron Rosenthal, Kartick Adhikari

Publication date: 5 September 2022

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: 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 $0lekled$ there are at least $$ 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.

Full work available at URL: https://arxiv.org/abs/2004.04967

Recommendations

• On the normalized Laplacian spectra of random geometric graphs
• The Spectral Gap of Random Graphs with Given Expected Degrees
• The spectrum of a random geometric graph is concentrated
• On the Laplacian Eigenvalues of G_n,p
• A spectral analysis of the normalized Laplacian matrix in random graphs

zbMATH Keywords

spectral measurerandom geometric graphshomological connectivity

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Integral operators (47G10)

Cites Work

• Random Geometric Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Spectral radii of sparse random matrices
• The eigenvalues of random symmetric matrices
• Eigenvalues of Euclidean random matrices
• A Survey on Spectra of infinite Graphs
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• Expander graphs and their applications
• Minimax grid matching and empirical measures
• Explicit construction of linear sized tolerant networks
• Sharp vanishing thresholds for cohomology of random flag complexes
• p-adic curvature and the cohomology of discrete subgroups of p-adic groups
• Explicit Concentrators from Generalized N-Gons
• Spectral statistics of Erdős-Rényi graphs II: eigenvalue spacing and the extreme eigenvalues
• Random matrix approximation of spectra of integral operators
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• The spectrum of kernel random matrices
• Spectral statistics of Erdős-Rényi graphs. I: Local semicircle law
• Spectral techniques applied to sparse random graphs
• Spectral norm of random matrices
• On Laplacians of random complexes
• On the Laplacian Eigenvalues of G_n,p
• Limits of kernel operators and the spectral regularity lemma
• Spectral Gaps of Random Graphs and Applications
• Title not available (Why is that?)
• Homological connectivity in random Čech complexes
• The dimension-free structure of nonhomogeneous random matrices
• On the sub-Gaussianity of the beta and Dirichlet distributions
• Eigenvalue confinement and spectral gap for random simplicial complexes

Cited In (4)

• Random geometric graphs and isometries of normed spaces
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• On the normalized Laplacian spectra of random geometric graphs
• The spectrum of a random geometric graph is concentrated

This page was built for publication: On the spectrum of dense random geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2170358)