Abstract:
Given a graph $G$ and an embedding of its vertices in $R^d$, what continuous motions of the vertices preserve all edge lengths? Clearly all motions induced by an isometry of $R^d$ do, these are the trivial motions; are there any others? If the answer is NO for all (equivalently, for one) generic embedding, $G$ is called $d$-rigid. What are the $d$-rigid graphs? This problem has been extensively studied since the 70s, and is still widely open for $d\geq 3$. It is studied mainly from algebraic geometry and combinatorial points of view. Variants of it, especially in dimensions 2 and 3, are of importance also beyond mathematics, e.g. in structural engineering, computational biology and more. I will focus on a quantitative version of rigidity via spectral analysis of the related stiffness matrix, including the construction of "rigidity expanders", generalizing expander graphs. Higher dimensional notions of rigidity and stiffness matrices, and their relation to the study of polytopes, will be addressed too.