On the Rigidity of Random Graphs in high-dimensional spaces

Abstract

We study the maximum dimension $d=d(n,p)$ for which an Erdős-Rényi $G(n,p)$ random graph is $d$-rigid. Our main results reveal two different regimes of rigidity in $G(n,p)$ separated at $p_c=C_{\ast }\log n/n,C_{\ast }=2/(1-\log 2)$ -- the point where the graph's minimum degree exceeds half its average degree. We show that if $p<(1-\epsilon )p_c$, then $d(n,p)$ is asymptotically almost surely (a.a.s.) equal to the minimum degree of $G(n,p)$. In contrast, if $p_c\le p=o(n^{-1/2})$ then $d(n,p)$ is a.a.s. equal to $(1/2+o(1))np$. The second result confirms, in this regime, a conjecture of Krivelevich, Lew, and Michaeli.