Talk information

Date: Sunday, November 15, 2026
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Benny Sudakov (ETH)
Title: Random Geometric Graphs: Ramsey Bounds and Testing Thresholds

Abstract:

The random geometric graph $G(n,S^d,p)$ is obtained by placing $n$ random points independently and uniformly on the unit sphere $S^d$, and connecting two points whenever they are sufficiently close, with the threshold chosen so that each edge appears with probability $p$. The underlying geometry of the model creates correlations between edges, making its behavior richer than that of the corresponding binomial random graph $G(n,p)$.

A striking recent application of these correlations is due to Ma, Shen, and Xie, who used high-dimensional random geometric graphs to obtain an exponential improvement over Erdős’s celebrated lower bound for $R(k,Ck)$, where $C>1$ is fixed. I will discuss a simplification of their approach using Gaussian random geometric graphs, leading to a much shorter analysis and sharper quantitative bounds.

I will then turn to a complementary question: when does the geometry disappear? More precisely, for which dimensions $d$ is $G(n,S^d,p)$ statistically indistinguishable from $G(n,p)$? This problem, introduced by Bubeck, Ding, Eldan, and Rácz, has attracted considerable interest across probability, theoretical computer science, and high-dimensional statistics. They conjectured that the threshold is governed by the signed triangle count, namely $d \asymp n^3p^3$ up to logarithmic factors. I will outline a proof of this conjecture for a wide range of $p$.

This talk is based on joint work with Zach Hunter and Aleksa Milojević.