Sharp threshold for rigidity of random graphs

Alan Lew, Eran Nevo, Yuval Peled, Orit E. Raz

Published 2022-02-20, updated 2022-09-13Version 2

We consider the Erd\H{o}s-R\'enyi 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$.