Directions in graph rigidity

Speaker
Eran Nevo, HUJI
Date
15/05/2022 - 13:00 - 12:00Add to Calendar 2022-05-15 12:00:00 2022-05-15 13:00:00 Directions in graph rigidity   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. Seminar rm, Math Bldg 216 אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Seminar rm, Math Bldg 216
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.

Last Updated Date : 11/05/2022