3. Rigidity
-
Definition (Measurement Set). Given a finite graph $G = (V, E)$ with $|V| = n$, $|E| = m$, and $d \geq 2$, let $m_G: \mathbb{C}^{dn} \rightarrow \mathbb{C}^m$ map point configurations of $G$ to edge lengths defined by $m_G(i, j) = (p_i - p_j) \cdot (p_i - p_j)$ where $(\cdot)$ is the usual (non-complex) dot product. Then the measurement set of $G$ is the set $M_G$ defined by the Zariski closure of the images of $m_G$.Known
Problem 3.1.
[Louis Theran] Suppose $G$ is redundantly rigid in $\mathbb{R}^d$. If $H$ is another graph with $n$ vertices and $m$ edges with $M_G = M_H$ then is $G \simeq H$?- The statement holds if $G$ is globally rigid.
- For $d=2$, 3-connectedness and redundant rigidity imply global rigidity. Hence, for $d=2$ the statement is true if $G$ is 3-connected.
- In fact, just 3-connectedness of $G$ is sufficient for the following: For any $d$, if $G$ and $H$ have the same Euclidean measurement sets $M^{\mathbb{E}}_G = M^{\mathbb{E}}_H$ (these are the measurement sets over $\mathbb{E}^{dn}$) then $G \simeq H$ such that the isomorphism is compatible with the edge lengths.
-
Ref: Fogelsanger: ‘ The generic rigidity of minimal cycles’, PhD Thesis, University of Cornell, Ithaca, NY, 1988.Vertex splitting (under certain requirements) preserves global rigidity, so if the surface has genus at most 1, then the conjecture holds, these results are proved in Jordan-Tanigawa ‘Global rigidity of triangulations with braces’. Proof idea is to fix the surface and then generate all triangulations via vertex splitting. Basis of induction is the set of irreducible triangulations (with respect to vertex splitting) which are globally rigid. The limitation of this approach, however, is that the number of irreducible triangulations grows very rapidly with the genus).
Problem 3.2.
[Shin-ichi Tanigawa] If $G$ is a 4-connected triangulation of a non-spherical closed 2-surface then is $G$ generically globally rigid in dimension 3?
What is needed is a new graph operation which (1) preserves global rigidity and (2) increases the genus of the triangulation. -
This question is an extension of Shin-ichi Tanigawa’s question in 3.2.
Background. (An idea of Bill Jackson.) Let $(G,p)$ be globally rigid in $\mathbb{R}^3$ and suppose $G'$ arises from G by a non-trivial vertex split which splits $v$ into $u$ and $v$. Define $(G',p')$ by setting $p'(x)=p(x)$ for all $x\in V(G)$ and $p'(u)=p(v)$. Then it is clear that $(G',p')$ is globally rigid in $\mathbb{R}^3$. Hence to show that $G'$ is globally rigid for some/all generic realizations it suffices to show that $(G',p')$ is infinitesimally rigid in $\mathbb{R}^3$. (Then we can perturb $(G',p')$ within a sufficiently small open neighborhood to find a nearby generic realization which is globally rigid.)
Hence the extension proposed below of Fogelsanger’s proof is one possible way to resolve Problem 3.2.Problem 3.3.
[Tony Nixon] Extend Fogelsanger’s proof that every triangulation of a closed, non-spherical, surface is infinitesimally rigid in 3-dimensions to apply in the case when two vertices $u,v$, such that $uv\in E$, are coincident. -
Known
Problem 3.4.
[Jozsef Solymosi] Let $f(n)$ be a function such that for any unit length graph $G$ with $n$ vertices, if $G$ has at least $f(n)$ edges then $G$ contains a non-trivial rigid subgraph (trivial means an edge). What is $f(n)$?- Only know $n \log (n) \leq f(n) \leq c n^{4/3}$.
- For non-unit distance frameworks with prescribed distances, $f(n) \le n^{3/2}$.
-
Problem 3.5.
[Brigitte Servatius] Is it possible to strengthen a theorem of Walter Whiteley (in A matroid on hypergraphs with applications in scene analysis and geometry, 1989) on body-pin frameworks in $d=2$, to say that $G=(B, J, I)$ has an independent realization in $\mathbb{R}^2$ where each body has all its joints at unit distance from each other if and only if $G$ satisfies $2i \le 3b +2j -3$ (should be true for every subgraph), where $i$ is the number of incidences, $j$ is the number of joints, and $b$ is the number of bodies? -
Problem 3.6.
[Orit Raz] In L. Lovasz’s paper ["Flats in Matroids and geometric graphs”], he considers the dimension of $span(F\cap h)$, where $F$ is a family of linear subspaces of $R^d$, $h$ is a subspace of codimension 1 in $\mathbb{R}^d$, and $F\cap h:=\{f\cap h \mid f\in F\}$. He proves that this dimension can be expressed as a certain minimum over all the partitions of the elements of $F$, given that $h$ satisfies a certain "general position” assumption. The questions are:
(i) Can the general position assumption in Lovasz’s theorem be relaxed?
(ii) Can one find a formula (in whatever terms) that applies to subspaces $h$ that are not necessarily in general position? -
Background. It is well known that if $G$ is independent in the generic 3-dimensional rigidity matroid then $G$ is $(3,6)$-sparse. If $k>5$ then this condition fails so we automatically have dependence. If $k\leq 4$ then a result of Jackson-Jordan ‘The d-dimensional rigidity matroid of sparse graphs’ shows that $G$ is independent if and only if $G$ is $(3,6)$-sparse. Hence only the case when $k=5$ is open. Perhaps it might be true that a 5-regular graph is independent if and only if it is $(3,6)$-sparse.
Problem 3.7.
[Tony Nixon] Determine which $k$-regular graphs are independent in the generic 3-dimensional rigidity matroid.
Cite this as: AimPL: Rigidity and flexibility of microstructures, available at http://aimpl.org/flexmicro.