On the rigidity of random graphs in high-dimensional spaces

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 pc=C_*log n/n,~C_*=2/(1-log 2) -- the point where the graph's minimum degree exceeds half its average degree. We show that if p < (1-ε)pc, then $d(n,p)$ is asymptotically almost surely (a.a.s.) equal to the minimum degree of $G(n,p)$. In contrast, if pc ≤ 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.