Isostatic graphs and the Henneberg conjecture

Question

I have been reading "Combinatorial Rigidity" by Graver, Servatius and Servatius and I am interested in their chapter on rigidity in dimension $\geq$ 3. I have two questions.

1. What is the current status of the Henneberg conjecture (ie that every 2-extension of a 3-isostatic graph is isostatic?) The GSS book was published in '91. Is there a more recent account of this material?

2. In the above mentioned book they provide an example (due to Maehara and Woodall) that shows that there is a 4-isostatic graph and a 2-extension of that graph that is not isostatic. Briefly, the example is this. Start with the graph $K_6$ with an edge removed (clearly this is 4-isostatic since it is a 0-extension of $K_5$) and then perform a sequence of 7 successive 2-extensions to obtain $K_{7,6}$, which is known to be not 4-isostatic. So somewhere in the sequence we have the desired example. However, they leave it as an exercise to identify precisely where in the sequence the change from isostatic to not isostatic occurs. I have thought about this for a few days and it's not clear to me. Can anyone shed any light on this? (It is Exercise 5.8 in the book). I have no idea where to start. It is not even clear to me that the answer is independent of the particular sequence of 2-extensions that are chosen. I (think I) can see that it will not occur after the first 2-extension and it does not at the last step because we already have a $K_{6,6}$ inside the graph before the last step, but in between is a mystery to me.

It also seems clear that if I can understand the example from question 2, that it would help to clarify why the Henneberg conjecture is difficult.

Any help will be much appreciated.

Answer 1

Question 2 can be addressed computationally by computing the ranks of generic rigidity matrices corresponding to the sequence of graphs.

I'll show below that the 6th 2-extension for one choice of sequence creates a non-isostatic set from an isostatic one (because a $K_{6,6}$ is formed exactly then). I'm not sure how much this changes as we change the sequence of 2-extensions, nor even how much freedom we have in performing these 2-extensions if we want to go from $K_6$ to $K_{7,6}$. I suspect that the key is in the formation of the cycle $K_{6,6}$.

Below I share what I did in Mathematica; perhaps the code will be helpful for further experimentation. It is a bit tedious, so search this page for "G6" if you want to skip to the exciting part.

First, I wrote some ugly code to compute a 4 dimensional rigidity matrix. No doubt this can be improved.

(* p is a list of 4 dimensional vectors corresponding to vertex positions, 
E is a list of the pairs of vertices {i,j} (with i<j) that are joined by edges *)
RigidityMatrix4[p_, E_] := 
 Module[{e = Length[E], nd = Length[p] Length[p[[1]]], px, py, pz, pw},
  Table[
   px = p[[E[[j, 1]], 1]] - p[[E[[j, 2]], 1]];
   py = p[[E[[j, 1]], 2]] - p[[E[[j, 2]], 2]];
   pz = p[[E[[j, 1]], 3]] - p[[E[[j, 2]], 3]];
   pw = p[[E[[j, 1]], 4]] - p[[E[[j, 2]], 4]];
   Insert[Insert[Insert[Insert[
       Insert[Insert[Insert[Insert[
           Table[0, {nd - 8}], px, 4 E[[j, 1]] - 3], py, 
          4 E[[j, 1]] - 2], pz, 4 E[[j, 1]] - 1], pw, 4 E[[j, 1]]],
       -px, 4 E[[j, 2]] - 3], -py, 4 E[[j, 2]] - 2], -pz, 
     4 E[[j, 2]] - 1], -pw, 4 E[[j, 2]]], {j, e}]]

Here's a function to create the list of edges corresponding to a complete graph:

makecompletegraph[l_] :=  Reap[Do[If[i != j, Sow[{i, j}]], {i, l}, {j, i, l}]][[2, 1]]

Now I begin by creating $K_6$ and deleting the edge {5,6}. The output is a list of the edges as pairs of vertices:

G = makecompletegraph[6][[1 ;; 14]]

{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}}

I next compute the number of nontrivial infinitesimal motions of a generic embedding of G and the number of redundancies among its edges:

R = RigidityMatrix4[RandomReal[{0, 1}, {6, 4}], G];
{MatrixRank[NullSpace[R]] - 10, Length[G] - MatrixRank[R]}

{0,0}

Thus G is isostatic.

I now perform the first 2-extension, by deleting the edges {1,2} and {3,4} and connecting a new vertex 7 to vertices 1 through 6, and check that the resulting graph "G1" is isostatic:

