Discrete Geometry and Combinatorics Seminar

Robert ConnellyCornell University
Universal rigidity

Monday, November 16, 2015 - 2:30pm
Malott 206

A framework is a finite graph $G$ whose vertices are in $\mathbb{R}^d$ and whose edges are fixed length bars. It is universally rigid if it is rigid not just in $\mathbb{R}^d$ but in any $\mathbb{R}^D$, $D>d$, containing $\mathbb{R}^d$. It turns out that if any framework is universally rigid, there is sequence of matrix stress certificates that guarantee universal rigidity, and for the special case of complete bipartite graphs, the certificate simplifies to the condition that the partitions are not separable by a quadric surface. Furthermore for any abstract graph, a theorem of L. Lovasz (interpreted by A. Alfakih) implies that if it is appropriately connected, it always has a universally rigid realization in $\mathbb{R}^d$. If the graph is generically globally rigid when restricted to $\mathbb{R}^d$, then it has a universally rigid and infinitesimally rigid configuration. This provides a certificate for generic global rigidity that gives an explicit graph that is globally rigid in $\mathbb{R}^d$, which had not been known in dimension three or higher. This is joint work with Steven Gortler.