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 newresults about rigidity of random graphs. In particular, we argue that for edge probability $p>2\ln(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.
 

A joint work with Alan Lew and Peleg Michaeli.