Computer Science/Discrete Mathematics Seminar I

The random geometric graph Geo_d(n,p) is a probability distribution over graphs, constructed by placing n points uniformly on a d-dimensional sphere and connecting two points whenever they are sufficiently close — where the proximity threshold is chosen so that each edge appears with probability p. Recently, Ma, Shen, and Xie used this model to obtain improved constructions for the Ramsey numbers R(k,Ck), where C>1 is a fixed constant. In this talk, I will present a simplification of their approach that allows for a sharper quantitative analysis and gives improved lower bounds.

I will also discuss how the same ideas can be used to make progress on a conjecture of Bubeck, Ding, Eldan, and Rácz. They observed that when the dimension d is sufficiently large as a function of n and p, the distribution Geo_d(n,p) converges to the classical Erdős–Rényi random graph G(n,p) in total variation distance, and conjectured that the precise threshold for this convergence is d=(np)^3polylog(p). Until now, this conjecture had been verified only in the extremal regimes p=Θ(1) and p=Θ(1/n). I will outline a proof of the conjecture in the intermediate regime n^{-1/5}<p<1.

This talk is based on the joint work with Zach Hunter and Benny Sudakov.