Suppose that n vertices are placed generically in R^d, and consider the Erdos-Rényi evolution of random graphs, where a new uniformly distributed edge is added to the graph in every step.
We discover the moments in the evolution in which the graph becomes (with high probability)
1. Rigid: the only way to continuously move the vertices while preserving all the distances between adjacent vertices is induced by an isometric motion of R^d.
2. Globally rigid: the embedding of the vertices can be reconstructed, up to isometry, from the distances between adjacent vertices.
Joint work with Alan Lew, Eran Nevo, Orit Raz.
Copyright. All Rights Reserved.