Combinatorial conditions for graph rigidity

A graph G=(V,E) is called d-rigid if, for a generic embedding of its vertices in R^d, there is no continuous motion of the vertices which preserves the distance between all pairs of adjacent vertices, except for the trivial motions — rotations and translations of the whole graph.

In this talk, I will first give a gentle introduction to the topic, focusing on a classical linear algebraic reformulation of the problem. Then, I will present various basic combinatorial tools for proving rigidity of graphs, as well as a new "partition-based" method, developed in recent joint works with Nevo, Peled, and Raz, and with Krivelevich and Michaeli. I will then survey various applications of this new method.