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 (noncomplex) dot product. Then the measurement set of $G$ is the set $M_G$ defined by the Zariski closure of the images of $m_G$.
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$, 3connectedness and redundant rigidity imply global rigidity. Hence, for $d=2$ the statement is true if $G$ is 3connected.
 In fact, just 3connectedness 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.
Problem 3.2.
[Shinichi Tanigawa] If $G$ is a 4connected triangulation of a nonspherical closed 2surface 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 Shinichi 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 nontrivial 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, nonspherical, surface is infinitesimally rigid in 3dimensions to apply in the case when two vertices $u,v$, such that $uv\in E$, are coincident. 
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 nontrivial rigid subgraph (trivial means an edge). What is $f(n)$? Only know $n \log (n) \leq f(n) \leq c n^{4/3}$.
 For nonunit 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 bodypin 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? 
Problem 3.7.
[Tony Nixon] Determine which $k$regular graphs are independent in the generic 3dimensional rigidity matroid.
Cite this as: AimPL: Rigidity and flexibility of microstructures, available at http://aimpl.org/flexmicro.