Graph rigidity is one of the most classical subjects in graph theory, studying geometric properties of graphs. Formally, a graph G=(V,E) is d-rigid if a generic embedding of its vertex set V into R^d is rigid, namely, every continuous motion of its vertices preserving the lengths of the edges of G necessarily preserves all pairwise distances between the vertices of G.

We develop a new sufficient condition for d-rigidity, formulated in graph theoretic terms. This condition allows us to obtain several new results about rigidity of random graphs. In particular, we argue that for edge probability p>2ln n/n, a random graph G(n,p) is with high probability (whp) cnp-rigid, for c>0 being an absolute constant. We also show that a random r-regular graph G_{n,r}, r>=3, is whp cr-rigid.

Another consequence is a sufficient condition for d-rigidity based on the minimum co-degree of the graph.    

The talk should be accessible to a general graph theoretic audience, no previous experience (whether positive or negative) with graph rigidity will be assumed.

Joint work with Alan Lew and Peleg Michaeli.