Sharp threshold for rigidity of random graphs

Abstract

We consider the Erdős-Rényi evolution of random graphs, where a new uniformly distributed edge is added to the graph in every step. For every fixed $d\ge 1$, we show that with high probability, the graph becomes rigid in ${\mathbb{R}}^d$ at the very moment its minimum degree becomes $d$, and it becomes globally rigid in ${\mathbb{R}}^d$ at the very moment its minimum degree becomes $d+1$.