The Spectrum of Dense Random Geometric Graphs
Speaker 
Kartick Adhikari,
Technion, Israel


When 
Sep 19, 2019
from 03:00 PM to 04:00 PM 
Where  LH006 
Add event to calendar 
vCal iCal 
Abstract: We study the spectrum of a random geometric graph, in a regime where the graph is dense and highly connected. As opposed to other random graph models (e.g.~the ErdosRenyi random graph), even when the graph is dense, not all the eigenvalues are concentrated around 1. In the case where the vertices are generated uniformly in a unit ddimensional box, we show that for every \(0\le k \le d\) there are \(\binom{d}{k}\) eigenvalues at \(12^{k}\). The rest of the eigenvalues are indeed close to 1. The spectrum of the graph Laplacian plays a key role in both theory and applications. We also show that the corresponding eigenfunctions are tightly related to the geometric configuration of the points. Aside from the interesting mathematical phenomenon we reveal here, the results of this paper can also be used to analyze the homology of the random VietorisRips complex via spectral methods.