APRG Seminar

Title: The Spectrum of Dense Random Geometric Graphs
Speaker: Kartick Adhikari (Technion, Haifa, Israel)
Date: 18 September 2019
Time: 3 pm
Venue: LH-1, Mathematics Department

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 Erdos-Renyi 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 d-dimensional box, we show that for every $0\le k \le d$ there are $\binom{d}{k}$ eigenvalues at $1-2^{-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 Vietoris-Rips complex via spectral methods.

The talk will be based on a joint work with R. Adler, O. Bobrowski, and R. Rosenthal.


Contact: +91 (80) 2293 2711, +91 (80) 2293 2265 ;     E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 17 Sep 2019