G1 = Join[Select[G, # != {1, 2} && # != {3, 4} &], Table[{i, 7}, {i, 6}]]
R1 = RigidityMatrix4[RandomReal[{0, 1}, {7, 4}], G1];
{MatrixRank[NullSpace[R1]] - 10, Length[G1] - MatrixRank[R1]}

{{1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}}

{0,0}

In the second step, I remove {1,3} and {2,4} and attach vertex 8 to vertices 1 through 6 to form G2, which is also isostatic:

G2 = Join[Select[G1, # != {1, 3} && # != {2, 4} &], Table[{i, 8}, {i, 6}]]
R2 = RigidityMatrix4[RandomReal[{0, 1}, {8, 4}], G2];
{MatrixRank[NullSpace[R2]] - 10, Length[G2] - MatrixRank[R2]}

{{1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 5}, {2, 6}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}}

{0,0}

Next {1,5} and {2,6} are removed and vertex 9 is attached to vertices 1 through 6 forming the isostatic G3:

G3 = Join[Select[G2, # != {1, 4} && # != {2, 5} &], Table[{i, 9}, {i, 6}]]
R3 = RigidityMatrix4[RandomReal[{0, 1}, {9, 4}], G3];
{MatrixRank[NullSpace[R3]] - 10, Length[G3] - MatrixRank[R3]}

{{1, 5}, {1, 6}, {2, 3}, {2, 6}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}, {6, 9}}

{0,0}

{1,5} and {2,6} are removed; vertex 10 is attached, G4 is isostatic:

G4 = Join[Select[G3, # != {1, 5} && # != {2, 6} &], Table[{i, 10}, {i, 6}]]
R4 = RigidityMatrix4[RandomReal[{0, 1}, {10, 4}], G4];
{MatrixRank[NullSpace[R4]] - 10, Length[G4] - MatrixRank[R4]}

{{1, 6}, {2, 3}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}, {6, 9}, {1, 10}, {2, 10}, {3, 10}, {4, 10}, {5, 10}, {6, 10}}

{0,0}

{1,6} and {2,3} are removed; vertex 11 is attached, G5 is isostatic:

G5 = Join[Select[G4, # != {1, 6} && # != {2, 3} &], Table[{i, 11}, {i, 6}]]
R5 = RigidityMatrix4[RandomReal[{0, 1}, {11, 4}], G5];
{MatrixRank[NullSpace[R5]] - 10, Length[G5] - MatrixRank[R5]}

{{3, 5}, {3, 6}, {4, 5}, {4, 6}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}, {6, 9}, {1, 10}, {2, 10}, {3, 10}, {4, 10}, {5, 10}, {6, 10}, {1, 11}, {2, 11}, {3, 11}, {4, 11}, {5, 11}, {6, 11}}

{0,0}

{3,5} and {4,6} are removed and vertex 12 is attached. The resulting graph G6 is not isostatic! Of course, this is because a $K_{6,6}$ is formed.

G6 = Join[Select[G5, # != {3, 5} && # != {4, 6} &], Table[{i, 12}, {i, 6}]]
R6 = RigidityMatrix4[RandomReal[{0, 1}, {12, 4}], G6];
{MatrixRank[NullSpace[R6]] - 10, Length[G6] - MatrixRank[R6]}

{{3, 6}, {4, 5}, {1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}, {6, 9}, {1, 10}, {2, 10}, {3, 10}, {4, 10}, {5, 10}, {6, 10}, {1, 11}, {2, 11}, {3, 11}, {4, 11}, {5, 11}, {6, 11}, {1, 12}, {2, 12}, {3, 12}, {4, 12}, {5, 12}, {6, 12}}

{1,1}

Just for completeness, I performed the last 2-extension; removing {3,6} and {4,5} and attaching vertex 13. You can see this is $K_{7,6}$:

G7 = Join[Select[G6, # != {3, 6} && # != {4, 5} &], Table[{i, 13}, {i, 6}]]
R7 = RigidityMatrix4[RandomReal[{0, 1}, {13, 4}], G7];
{MatrixRank[NullSpace[R7]] - 10, Length[G7] - MatrixRank[R7]}

{{1, 7}, {2, 7}, {3, 7}, {4, 7}, {5, 7}, {6, 7}, {1, 8}, {2, 8}, {3, 8}, {4, 8}, {5, 8}, {6, 8}, {1, 9}, {2, 9}, {3, 9}, {4, 9}, {5, 9}, {6, 9}, {1, 10}, {2, 10}, {3, 10}, {4, 10}, {5, 10}, {6, 10}, {1, 11}, {2, 11}, {3, 11}, {4, 11}, {5, 11}, {6, 11}, {1, 12}, {2, 12}, {3, 12}, {4, 12}, {5, 12}, {6, 12}, {1, 13}, {2, 13}, {3, 13}, {4, 13}, {5, 13}, {6, 13}}

{2,2}

Answer 2

Is there a more recent account of this material?

I can update you to 2004, but not later. There is a discussion around this topic by Walter Whiteley in the Handbook of Discrete and Computational Geometry, CRC Press, pp.1335-6, 2004 (which you can access via Google Books). He says,

There is no combinatorial characterization of generically 3-isostatic graphs. There are several related conjectures, due to Dress, Graver, and Tay and Whiteley, that may be correct but are unproven. [...] Every 3-isostatic graphi is generated by an "extended Hennenberg 3-construciton," which adds these two moves to the simpler edge splitting and vertex addition. What is unproven is that only 3-isostatic graphs are generated in this way.