Chapter 2 Combinatorial Torelli

Let \(P = P(G)\) be a polytope in a real affine space \(S = S(G)\) associated with a graph \(G\) of principal series. We will reconstruct the graph from the affine relations between the vertices of the polytope (which we further call rays to distinguish them from vertices of the graph).

2.1 Algorithm

  1. The center of mass of all rays equals \(0\).

  2. Principal step. In the set of all semi-sums of all pairs of distinct rays record those that appear at least twice, i.e. record all the centers of the parallelograms that can be obtained as convex envelopes of some pairs of diagonals. Claim: these are exactly the vectors \(±e(i)\) for all (internal) edges \(i\). So at this step we have reconstructed the set of (internal) edges of the graph.

  3. Let \(p(i)\) be the coordinates of the ray \(p=p(v,s)\) in a basis \(\{±e(i)\}\). The vertices and the adjacency matrix are given by the image of the map \(p \mapsto \{i : p(i) ≠ 0\}\).

2.2 The proof of correctness

The first two assumptions imply that all vectors \(p(v,s)\) are distinct.

The second assumption implies that each vector \(p(v,s)\) in the basis \(\{e(i)\}\) is a permutation of \((±1,±1,±1,0,0,...,0)\). So all vectors \(p(v,s)\) are equidistant from \(0\) with respect to the Euclidean norm in which the basis \(e(i)\) is orthonormal. This implies that vectors \(p(v,s)\) are convex independent, thus their set coincides with the set of the rays (vertices of the polytope \(P(G)\)). The latter is partitioned into quadruples \(\{p(v,s)\}\) enumerated by vertices \(v \in V(G)\). If \(x,y,z,w\) are four distinct admissible sign assignments then there is a linear relation \[\begin{equation} p(v,x) + p(v,y) + p(v,z) + p(v,w) = 0, \end{equation}\] so the center of mass of the rays in any such quadruple is \(0\), hence the center of mass of all the rays is \(0\). Step 0 is proved.

If a vertex \(v\in V(G)\) is incident to edges \(i,j,k\) then the \(6\) semi-sums of two vectors from a quadruple are equal to \(±e(i),±e(j),±e(k)\). So if \(i\) is an (internal non-loop) edge connecting vertices \(v\) and \(v'\) there are at least two distinct ways to write \(e(i)\) as a semi-sum of two vectors: \(2 e(i) = p(v,x) + p(v,y) = p(v',z') + p(v',w')\), and similarly \(-2 e(i) = p(v,z) + p(v,w) = p(v',x') + p(v',y')\). To prove the claim of Step 1 it remains to show that no other vector has two representations as a semi-sum.

Suppose that for some vertices \(u,u',v,v' \in V(G)\) and signs \(x,y,z,w\) there is a relation \[\begin{equation} p(u,x) + p(u',y) = p(v,z) + p(v',w) \end{equation}\] For each vertex consider the parity of times it appears in a relation. The relation implies that for every edge \(i\) the parities of the adjacent vertices are equal. So the assigned parities of vertices are constant in every connected component. Since we have only four terms in a relation, number of odd vertices is at most four, so in every connected component with at least 5 vertices all vertices are even.

Thus either \(u=u'=v=v'\), but then six semi-sums are all distinct, or there are two vertices and each appears in the relation twice. Hence either each vertex appears only on one side of the equation or both vertices appear on both sides.

If each vertex appears on its own side then we have an equation \(±e(i) = ±e(j)\) where \(i\) is an edge adjacent to \(u\) and \(j\) is an edge adjacent to \(v\), thus \(i=j\) and vertices \(u,v\) are adjacent to each other.

Finally, the equation \[\begin{equation} \label{ssd} p(v,x) + p(v',w) = p(v,y) + p(v',z) \end{equation}\] is equivalent to \(p(v,x) - p(v,y) = p(v',z) - p(v',w)\) (where the differences are zero iff the summands on both sides are identical). For every vertex \(v\) with edges \(i,j,k\) the \(12\) semi-differences are equal to \(±e(i)±e(j),±e(i)±e(k),±e(j)±e(k)\). So if for two distinct vertices \(v,v' \in V(G)\) and some sign choices \(x,y,z,w\) the relation holds, then vertices \(v\) and \(v'\) would be connected by at least two edges, contradicting to the third assumption.

Now Step 1 is justified and Step 2 is straightforward.