Testing thresholds for high-dimensional random geometric graphs

Mon May 23rd 2022, 4:00pm
Sequoia 200
Tselil Schramm, Stanford Statistics

We study random geometric graphs on the unit sphere in the high-dimensional setting, where the dimension grows to infinity with the number of vertices. Our central question is: given such a graph, at which dimensions is it possible to identify the underlying geometry? As the dimension grows relative to the number of vertices, the edges in the graph become increasingly independent, and the underlying geometry becomes less apparent. In this talk I will present recent progress on this question: we show that in sparse geometric random graphs, if the dimension is at least polylogarithmic in the number of vertices, then the graphs are statistically indistinguishable from Erdös–Renyi graphs, and the underlying geometry disappears.