Given a graph G=(V,E) and embedding p:V-->R^d, the framework (G,p) is called rigid if every perturbation of p which preserves the length of each edge in E, does not change the distance between any pair of vertices. If this holds for a generic p we say that G is d-rigid. In the last 50 years, starting from works of Laman, and Asimov and Roth, the mathematical problem of characterizing d-rigid graphs has been studied extensively.

In this talk we will discuss the problem of determining the threshold probability for d-rigidity of random graphs. We prove a hitting time result in the Erdős-Rényi evolution: If uniform random edges on n vertices are added one at a time, then, with high probability, the graph becomes d-rigid at the very moment that its minimum degree becomes d.
Joint work with Alan Lew, Eran Nevo and Orit Raz.`