On the spectrum of dense random geometric graphs

DOI10.1214/21-AAP1720MaRDI QIDQ2170358zbMATHFDO

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

Publication date 5 September 2022

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

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

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)

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.

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

Cites work

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

Cited in

(6)

• Random geometric graphs and isometries of normed spaces
• The spectrum of a random geometric graph is concentrated
• Symmetric motifs in random geometric graphs
• On the normalized Laplacian spectra of random geometric graphs
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Asymptotic representation theory and the spectrum of a random geometric graph on a compact Lie group

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)