Colloquium: Tuesday, June 7, 2022. Speaker: Eran Nevo (Hebrew University). Title: “Directions in graph rigidity”.
The talk will be on Zoom. The link for the meetings is:
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>=3. It is studied mainly from algebraic geometry, linear algebra, and combinatorics 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 discuss various directions and open problems in graph rigidity, including:
combinatorial characterization, numerical consequences, non-generic rigid embeddings, rigidity of random graphs, and a quantitative version of rigidity via spectral analysis of the related stiffness matrix.