On the Rigidity of Random Graphs in high-dimensional spaces

Yuval Peled, Niv Peleg

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)$ separat…