format: text

text:
# Criteria for Balance in Abelian Gain Graphs, with Applications to Piecewise-Linear Geometry11footnote 1We thank Keith Dennis and Kenneth S. Brown for very helpful discussions.

## 1 Introduction

A *gain graph* $`(\mathrm{\Gamma },g,G)`$ consists of a graph $`\mathrm{\Gamma }=(V,E)`$, a group $`G`$, and a homomorphism $`g`$ from the free group $`F_E`$ on the edges of $`\mathrm{\Gamma }`$ to $`G`$. We call $`g`$ the *gain map* and $`G`$ the *gain group*.444See, e.g., Zaslavsky (1989), Section 5, for the basic theory of gain graphs. Gain graphs have been called *voltage graphs* in graph embedding theory—e.g., in Gross & Tucker (1987); we eschew the term “voltage” because gains do not have to obey Kirchhoff’s voltage law. (One thinks of the edges of $`G`$ as oriented in an arbitrary but fixed way). Gain graphs have appeared in pure mathematics, physics, operations research, psychology, and discrete geometry, among many other areas (see Zaslavsky’s annotated bibliography (1998) for a survey).

The simplest gain graphs are those in which every simple closed walk on $`\mathrm{\Gamma }`$ lies in the kernel of $`g`$; such gain graphs are called *balanced*. If $`\mathrm{\Gamma }`$ is connected, $`(\mathrm{\Gamma },g,G)`$ is balanced if and only if $`\pi (\mathrm{\Gamma })\mathrm{Ker}g`$. Since for general gain graphs one can treat each component separately, we shall assume throughout that $`G`$ is connected. A basic problem is how to tell whether or not a gain graph is balanced. We investigate this problem when $`G`$ is abelian; then we call $`(\mathrm{\Gamma },g,G)`$ an *abelian gain graph*. We propose here a criterion for balance in abelian gain graphs that is broader than previous ones, but which has the drawback that it is not valid for all groups. Our topics are, first, the problem of describing the abelian gain groups for which it is valid and, second, an application of the criterion to a problem of polyhedral geometry.

To state the criterion we must first define a “circle” and a “cycle” in a graph. A *circle* is the edge set of a nontrivial simple closed walk (a walk in which no vertex or edge is repeated, except that the initial and final vertices are the same). There are two kinds of cycles of concern to us:555The graph-theory literature contains at least five incompatible definitions of the term “cycle”. they are *integral cycles*, i.e., elements of $`Z_1(\mathrm{\Gamma })=\mathrm{Ker}`$ where $``$ is the standard 1-dimensional boundary operator of cellular homology of $`\mathrm{\Gamma }`$, and *binary cycles*, i.e., elements of $`Z_1(\mathrm{\Gamma };_2)`$. There are natural epimorphisms

$$\pi (\mathrm{\Gamma })\stackrel{𝑎}{}Z_1(\mathrm{\Gamma })\stackrel{[]}{}Z_1(\mathrm{\Gamma };_2)$$

that consist, respectively, of abelianization and reduction of coefficients modulo 2. Suppose that $`b`$ is a binary cycle: a *cyclic orientation* of $`b`$ is any closed walk $`\stackrel{~}{b}`$ for which $`[\stackrel{~}{b}^a]=b`$. If $`B`$ is a set of binary cycles, a *cyclic orientation of $`B`$* is any set $`\stackrel{~}{B}=\{\stackrel{~}{b}:bB\}`$ of cyclic orientations of the members of $`B`$. This definition is very broad: a binary cycle has many cyclic orientations; also, edges may appear in $`\stackrel{~}{b}`$ that are not in the support of $`b`$, provided that each such edge appears an even number of times in $`\stackrel{~}{b}`$. Thus, a binary cycle with disconnected support can have a cyclic orientation, which is always connected. In general, there is no cyclic orientation of a cycle that can reasonably be regarded as canonical, except in the case of a binary cycle whose support is a circle.

Now, our test for balance:

Definition.  Let $`(\mathrm{\Gamma },g,G)`$ be a gain graph and $`B`$ be a basis of $`Z_1(\mathrm{\Gamma };_2)`$. We say that $`B`$ *passes the Binary Cycle Test* if it has a cyclic orientation $`\stackrel{~}{B}`$ such that all elements of $`\stackrel{~}{B}`$ have gain 1. We say the Binary Cycle Test is *valid for $`(\mathrm{\Gamma },g,G)`$* if the existence of a basis $`B`$ that passes the Binary Cycle Test implies that $`(\mathrm{\Gamma },g,G)`$ is balanced. We say the Binary Cycle Test is *valid* for a family of graphs $`𝒢`$ and a family of groups $``$ if it is valid for every gain graph $`(\mathrm{\Gamma },g,G)`$ with $`\mathrm{\Gamma }𝒢`$ and $`G`$.

Our main results are that the Binary Cycle Test is valid for any abelian gain group that has no odd torsion if the graph is finite (Theorem 3.3) or if the gain group has no nontrivial infinitely 2-divisible elements (Theorem 3.5). We also show an infinite graph that fails the Binary Cycle Test for all gain groups that have an infinitely 2-divisible element other than the identity. (In Rybnikov & Zaslavsky (20xx) we prove that for any gain group with non-trivial elements of odd order there is a graph for which the Binary Cycle Test does not work. Focussing on properties of the gain graph that are due to the gain group rather than the graph is how the present paper differs from that one.)

In most applications to physics, psychology, or operations research, the gain graphs are finite and have $`_2`$ or $`^{}`$ as the gain group. Groups $`^{}`$ or $`^d`$ tend to appear in discrete-geometry applications such as Voronoi’s generatrix construction and the Maxwell–Cremona correspondence. The Binary Cycle Test applies to such situations, since all these groups are abelian and do not have odd torsion. However, if the gain graph is infinite, our results do not apply when $`G=^{}`$ or $`^d`$, since these groups are 2-divisible. We know that for certain particular binary cycle bases their passing the Binary Cycle Test does imply balance even then, but they have to be carefully selected, as Example 7.1 shows.

The reason we need the Binary Cycle Test rather than a simpler test for balance of $`(\mathrm{\Gamma },g,G)`$, such as the existence of a set of balanced circles that form a fundamental system of circles (i.e., the set of circles obtained from a fixed spanning tree by adjoining each nontree edge), is that, in applications, often a basis of the binary cycle space is given to us or is in some way naturally associated with the problem, so we are not free to choose the basis, or the geometry may yield information about the gains only of certain cycles that are not a fundamental system or otherwise tractable.

In Euclidean space, the sphere, or hyperbolic space, gain graphs are a natural setting for problems of existence and classification of tilings with prescribed restrictions on the group or the tiles, and of $`d+1`$-dimensional piecewise-linear realization of $`d`$-manifolds with given projection. Among important examples are Coxeter’s theorem reducing the classification of reflection groups to that of Coxeter simplices (1934), Alexandrov’s space-filling theorem (1954), Voronoi’s (1908) construction of a generatrix (*generatice* in the French original), the Maxwell–Cremona correspondence and its generalizations (see Crapo & Whiteley, 1993; Rybnikov, 1999; Erdahl, Rybnikov, & Ryshkov, 2001), colorings of graphs and polyhedra (Ryshkov & Rybnikov, 1997), etc. In Section 6 we demonstrate the appropriateness of gain graphs by applying the Binary Cycle Test to generalize a theorem of Voronoi (1908), that any simple tiling of $`^d`$ is the projection of a (convex) PL-surface which, given the tiling, is uniquely determined by $`d+2`$ free real parameters. (A spline theorist would say that the dimension of the space of $`C_1^0`$-splines over the tiling is $`d+2`$.) Such a surface is called a *(convex) lifting of the tiling to* $`^{d+1}`$. It is known that the notion of lifting and the space of liftings can be defined for any PL-realization of a homology $`d`$-manifold in $`^d`$. Our generalization consists in showing that the dimension of the space of liftings of any non-degenerate PL-realization in $`^d`$ of a homology $`d`$-manifold $``$ with $`H_1(;_2)=0`$ is $`d+2`$, provided that each $`(d3)`$-cell of $``$ is incident to exactly four $`d`$-cells. This application was chosen because in the course of the proofs gain graphs appear in a number of different geometric guises and we employ the Binary Cycle Test several times.

Another application of the Binary Cycle Test is to Voronoi’s conjecture on parallelohedra, which states that any parallelohedron is an affine copy of the Dirichlet domain of a lattice. Deza and Grishukhin (2003) recently gave a number of combinatorial reformulations of Voronoi’s conjecture that are essentially gain-graphical. The proof of the Voronoi conjecture can be reduced to a number of questions about a certain type of finite gain graph with gain group $`^{}`$, called the *Venkov graph*. (See Ordine (2002), Rybnikov (2002a,b), and Deza & Grishukhin (2003) for definitions and examples.) We have noticed that the Binary Cycle Test simplifies attacking these questions, because in the case of Venkov graphs it is much easier to look for a basis of the binary cycle space rather than of the integral cycle space. Very recently Ordine (2004) made a major advance in Voronoi’s conjecture by proving an important special case, where the dual figures for the stars of $`(d3)`$-cells of the tiling are restricted to tetrahedra, octahedra, and pyramids. The Binary Cycle Test can be applied to greatly simplify his proof; we hope to explain this elsewhere.

## 2 Preliminaries

Our graphs may be infinite. Loops (edges with two equal endpoints) and multiple edges are allowed. We assume that $`\mathrm{\Gamma }`$ is connected and that it has a fixed (but arbitrary) orientation.

A circle $`C`$ can be written as the edge set of a simple closed walk in a way that is unique up to choice of initial vertex and direction. Then it depends only on $`C`$, not on the choice of walk, whether the walk is in $`\mathrm{Ker}g`$. If it is, we say $`C`$ is *balanced*.

If $`\stackrel{~}{w}`$ is a closed walk on $`\mathrm{\Gamma }`$, denote by $`𝐰`$ the corresponding element $`\stackrel{~}{w}^a`$ of $`Z_1(\mathrm{\Gamma })`$. If $`𝐰Z_1(\mathrm{\Gamma })`$, denote by $`[𝐰]`$ the corresponding element of $`Z_1(\mathrm{\Gamma };_2)`$.

We denote by $`\pi (\mathrm{\Gamma })`$ the fundamental group of $`\mathrm{\Gamma }`$. The *essential gain group* of a gain graph is $`g(\pi (\mathrm{\Gamma }))`$. It is well defined up to conjugation in $`G`$. Evidently, $`(\mathrm{\Gamma },g,G)`$ is balanced if and only if the essential gain group is trivial.

Naturally, $`g`$ induces a homomorphism from $`\pi (\mathrm{\Gamma })`$ to $`G`$ and from $`E`$, the free abelian group on $`E`$, to $`G/G^{}`$, where, as usual, $`G^{}`$ denotes the commutator subgroup. Hence, $`g`$ induces a homomorphism from $`Z_1(\mathrm{\Gamma })`$, the abelianization of $`\pi (\mathrm{\Gamma })`$, to $`G/G^{}`$.

A *cyclic orientation*, or *lifting to the fundamental group*, of an element $`b`$ of $`Z_1(\mathrm{\Gamma };_2)`$ is any element $`\stackrel{~}{b}`$ of $`\pi (\mathrm{\Gamma })`$ whose abelianization modulo 2 is $`b`$. A circle has natural cyclic orientations obtained by taking an element of $`\pi (\mathrm{\Gamma })`$ corresponding to a simple walk around the circle in either direction from any starting point. A *lifting of $`b`$ to the cycle space* is the image $`𝐛`$ in $`Z_1(\mathrm{\Gamma })`$ of a cyclic orientation of $`b`$. If $`B`$ is a basis of $`Z_1(\mathrm{\Gamma };_2),`$ then denote by $`\stackrel{~}{B}`$ a cyclic orientation of $`B`$. As one can see from our notation, if $`b`$ denotes an element of the binary cycle space, then $`𝐛`$ denotes one of the possible liftings of $`b`$ to the cycle space, and $`\stackrel{~}{b}`$ is one of the liftings of $`b`$ to the fundamental group. If $`𝐰Z_1(\mathrm{\Gamma })`$, denote by $`[𝐰]`$ the corresponding element of $`Z_1(\mathrm{\Gamma };_2)`$.

If $`H\pi (\mathrm{\Gamma })`$, then $`H^a`$ denotes $`H/(\pi (\mathrm{\Gamma })^{}H)`$, the abelianization of $`H`$ with respect to $`\pi (\mathrm{\Gamma })`$; that is, $`H^a`$ is the image of $`H`$ in $`Z_1(\mathrm{\Gamma })`$. If $`L,MA`$, we denote by $`L/M`$ the image of $`L`$ in $`A/M`$; in particular, $`L/2A`$ is $`L`$ reduced modulo $`2`$.

## 3 The Test for Abelian Groups

###### Lemma 3.1

Let $`A`$ be a free abelian group, and let $`h`$ be a homomorphism from $`A`$ to $`G`$, an abelian group without odd torsion. Let $`L`$ be a subgroup of $`A`$ such that $`h(L)=0`$ and $`L/2A=A/2A`$. Suppose $`K`$ is a subgroup of $`A`$ such that $`K/(LK)`$ does not have elements of infinite order. Then $`h(K)=0`$.

Proof. Suppose there is $`𝐲K`$ such that $`h(𝐲)0`$. Since $`h(L)=0`$, $`𝐲L`$. There is a minimal $`l>1`$ such that $`l𝐲L`$. Let $`l=2^ea`$, where $`a`$ is odd. Denote $`a𝐲`$ by $`𝐱`$. Notice $`e>0`$, since otherwise $`h(𝐱)`$ would have odd order in $`G`$.

Now, $`h(a𝐲)0`$, since otherwise $`h(𝐲)`$ would have odd order in $`G`$. Then $`2^e`$ is the order of $`𝐱`$ in $`K/(LK)`$ and $`e=\mathrm{min}\{k2^k𝐱L\}`$. Let $`\{𝐛_i\}`$ be a basis of $`L`$, so that $`2^e𝐱=l_i𝐛_i`$. Since $`L/2A=A/2A`$, $`\{[𝐛_i]\}_i`$ generates $`A/2A`$. Thus $`[𝐱]=\lambda _i[𝐛_i]`$, i.e., $`𝐱=\lambda _i𝐛_i+2𝐳`$ for some $`𝐳A`$. We have $`2^e𝐱=\lambda _i2^e𝐛_i+2^{e+1}𝐳`$. Thus $`(l_i\lambda _i2^e)𝐛_i2A`$ and all $`l_i`$ are divisible by $`2`$, i.e., $`l_i=2m_i`$, $`m_i`$. Since $`e>0`$ we have $`2^{e1}𝐱=m_i𝐛_iL`$. This contradicts the choice of $`e`$ as $`\mathrm{min}\{k2^k𝐱L\}`$. Therefore $`h(K)=0.`$

###### Lemma 3.2

Let $`(\mathrm{\Gamma },g,G)`$ be a gain graph, where $`G`$ is an abelian group without odd torsion, and let $`K`$ be a subgroup of $`Z_1(\mathrm{\Gamma })`$. If a basis $`B`$ of $`Z_1(\mathrm{\Gamma };_2)`$ has some cyclic orientation $`\stackrel{~}{B}`$ that lies in the kernel of $`g`$, and if $`K/(\stackrel{~}{B}^aK)`$ does not have elements of infinite order, then any lifting of $`K`$ to $`\pi (\mathrm{\Gamma })`$ lies in $`\mathrm{Ker}g`$.

Proof. Denote $`\stackrel{~}{B}^a`$ by $`L`$. The homomorphism $`g`$ induces, in a natural way, a homomorphism $`h`$ from $`Z_1(\mathrm{\Gamma })`$ to $`G`$. Obviously, $`h(L)=0`$ and $`L/2Z_1(\mathrm{\Gamma })=Z_1(\mathrm{\Gamma })/2Z_1(\mathrm{\Gamma })=Z_1(\mathrm{\Gamma };_2).`$ We can now apply Lemma 3.1 and conclude that $`K`$ lies in the kernel of $`h`$. Since $`G`$ is abelian, any lifting of $`K`$ to $`\pi (\mathrm{\Gamma })`$ also lies in $`\mathrm{Ker}g`$.

###### Theorem 3.3

Suppose $`\mathrm{\Gamma }`$ is a *finite* graph and $`G`$ is an abelian group without odd torsion. If all elements of a basis $`B`$ of $`Z_1(\mathrm{\Gamma };_2)`$ have cyclic orientations that lie in $`\mathrm{Ker}g`$, then $`(\mathrm{\Gamma },g,G)`$ is balanced.

Proof. Since $`\mathrm{\Gamma }`$ is finite, $`\mathrm{rank}\stackrel{~}{B}^a=\mathrm{rank}Z_1(\mathrm{\Gamma })`$, so all elements of $`Z_1(\mathrm{\Gamma })/\stackrel{~}{B}^a`$ have finite order. Now apply Lemma 3.2 with $`K=Z_1(\mathrm{\Gamma })`$.

###### Lemma 3.4

Let $`G`$ be an abelian group without odd torsion. If some basis $`B`$ of $`Z_1(\mathrm{\Gamma };_2)`$ has a cyclic orientation $`\stackrel{~}{B}`$ that lies in $`\mathrm{Ker}g`$, then $`g(\pi (\mathrm{\Gamma }))`$ is 2-divisible.

Proof. The elements of $`Z_1(\mathrm{\Gamma })`$ that have finite order in $`Z_1(\mathrm{\Gamma })/\stackrel{~}{B}^a`$ form a subgroup in $`Z_1(\mathrm{\Gamma })`$, which we denote by $`F`$. Since $`F/\stackrel{~}{B}^a`$ does not have elements of infinite order, Lemma 3.2 with $`K=F`$ implies that $`g(F)=0`$. Thus if $`𝐲𝐱F`$, $`g(𝐲𝐱)=0.`$ Therefore, $`g`$ induces an epimorphism $`h`$ from $`Z_1(\mathrm{\Gamma })/F`$ onto $`g(\pi (\mathrm{\Gamma }))`$.

Let $`𝐲Z_1(\mathrm{\Gamma }).`$ Since $`\stackrel{~}{B}^aF`$ and $`[\stackrel{~}{B}^a]=Z_1(\mathrm{\Gamma },_2)`$, there is $`𝐱F`$ such that $`𝐲𝐱=2𝐳`$ for some $`𝐳Z_1(\mathrm{\Gamma })`$. Thus $`𝐲2𝐳+F,`$ and $`𝐲+F=2𝐳+F=2(𝐳+F)`$ as posets. Therefore all elements of $`Z_1(\mathrm{\Gamma })/F`$ are 2-divisible.

Let $`ag(\pi (\mathrm{\Gamma }))`$. Since the homomorphism $`h`$ from $`Z_1(\mathrm{\Gamma })/F`$ is onto $`g(\pi (\mathrm{\Gamma }))`$, there is $`𝐲Z_1(\mathrm{\Gamma })/F`$ such that $`h(𝐲)=a`$. Since $`𝐲`$ is 2-divisible, $`a`$ is also 2-divisible: $`a=h(𝐲)=h(2𝐳)=2h(𝐳).`$

###### Theorem 3.5

Let $`G`$ be an abelian group, without odd torsion, which has no infinitely 2-divisible elements other than $`0`$. If some basis $`B`$ of $`Z_1(\mathrm{\Gamma };_2)`$ has a cyclic orientation $`\stackrel{~}{B}`$ that lies in $`\mathrm{Ker}g`$, then $`(\mathrm{\Gamma },g,G)`$ is balanced.

Proof. If $`Z_1(\mathrm{\Gamma })/\stackrel{~}{B}^a`$ does not have elements of infinite order, then, an application of Lemma 3.2 with $`K=Z_1(\mathrm{\Gamma })`$ implies that $`(\mathrm{\Gamma },g,G)`$ is balanced. If $`Z_1(\mathrm{\Gamma })/\stackrel{~}{B}^a`$ has elements of infinite order, then by Lemma 3.4 $`g(\pi (\mathrm{\Gamma }))`$ is 2-divisible, which is only possible if $`g(\pi (\mathrm{\Gamma }))=0`$. Thus $`(\mathrm{\Gamma },g,G)`$ is balanced.

###### Corollary 3.6

Suppose $`\mathrm{\Gamma }`$ is a *finite* graph and $`G`$ is a free group. If all elements of a basis $`B`$ of $`Z_1(\mathrm{\Gamma };_2)`$ have cyclic orientations that lie in $`\mathrm{Ker}g`$, then $`(\mathrm{\Gamma },g,G)`$ is balanced.

Proof. $`g`$ induces a homomorphism $`\overline{g}`$ from $`\pi (\mathrm{\Gamma })`$ into $`G/G^{}.`$ $`G/G^{}`$ is a free abelian group and, therefore, does not have torsion or infinitely 2-divisible elements. By Theorem 3.5, $`\mathrm{Im}\overline{g}=0.`$ But this can only happen if $`\mathrm{Im}g=1`$, because $`\mathrm{Ker}g`$ is a free group whose abelianization is $`\mathrm{Ker}\overline{g}`$.

###### Corollary 3.7

Let $`g`$ be a group such that $`G/G^{}`$ has no torsion or has only 2-torsion. Let $`(\mathrm{\Gamma },g,G)`$ be a gain graph whose gain group is $`G`$. If there is a basis $`B`$ of the binary cycle space $`Z_1(\mathrm{\Gamma };_2)`$ such that for each $`bB`$ there is a cyclic orientation $`\stackrel{~}{b}`$ for which $`g(\stackrel{~}{b})G^{}`$, then every circle has gain in $`G^{}`$.

## 4 Counterexamples

In discrete geometry the case of an infinite gain graph with an abelian 2-divisible group of gains, such as $`^n`$ or $`^{}`$ is one of the most typical ones (see Ryshkov & Rybnikov (1997), Rybnikov (1999)). In such applications the cycle basis for which we can verify the balance property normally consists of *circles*. Might the *Circle Test*, i.e., the Binary Cycle Test where all elements of the binary basis are known to be *circles*, work for infinite graphs with 2-divisible groups of gains? Unfortunately, not. We construct an infinite gain graph with a 2-divisible, torsion-free group of gains, unbalanced yet having a binary circle basis all of whose elements are balanced.

*A more detailed description of examples considered, or only mentioned, in this section is given in Appendix, following the paper.*

###### Example 4.1

The graph is shown in Figure 1. We use the following notation for elements of $`Z_1(\mathrm{\Gamma })`$:

$$𝐞_k=D_kL_kD_{k+1}U_kD_k,𝐠_k=L_kL_{k+1}D_{k+1}L_k,𝐡_k=U_kD_{k+1}U_{k+1}U_k.$$

Then $`\{𝐞_k,𝐠_k,𝐡_k\}_{k1}`$ is an integral circle basis of $`\mathrm{\Gamma }`$. As usual, we denote an element of $`Z_1(\mathrm{\Gamma };_2)`$ corresponding to $`𝐱Z_1(\mathrm{\Gamma })`$ by $`[𝐱]`$. Let

$$𝐁=\{𝐞_k+𝐠_k+𝐡_k\}_{k1}\{𝐠_k+𝐞_{k+1}\}_{k1}\{𝐡_k+𝐞_{k+1}\}_{k1}$$

and let $`B=\{[𝐛]𝐛𝐁\}`$. $`B`$ is obviously a basis of $`Z_1(\mathrm{\Gamma };_2)`$, because $`[𝐞_k]=[𝐞_k+𝐠_k+𝐡_k]+[𝐠_k+𝐞_{k+1}]+[𝐡_k+𝐞_{k+1}]`$. Let $`H`$ denote the subgroup of $`Z_1(\mathrm{\Gamma })`$ (hence of $`E`$) generated by $`𝐁`$, and let $`\chi :EE/H`$ be the quotient map. Now, let us set the gain group to be $`E/H`$ and the gain map $`g`$ to be $`\chi a`$, where $`a`$ is the abelianization mapping from $`F_E`$ to $`E`$. Then the essential gain group $`g(\pi (\mathrm{\Gamma }))=\chi (Z_1(\mathrm{\Gamma }))=Z_1(\mathrm{\Gamma })/H`$. By construction, $`B`$ is a basis of the binary cycle space that consists of balanced circles. If $`HZ_1(\mathrm{\Gamma })`$, then the constructed gain graph is not balanced, because $`Z_1(\mathrm{\Gamma })/H=\chi (𝐞_k),\chi (𝐠_k),\chi (𝐡_k)k1=g(\pi (\mathrm{\Gamma }))`$. But in fact, $`HZ_1(\mathrm{\Gamma })`$, because there is no finite linear combination of elements of $`H`$ that is equal to $`𝐞_1`$.

Denote by $`[\frac{1}{2}]`$ the ring of dyadic rationals, i.e., the ring of rational numbers whose denominators are powers of 2. Its additive group $`[\frac{1}{2}]^+`$ is the unique smallest group that contains an infinitely 2-divisible element of infinite order. One can show that $`Z_1(\mathrm{\Gamma })/H[\frac{1}{2}]^+`$ by mapping $`𝐞_i+Hd_i`$ where $`\{d_i\}_{i=1}^{\mathrm{}}`$ generates $`[\frac{1}{2}]^+`$ and satisfies $`d_i=2d_{i+1}`$. Thus, the essential gain group $`g(\pi (\mathrm{\Gamma }))`$ is 2-divisible.

Notice that a circle $`𝐞_i+𝐠_i+𝐡_i`$ has 5 edges.

###### Conjecture 4.1

Let $`G`$ be a torsion-free abelian group, possibly 2-divisible, and suppose $`Z_1(\mathrm{\Gamma })`$ has a basis that consists of balanced circles with at most $`k`$ edges. Then $`(\mathrm{\Gamma },g,G)`$ is balanced if $`k=3`$, but it need not be balanced if $`k=4`$.

There are also finite counterexamples, but the gain group necessarily has an element of odd order. Two such examples, based respectively on the wheel and on an even circle with all edges doubled, are in Rybnikov & Zaslavsky (20xx), Theorem 6.16 (see Appendix for one of them).

## 5 Algebra of gain graphs and their states

In applications of the kind in Section 6 gain graphs are normally used in the following setup. Let $`(\mathrm{\Gamma },g,G)`$ be a gain graph. Let $`Q`$ be a set, which we call the set of *qualities*, and suppose $`G`$ acts on $`Q`$; for $`qQ`$ and $`hG`$ we denote the result of the action by $`[q]h`$. For instance, it may be that $`Q=G`$ and the action is by right multiplication (the *right regular action*). The combination $`(\mathrm{\Gamma },g,G,Q)`$ is a *permutation gain graph*. (The idea was introduced by Gross & Tucker (1977) under the name “permutation voltage graph”.) A *state* of the graph is an assignment $`s`$ of qualities to the vertices of $`\mathrm{\Gamma }`$. We want to find a state such that for any two adjacent vertices $`v`$ and $`w`$ their qualities $`s(v)`$ and $`s(w)`$ are connected by $`s(w)=[s(v)]g(vw)`$. Such a state is called *satisfied* with respect to $`g`$, or *$`g`$-satisfied*. The set of all $`g`$-satisfied states is denoted by $`\mathrm{Sat}_g(\mathrm{\Gamma },G,Q)`$. The set of all states that are satisfied with respect to at least one element of $`G`$ is denoted by $`\mathrm{Sat}(\mathrm{\Gamma },G,Q)`$. If $`H`$ is a subgroup of $`G^E`$, then $`\mathrm{Sat}_H(\mathrm{\Gamma },G,Q)`$ is the set of all states that are satisfied with respect to some $`gH`$. A $`g`$-satisfied state always exists if $`g`$ is balanced, because in this case one can arbitrarily choose the state of one vertex in each connected component, then assign the states of other vertices according to the rule of satisfaction. The exact rule is that, if $`s(v_0)`$ is the arbitrary state and $`v`$ is a vertex connected to $`v_0`$ by a walk $`W`$, then $`s(v)=[s(v_0)]g(W)`$.

The set $`G^E`$ of all gain maps with values in $`G`$ forms a group under componentwise multiplication, $`gg^{}(e)=g(e)g^{}(e)`$. If $`G`$ is abelian the set $`\mathrm{Bal}(\mathrm{\Gamma },G)`$ of all balanced gain maps is a subgroup of $`G^E`$. If, in addition, $`\mathrm{\Gamma }`$ is connected, then $`|\mathrm{Bal}(\mathrm{\Gamma },G)|=|G|^{|V|1}`$, and $`\mathrm{Bal}(\mathrm{\Gamma },G)G^{|V|1}`$ if $`G`$ is abelian, because one can assign gains arbitrarily to the edges of a spanning tree and then other edge gains are uniquely determined by balance. In general, $`\mathrm{Bal}(\mathrm{\Gamma },G)\cong ̸G^{|V|1}`$ if $`G`$ is nonabelian. From now on *we assume that $`\mathrm{\Gamma }`$ is connected.*

If $`Q`$ is a group, the set $`Q^V`$ of states forms a group under componentwise multiplication, $`ss^{}(v)=s(v)s^{}(v)`$. From now on *we assume that $`Q`$ is a group.* We do not assume, in general, that the action of $`G`$ on $`Q`$ is a group action.

If $`G`$ does act on $`Q`$ in the manner of a *group action* (i.e., through a homomorphism $`G\mathrm{Aut}Q`$), then the set of all $`g`$-satisfied states, $`\mathrm{Sat}_g(\mathrm{\Gamma },G,Q)`$, forms a subgroup of $`Q^V`$. If in addition $`\mathrm{\Gamma }`$ is connected and $`g`$ is balanced, then

$$\mathrm{Sat}_g(\mathrm{\Gamma },G,Q)Q$$

because the choice of $`s(v)`$ at one vertex $`v`$ determines $`s`$.

Another way $`G`$ may act on $`Q`$ is by a *product action*, that is, where

(5.1)
$$[qq^{}](ff^{})=([q]f)([q^{}]f^{}).$$

Affine action of $`^n`$ on itself (by translations) is an example of a product action in geometry. A product action is very restricted.

###### Lemma 5.1

An action of $`G`$ on $`Q`$ is a product action if and only if it has the form $`[q]f=\sigma (q)c(f)`$, where $`\sigma :QQ`$ is an endomorphism of $`Q`$ and $`c:GQ`$ is a homomorphism of $`G`$ into the center of $`Q`$.

Proof. Any action of this form is clearly a product action. For the converse, compare the two sides of (5.1). First, with $`q=q^{}=1`$; this establishes the existence of a homomorphism $`c`$ given by $`c(f)=[1]f`$. Next, with $`q^{}=1`$, and $`f=1`$; this establishes that $`[q]f^{}=([q]1)c(f^{})`$. Taking $`q=1`$ and $`f^{}=1`$ establishes that $`[q]f=c(f)q^{}`$; combining this with the previous conclusion we get $`[q]1c(f)=[q]f=c(f)[q]1`$ for all $`qQ`$. So, $`c(f)`$ is in the center of $`Q`$. Taking $`f=f^{}=1`$ shows that $`\sigma :q[q]1`$ is a homomorphism $`QQ`$.

We call $`(g,s)G^E\times Q^V`$ a *satisfied pair* if $`s`$ is a satisfied state with respect to the gain map $`g`$. With a product action of $`G`$ on $`Q`$, the set of satisfied pairs forms a group $`\mathrm{SatPair}(\mathrm{\Gamma },G,Q)`$ with respect to componentwise multiplication, $`(g,s)(g^{},s^{})=(gg^{},ss^{})`$. If $`HG^E`$, then $`\mathrm{SatPair}_H(\mathrm{\Gamma },G,Q)`$ stands for the set of all satisfied pairs $`(s,g)`$ where $`gH`$. If $`G`$ is abelian and $`H`$ happens to be a subgroup of $`\mathrm{Bal}(\mathrm{\Gamma },G)`$, $`\mathrm{SatPair}_H(\mathrm{\Gamma },G,Q)`$ forms a subgroup of $`\mathrm{SatPair}(\mathrm{\Gamma },G,Q)`$.

We call an action of $`G`$ on $`Q`$ *fixed-point free* if every element of $`G`$, other than the identity, acts without fixed points. If $`\mathrm{\Gamma }`$ is connected and the action of $`G`$ is fixed-point free, then $`\mathrm{Sat}(\mathrm{\Gamma },G,Q)\mathrm{Bal}(\mathrm{\Gamma },G)\times Q`$, because, as shown in the following lemma, a gain mapping $`gG^E`$ and the value $`qQ`$ at one vertex together determine a satisfied state if and only if $`g\mathrm{Bal}(\mathrm{\Gamma },G)`$. Ffrom the definitions we have:

###### Lemma 5.2

Suppose the action of $`G`$ on $`Q`$ is fixed-point free. Then a permutation gain graph $`(\mathrm{\Gamma },g,G,Q)`$ has a satisfied state if and only if $`(\mathrm{\Gamma },g,G)`$ is balanced, and then the state is determined by its value at any one vertex.

Proof. Given $`(\mathrm{\Gamma },g,G,Q)`$, let $`s`$ be a state. Let $`W_v`$ denote a simple closed walk from $`v`$ to $`v`$. Then $`s`$ is satisfied if and only if $`[s(v)]g(W_v)=s(v)`$ for all choices of $`v`$ and $`W_v`$. Under the hypothesis on fixed points, this is true if and only if $`g(W_v)=1`$ for all choices of $`W_v`$, i.e., if and only if $`g`$ is balanced.

On the other hand, if the action if not fixed-point free and $`\mathrm{\Gamma }`$ is not a tree, then one can always define an unbalanced gain map that has a satisfied state. The lemma implies, in particular, that if $`H`$ is a subgroup of $`\mathrm{Bal}(\mathrm{\Gamma },G)`$, then there is a natural bijection between $`\mathrm{Sat}_H(\mathrm{\Gamma },G,Q)`$ and $`H\times Q`$.

Suppose $`G`$ acts on $`Q`$ in the manner of a group action. If $`Q`$ is a module over a ring $``$ and the group action is linear over $``$, then for any gain map $`g`$, $`\mathrm{Sat}_g(\mathrm{\Gamma },G,Q)`$ is also an $``$-module. Furthermore, by Lemma 5.2

(5.2)
$$\mathrm{Sat}_g(\mathrm{\Gamma },G,Q)Q.$$

If $`G`$ is also an $``$-module, then the group of gain mappings, $`G^E`$, is an $``$-module. If, moreover, $`H`$ is a submodule of $`\mathrm{Bal}(\mathrm{\Gamma },G)`$, then the action of $`G`$ on $`Q`$ is indeed a product action, $`\mathrm{SatPair}_H(\mathrm{\Gamma },G,Q)`$ is a subgroup of $`\mathrm{SatPair}(\mathrm{\Gamma },G,Q)`$, and

(5.3)
$$\mathrm{SatPair}_H(\mathrm{\Gamma },G,Q)QH.$$

In particular, $`\mathrm{SatPair}(\mathrm{\Gamma },G,Q)QG^{|V|1}`$.

If the action of module $`G`$ on module $`Q`$ is also fixed-point free, then by Lemma 5.2,

(5.4)
$$\mathrm{Sat}_H(\mathrm{\Gamma },G,Q)\mathrm{SatPair}_H(\mathrm{\Gamma },G,Q)QH.$$

A special case of permutation gain graphs has been studied by Joswig (2002) and Izmestiev & Joswig (2003) in connection with coloring of tilings of manifolds and problems in the geometric topology of covering spaces. Let $`\mathrm{\Gamma }`$ be the dual graph of a finite, pure, $`d`$-dimensional, strongly connected simplicial complex $`\mathrm{\Delta }`$ on $`n`$ vertices, and let $`G`$, the gain group, be $`S_n`$, the symmetric group on the vertices of $`\mathrm{\Delta }`$. The gain mapping $`g`$ takes an edge connecting adjacent $`d`$-simplices whose symmetric difference is a pair $`\{i,j\}`$ to the transposition that exchanges $`i`$ and $`j`$ (Joswig calls this a “perspectivity”). Joswig calls the image $`g(\pi (\mathrm{\Gamma }))`$ of the group of closed edge-walks beginning and ending at a vertex $`v\mathrm{\Gamma }`$ the group of “projectivities” and writes it $`\mathrm{\Pi }(\mathrm{\Delta },v)`$. The main object of Izmestiev and Joswig’s studies is the size and structure of this group for various combinatorial manifolds. See Appendix for more details on projectivities and their applications in combinatorial topology.

## 6 Gain graphs in geometry

Given a tiling of $`^d`$ by convex polyhedra, it is natural to ask whether this tiling can be thought of as the vertical projection of a convex PL-surface or, more generally, any PL-surface. A PL-function on $`^d`$ is known as a *$`C_1^0`$-spline* in approximation theory. The problem of finding the dimension of the space of such splines on a given tiling has received significant attention from discrete geometers and spline enthusiasts (see, e.g., Whiteley (1996) or Billera (1989) for details). Voronoi (1908) showed that any *simple* tiling $`T`$, i.e., such that each vertex is incident to exactly $`d+1`$ tiles, is indeed the projection of a convex surface, which he called a *generatrix* of $`T`$; furthermore, a surface that gives this tiling as a projection is uniquely determined by the choice of an affine support function and a dihedral angle.

A tiling is an example of a more general concept, namely a PL-realization $`M`$ in $`^d`$ of a $`d`$-dimensional manifold $``$. In this section, as an application of the Binary Cycle Test, we ask about possible PL-realizations of $``$ in $`^{d+1}`$ that give $`M`$ as a vertical projection.

If $`M`$ is a PL-realization in $`^d`$ of a cell-complex $``$ (*cell-complex* defined, e.g., in the sense of Seifert & Threlfall (1980); the PL-realization is what is called a *geometric cell-complex*), and $`L`$ is another PL-realization of $``$, but in $`^{d+1}`$, such that for each cell $`C`$ of $``$ its realization in $`M`$ is the vertical projection of its realization in $`L`$, then $`L`$ is called a *lifting* of $`M`$. The notion of lifting naturally generalizes that of $`C_1^0`$-spline. The graph of a $`C_1^0`$-spline is a lifting of the tiling over which it is defined, while a lifting of a PL-realization $`M`$ in $`^d`$ of a $`d`$-manifold $``$ is the graph of a $`C_1^0`$-spline if and only if $`M`$ is an embedding. Obviously, liftings can be added, just like $`C_1^0`$-splines. The space of liftings of $`M`$ is denoted by $`\mathrm{Lift}(M)`$. A trivial kind of lifting is to a hyperplane in $`^{d+1}`$. The opposite kind is a sharp lifting: we call a PL-realization in $`^{d+1}`$ of a $`d`$-complex *sharp* if any two adjacent $`d`$-cells are realized on different affine hyperplanes.

Of course, questions about projections of piecewise-linear surfaces belong to the realm of projective geometry. To make our presentation more visual and accessible we do all our geometry in the real affine space $`^d`$, although at the end of the section we give our result a proper projective interpretation.

Although some of the constructions that we treat below were considered in Rybnikov (1999), the Binary Cycle Test is formulated incorrectly there (in Lemma 4.1). Roughly speaking, that formulation does not have any restriction on gain groups, due to the fact that the author had in mind only abelian groups. However, since the test was applied there for abelian, torsion-free groups only, all the geometric results of Rybnikov (1999) about PL-realizations of (and splines over) a manifold $``$ with $`H_1(;_2)=0`$ hold true if one assumes that the manifold has finitely many cells; this last requirement was also omitted in Rybnikov (1999). (When $``$ is simply connected the finiteness restriction is not necessary, since in this case there is an alternative argument, which uses the fundamental group—see Ryshkov & Rybnikov (1997) for proofs and examples.)

### 6.1 Technical Preparation

We use standard notions of PL-topology. (See, e.g., Munkres (1984) or Seifert & Threlfall (1980).) A *regular CW-complex* $`𝒦`$ is a locally finite CW-complex in which all gluing mappings are homeomorphisms. A regular CW-complex has a barycentric subdivision $`𝒦^{\mathrm{}}`$, which is a simplicial complex. $`𝒦`$ also has a natural dual structure, called the *dual cell-decomposition*; we will denote the dual CW-complex by $`𝒦^{}`$. Note that $`𝒦`$, $`𝒦^{}`$ and $`𝒦^{\mathrm{}}`$ have the same support and are homeomorphic. The face lattices of $`𝒦`$ and $`𝒦^{}`$ are dual. A cell is always assumed to be *relatively open* and the closure of a cell need not be homeomorphic to a ball. A $`k`$-cell $`C^{}`$ of $`𝒦^{}`$ is the union of all simplices of $`𝒦^{\mathrm{}}`$ whose closures share the barycenter of a $`(dk)`$-cell $`C`$ of $`𝒦`$. The boundary of $`C^{}`$ is called the link of $`C`$. The dimension of $`𝒦`$ is the maximum dimension of any cell of $`𝒦`$. *Facets* of $`𝒦`$ are cells of dimension $`dim𝒦1`$, and *ridges* of $`𝒦`$ are cells of dimension $`dim𝒦2`$. Two $`k`$-cells are *adjacent* if their closures share a $`(k1)`$-cell. A pure $`d`$-dimensional CW-complex is *strongly connected* if any two $`d`$-cells can be joined by a sequence of adjacent $`d`$-cells. We use $`\text{C}^k(𝒦,A)`$ and $`\text{C}_k(𝒦,A)`$ to refer to the $``$-spaces of $`k`$-co-chains and $`k`$-chains over a real vector space $`A`$.

A *homology sphere* is defined inductively: a homology 0-sphere is a standard 0-sphere, and a higher-dimensional homology sphere is a strongly connected regular CW-complex such that: (1) all its homology groups are like those of a standard sphere and (2) the boundaries of all cells of the dual cell-decomposition are homology spheres. A homology ball is a cone over a homology sphere. A finite *homology $`d`$-manifold (with boundary)* is a strongly connected regular CW-complex with finitely many cells, in which the link of each $`k`$-cell, for $`0k<d`$, is a homology sphere (or ball, if the cell belongs to the boundary) of dimension $`dk1`$.

Seifert & Threlfall (1980) allow the cells of a homology manifold to be homology balls; then the regular CW-complexes in our definitions should be replaced by regular homology CW-complexes. All of our results hold for this more general interpretation.

If $`𝒦`$ is a regular CW-complex and $`r`$ is a continuous map from the barycentric subdivision $`𝒦^{\mathrm{}}`$ to $`^N`$ such that (1) each abstract simplex is mapped to an affine simplex, and (2) the simplices of $`𝒦^{\mathrm{}}`$ making up a $`k`$-cell of $`𝒦`$ are mapped to the same affine $`k`$-flat of $`^N`$, then $`K=(𝒦,r)`$ is called a *PL-realization* of $`𝒦`$. The realization is called *non-degenerate* if $`r`$, restricted to the closure of each cell of $`𝒦`$, is a homeomorphism.

### 6.2 Local Considerations

An *oriented facet* is an ordered pair of adjacent $`d`$-cells. The minimum possible number of $`d`$-cells that make contact at a $`k`$-cell of a convex tiling of $`^d`$, or of a $`(d+1)`$-polytope, is $`dk+1`$. We call the star of a $`k`$-cell in a manifold *simple* (a.k.a. *primitive* in the theory of parallelohedra) if the cell is incident to only $`dk+1`$ $`d`$-cells. A $`d`$-manifold is called *$`k`$-simple* if the star of each $`k`$-cell is simple. A manifold with boundary is $`k`$-simple if the stars of all its interior $`k`$-cells are simple. Notice that $`k`$-simplicity implies $`m`$-simplicity for $`m>k`$.

The *dual graph* $`\mathrm{\Gamma }()`$ of a homology $`d`$-manifold $``$ (possibly with boundary) is the graph of adjacency of $`d`$-cells. It is the 1-skeleton of the dual cell-decomposition $`^{}`$. The vertices are the $`d`$-cells of $``$ and the edges are the pairs of $`d`$-cells that share a common facet. The edges of $`\mathrm{\Gamma }()`$ can be thought of as the internal facets of $``$. In the dual graph of a $`k`$-simple manifold, the subgraphs corresponding to the stars of $`k`$-cells are complete subgraphs on $`dk+1`$ vertices. Subgraphs of $`\mathrm{\Gamma }()`$ that correspond to the stars of ridges are circles; we call them *ridge circles* and, in the case when the stars of ridges are simple, *ridge triangles*.

A *reciprocal* for a PL-realization $`M`$ in $`^d`$ of a homology manifold $``$ is a rectilinear realization $`R`$ in $`^d`$ of the dual graph $`\mathrm{\Gamma }()`$ such that the edges of $`R`$ are perpendicular to the corresponding facets. If none of the edges of $`R`$ collapse into a point, the reciprocal is called *non-degenerate*; a one-point reciprocal is called *trivial*. A reciprocal for the star of a cell $`C`$ is called a *local reciprocal* of $`C`$. Reciprocals were originally considered by Maxwell (1864) and Cremona (1890) in connection with stresses in plane frameworks. Crapo & Whiteley (1993) gave a modern treatment of the Maxwell–Cremona theory of reciprocals, stresses, and liftings for 2-manifolds. Obviously, reciprocals can be added and multiplied by real scalars. Geometrically, multiplication corresponds to scaling. The addition is induced by vector addition of the vertices. Thus, for a given $`M`$ the reciprocals form a linear space. This space, factored by all translations of $`^d`$, is denoted $`\mathrm{Rec}(M)`$.

A PL-realization of a homology $`d`$-manifold is called *generic* if no pair of adjacent facets lies in the same $`(d1)`$-plane.

###### Lemma 6.1

For each non-degenerate generic PL-realization in $`^d`$ of a simple star of a cell there is a non-degenerate reciprocal. It is unique up to translations, homotheties, and central inversions.

Proof. The existence of a non-degenerate reciprocal for a simple star is a trivial exercise in linear algebra. Such a reciprocal is the 1-skeleton of a simplex whose edges are perpendicular to the corresponding facets. Since directions of edges and the angles between them are uniquely determined by the geometry of the star, the reciprocal is unique up to affine transformations preserving directions and angles.

###### Lemma 6.2

If $`Star`$ is a non-degenerate generic PL-realization of a simple star of a cell, then $`dim\mathrm{Lift}(Star)=d+2`$.

Proof. Any three $`d`$-cells of $`Star`$ form a triangle in the dual graph. Choose two $`d`$-cells in $`Star`$. By fixing two affine functions that lift the union of these $`d`$-cells to $`^{d+1}`$, so that these functions coincide on the common facet of the cells, we fix the lifting for all of $`Star`$. Since a lifting of two adjacent $`d`$-cells is defined by $`d+2`$ parameters (e.g., the coefficients of an affine function in $`d`$ variables and a dihedral angle in $`(d+1)`$-space), $`dim\mathrm{Lift}(Star)=d+2`$.

### 6.3 From Local to Global

In the remainder of the section we show that, subject to the topological restriction that $`H_1(;_2)=0`$ and the combinatorial restriction of $`(d3)`$-simplicity, liftings of $`(d2)`$-simple manifolds behave in the same way as those of simple stars. (Although a tiling of $`^d`$ may not be a CW-complex, all our theorems hold for the case when $`M`$ is a finite tiling.)

The following lemma is a homological version of what some call Poincaré’s $`(d2)`$-face principle (1882) in discrete geometry, which, basically, says that for a group of isometries to tile a Euclidean space, sphere, or hyperbolic space with copies of a $`d`$-polyhedron $`T`$ it is enough that for each $`(d2)`$-face $`F`$ of $`T`$ there are group elements $`g_1,\mathrm{},g_k`$ such that $`T,g_1(T),\mathrm{},g_k(T)`$ fill the space, face-to-face, around $`F`$ without gaps or overlaps. See Dolbilin (2000) for an exact formulation and recent generalization of this principle.

###### Lemma 6.3

Let $``$ be a finite homology $`d`$-manifold with $`d2`$ and with $`H_1(;_2)=0`$. Let $`(\mathrm{\Gamma }(),g,G)`$ be an abelian gain graph whose underlying graph is $`\mathrm{\Gamma }()`$ and whose gain group has no odd torsion. Then the gain graph is balanced if and only if the ridge circles of $`\mathrm{\Gamma }()`$ are balanced.

Proof. The “only if” part follows from the definition of balanced graph.

Consider the dual cell-decomposition $`^{}`$ of $``$. The 2-cells of this decomposition are in one-to-one correspondence with the ridges of $``$. Since $`H_1(;_2)=0`$ and the underlying spaces of $``$ and $`^{}`$ are the same, the boundaries of the 2-cells of $`^{}`$ generate $`Z_1(^{};_2)`$. These boundaries are circles and they are balanced by our assumption. According to the Binary Cycle Test for finite graphs, $`(\mathrm{\Gamma }(),g,G)`$ must be balanced.

For instance, Lemma 6.3 applies to homology spheres of dimension at least 2.

###### Theorem 6.4

Let $``$ be a finite $`(d3)`$-simple homology $`d`$-manifold without boundary, with $`d3`$, and with $`H_1(;_2)=0`$. Let $`M`$ be a non-degenerate generic PL-realization of $``$ in $`^d`$. Then $`M`$ has a non-degenerate reciprocal and $`dim\mathrm{Rec}(M)=1`$.

Proof. The main ingredients of the proof are the dual cell-decomposition $`^{}`$ of $``$, the notion of gain graph, and the Binary Cycle Test for balance.

Let $`\mathrm{\Gamma }=\mathrm{\Gamma }(V,E)`$ be the dual graph of $``$. An oriented facet can be thought of as an oriented edge of $`\mathrm{\Gamma }`$.

From the algebraic standpoint a reciprocal for $`M`$ is a linear operator $`r`$ from the vector space $`(^d)^V`$ of 0-cochains on $`\mathrm{\Gamma }(V,E)`$ with values in $`^d`$, which has the property that $`\delta r(C_i,C_j)`$ is orthogonal to the common facet $`F_{ij}`$ of $`C_i`$ and $`C_j`$, where $`\delta :C^0(\mathrm{\Gamma },^d)C^1(\mathrm{\Gamma },^d)`$ is the coboundary map, defined by $`\delta r(C_i,C_j)=r(C_j)r(C_i)`$ for each oriented facet $`(C_i,C_j)`$. (See Appendix for more detailed description of the above.) Thus, the edges $`\{(r(C_i),r(C_j))\}`$ of a non-degenerate reciprocal have a natural interpretation as the linear parts of the equations defining the facets of $`M`$. These linear parts are often called the *covectors* of the facets of $`M`$. It follows from the definition that

(6.1)
$$\delta r(C_1,C_2)=\delta r(C_2,C_1)$$

and that

(6.2)
$$\delta r(C_1,C_2)+\delta r(C_2,C_3)+\delta r(C_3,C_1)=0$$

whenever $`C_1`$, $`C_2`$, $`C_3`$ share a common ridge. Equation 6.1 means that $`\delta r`$ is a gain map on $`\mathrm{\Gamma }`$ with gain group $`^d`$. The gain graph is balanced because $`\delta r`$ is a coboundary. Because $`\mathrm{\Gamma }`$ is connected, $`r`$ is completely determined by $`\delta r`$ and one point $`r(C)`$; indeed, $`r`$ is any satisfied state of $`(\mathrm{\Gamma },\delta r,^d,^d)`$, where $`^d`$ acts on $`^d`$ by translation (that is, the right regular action). Thus,

(6.3)
$$\mathrm{Rec}(M)=\{\delta r:r\text{ is a reciprocal for }M\},$$

the space of coboundaries of reciprocals.

We associate with each oriented facet $`(C_1,C_2)`$ a unit vector $`𝐧(C_1,C_2)`$, normal to the common facet of $`C_1`$ and $`C_2`$, so that $`𝐧(C_1,C_2)=𝐧(C_2,C_1)`$. Henceforth, these normals are fixed.

Consider the *facet graph* $`\mathrm{\Phi }`$, whose vertices are the (unoriented) facets of $``$ and whose edges are the pairs of facets sharing ridges. Orient the edges of $`\mathrm{\Phi }`$ in an arbitrary way. Take a ridge $`R`$ where $`d`$-cells $`C_1`$, $`C_2`$, $`C_3`$ make contact. Denote by $`F_{ij}`$ the common facet of $`C_i`$ and $`C_j`$. Up to scaling there is only one nontrivial linear combination of $`𝐧(C_1,C_2)`$, $`𝐧(C_2,C_3)`$, $`𝐧(C_3,C_1)`$ equal to zero. Let

$$\alpha _{12}𝐧(C_1,C_2)+\alpha _{23}𝐧(C_2,C_3)+\alpha _{31}𝐧(C_3,C_1)=0$$

be one such combination with nonzero coefficients; it exists because $`M`$ is a non-degenerate PL-realization. For the oriented edge $`F_{12}F_{23}`$ in the facet graph, define

$$g(F_{12}F_{23})=\alpha _{23}/\alpha _{12}.$$

In this way we define the map $`g`$ on all oriented edges of the facet graph. We call $`(\mathrm{\Phi },g,^{})`$ the *facet gain graph*.

###### Lemma 6.5

$`(\mathrm{\Phi },g,^{})`$ is a balanced gain graph.

Proof. Obviously, $`g(F_{12}F_{23})`$ depends only on the geometric realization $`M`$ of $``$ and on the (fixed) choice of normals $`𝐧(A,B)`$ for oriented facets. It is clear that $`g(F_{12}F_{23})=g(F_{23}F_{12})^1`$ and

(6.4)
$$g(F_{12}F_{23})g(F_{23}F_{31})g(F_{31}F_{12})=1;$$

that is, $`g`$ is a gain map on $`\mathrm{\Phi }`$ and each triangle corresponding to a ridge (a *ridge triangle of $`\mathrm{\Phi }`$*) is balanced. Furthermore,

(6.5)
$$𝐧(C_1,C_2)+g(F_{12}F_{23})𝐧(C_2,C_3)+g(F_{23}F_{31})g(F_{12}F_{23})𝐧(C_3,C_1)=0.$$

The dual cell-decomposition $`^{}`$ of $``$ can be refined in a useful way. Each 2-cell of $`^{}`$ is a triangle. Let $`^{}`$ be the cell-complex obtained from $`^{}`$ by subdividing each edge in the middle and then joining the *new vertices* by three *new edges* within each 2-cell, thereby partitioning the 2-cell into four triangles.

Since $`^{}`$ and $`^{}`$ are identical to $``$ as topological spaces,

$$H_1(^{};_2)=H_1(^{};_2)=H_1(;_2)=0.$$

Moreover, $`\mathrm{\Phi }`$ is a subgraph of $`\mathrm{Sk}_1(^{})`$. Consequently, for any $`cZ_1(\mathrm{\Phi };_2)`$ there is a 2-chain $`\mathrm{\Delta }C_2(^{};_2)`$ such that $`c=\mathrm{\Delta }`$. The chain $`\mathrm{\Delta }`$ can be decomposed as $`\mathrm{\Delta }_1+\mathrm{\Delta }_2`$, the sum of $`\mathrm{\Delta }_1=\mathrm{\Delta }_{1j}`$, where each $`\mathrm{\Delta }_{1j}`$ is a triangle whose vertices are new vertices corresponding to facets of $``$ making contact at a ridge, and $`\mathrm{\Delta }_2=\mathrm{\Delta }_{2i}`$, where each $`\mathrm{\Delta }_{2i}`$ has one vertex in $`\mathrm{Sk}_0(^{})`$, corresponding to a cell of $``$, and two vertices that are new vertices corresponding to facets of that cell. For each $`d`$-cell $`C`$ of $``$, let $`\mathrm{\Delta }_{2C}`$ be the sum of all the $`\mathrm{\Delta }_{2i}`$ having as one vertex that vertex of $`^{}`$ that corresponds to $`C`$. Then $`c=\mathrm{\Delta }_{1j}+\mathrm{\Delta }_{2C}`$ where each term in the first sum is a ridge triangle of $`\mathrm{\Phi }`$ and each term in the second sum is a cycle on the boundary of a $`d`$-cell of $``$.

This shows that ridge triangles and cycles lying on the boundaries of $`d`$-cells generate $`Z_1(\mathrm{\Phi };_2)`$. We prove next that $`(\mathrm{\Phi },g,^{})`$ is balanced. Since $``$ is $`(d3)`$-simple, the boundary of each $`d`$-cell $`C`$ is $`((d1)2)`$-simple. $`\mathrm{\Phi }_C`$, the subgraph of $`\mathrm{\Phi }`$ on the vertices that belong to $`C`$, is the dual graph $`\mathrm{\Gamma }(C)`$ of the boundary cell-complex of $`C`$. The corresponding gain subgraph is $`(\mathrm{\Phi }_C,g,^{})`$. By Equation (6.4) the ridge circles of $`\mathrm{\Phi }_C`$ are balanced. Since $`dimC2`$, Lemma 6.3 applied to $`C`$ implies that $`(\mathrm{\Phi }_C,g,^{})`$ is balanced and, therefore, all cyclic orientations of binary cycles of $`\mathrm{\Phi }_C`$ have gain 1. We have seen that binary cycles of these two types generate $`Z_1(\mathrm{\Phi };_2)`$. By the Binary Cycle Test for finite graphs, $`(\mathrm{\Phi },g,^{})`$ is balanced.

Suppose the set of qualities $`Q`$ is $``$ and $`^{}`$ acts on $``$ by multiplication. The action of $`^{}`$ on $`0`$ is fixed-point free and therefore, by Lemma 5.2 and the obvious properties of the all-zero state, $`\mathrm{Sat}_g(\mathrm{\Phi },^{},)`$. We are now going to explain why $`\mathrm{Sat}_g(\mathrm{\Gamma },^{},)`$ can be regarded as a 1-dimensional subspace of $`(^d)^E`$, where $`E`$ is the set of edges of $`\mathrm{\Gamma }`$.

Fix a non-zero satisfied state $`s`$ of $`(\mathrm{\Phi },g,^{},)`$. We denote by $`s(C_i,C_j)`$ the value of $`s`$ on a vertex of $`\mathrm{\Phi }`$ corresponding to a facet between $`d`$-cells $`C_i`$ and $`C_j`$. We will construct yet another gain graph, $`(\mathrm{\Gamma },h_s,^d)`$, this time with the gain group $`^d`$. Assign to each oriented edge $`C_1C_2`$ of $`\mathrm{\Gamma }`$ the vector $`h_s(C_1C_2)=s(C_1,C_2)𝐧(C_1,C_2)`$.

###### Lemma 6.6

$`(\mathrm{\Gamma },h_s,^d)`$ is a balanced gain graph.

Proof. Since $`𝐧(C_1,C_2)=𝐧(C_1,C_2)`$ and $`s(C_1,C_2)=s(C_2,C_1)`$, $`h_s(C_2C_1)=h(C_1C_2)`$. Since $`H_1(^{};_2)=H_1(;_2)=0`$, by Lemma 6.3 balance of the ridge triangles of $`\mathrm{\Gamma }`$ implies balance of the gain graph. To conclude that these triangles are balanced we have to show that

$$s(C_1,C_2)𝐧(C_1,C_2)+s(C_2,C_3)𝐧(C_2,C_3)+s(C_3,C_1)𝐧(C_3,C_1)=0.$$

Let us divide this equation by $`s(C_1,C_2)`$ and recall that (with indices taken modulo 3) $`s(C_{i+1},C_{i+2})/s(C_i,C_{i+1})=g(F_{i,i+1}F_{i+1,i+2})`$ for the star of each ridge. So, we need

$$𝐧(C_1,C_2)+g(F_{12}F_{23})𝐧(C_2,C_3)+g(F_{12}F_{31})𝐧(C_3,C_1)=0.$$

This is equivalent to Equation (6.5). Thus each ridge triangle is balanced, and $`(\mathrm{\Gamma },h_s,^d)`$ is balanced by the Binary Cycle Test.

We want to prove that the elements of $`\mathrm{Sat}_g(\mathrm{\Phi },^{},)`$ correspond to the reciprocals (modulo $`^d`$) in one-to-one fashion; hence $`dim\mathrm{Rec}M=1`$. Our strategy is to show that $`\mathrm{Sat}_g(\mathrm{\Phi },^{},)\mathrm{Rec}(M)`$ as real vector spaces by producing a specific isomorphism $`\rho `$. We define $`\rho (s)=h_s`$. It is obvious that $`\rho `$ is an injection and a vector-space homomorphism. Let $`H`$ be the image of $`\rho `$. Then $`H\mathrm{Bal}(\mathrm{\Gamma },^d)`$ and $`dimH=1`$.

Consider now the permutation gain graph $`(\mathrm{\Gamma },h_s,^d,^d)`$, where the first three components are as above and $`^d`$ acts on $`^d`$ by translation. This action is obviously fixed-point free. Since a reciprocal is completely defined by the coordinates of its vertices, all reciprocals form a linear subspace of $`(^d)^V`$. A satisfied state for $`(\mathrm{\Gamma },h_s,^d,^d)`$ is a reciprocal $`r`$ whose edge lengths have been decided by the gain graph $`(\mathrm{\Gamma },h_s,^d)`$. That is, since $`(\mathrm{\Gamma },h_s,^d)`$ is balanced and connected, we can start from any point in $`^d`$ as a vertex of the reciprocal and construct all other vertices. Then $`h=\delta r`$. By Lemma 5.2 this construction gives all of $`\mathrm{Sat}_{h_s}(\mathrm{\Gamma },^d,^d)`$; varying $`s`$, it gives all of $`\mathrm{Sat}_H(\mathrm{\Gamma },^d,^d)`$. Furthermore, it shows that $`H\{\delta r|r\text{ is a reciprocal}\}`$, the reciprocal coboundary space, which is $`\mathrm{Rec}M`$ by Equation 6.3. The non-zero elements of $`H`$ correspond (bijectively) to the non-degenerate reciprocals.

Conversely, the edges of a reciprocal $`r`$ determine a balanced gain map $`\delta r`$ with values in the gain group $`^d`$. By the orthogonality property of a reciprocal and Equation (6.2), $`\delta r`$ has the form $`\rho (s)`$ for some non-zero $`s(\mathrm{\Phi },g,^{},)`$. Therefore, $`H=\{\delta r|r\text{ is a reciprocal}\}=\mathrm{Rec}(M)`$.

We established earlier that $`dim_{}H=1`$. It follows that $`dim_{}\mathrm{Rec}(M)=1`$.

###### Theorem 6.7

Let $``$ and $`M`$ be as in Theorem 6.4. Then $`M`$ has a sharp lifting and $`dim_{}\mathrm{Lift}(M)`$ is $`d+2`$.

Proof. Since $``$ is $`(d2)`$-simple, in any lifting of $`M`$ the position of a $`d`$-cell $`C`$ from the star $`\mathrm{Star}(R)`$ of a ridge $`R`$ is completely defined by the positions of the other two $`d`$-cells of $`\mathrm{Star}(R)`$. Therefore, if the lifting of $`\mathrm{Star}(R)`$ can be extended to a lifting of $`M`$, the resulting lifting of $`M`$ is completely defined by the lifting of $`\mathrm{Star}(R)`$. By Lemma 6.2, $`dim\mathrm{Lift}(M)d+2`$.

Let us now prove that $`dim\mathrm{Lift}(M)=d+2`$. Let $`H`$ be as in the above theorem, i.e., let $`H`$ be the subspace of $`\mathrm{Bal}(\mathrm{\Gamma },^d,^d)`$ that consists of those realizations of the dual graph $`\mathrm{\Gamma }`$ of $``$ that are reciprocals of $`M`$. Consider gain graphs where the underlying graph is the dual graph $`\mathrm{\Gamma }`$ and the gain group is the additive group $`A_d`$ of all affine functions on $`^d`$ (this is isomorphic to $`^{d+1}`$). $`A_d`$ acts on itself by addition and this action is fixed-point free. Therefore, by Lemma 5.2, the liftings of $`M`$ can be identified with all satisfied states of permutation gain graphs $`(\mathrm{\Gamma },h_1,^{d+1},A_d)`$ where $`h_1`$ is taken from the subgroup $`H_1`$ of $`\mathrm{Bal}(\mathrm{\Gamma },^{d+1})`$ that consists of gain maps of the form $`h_1(F)=𝐞_F(𝐱𝐜_F)`$, where $`F`$ is an oriented facet, $`𝐞_F`$ is the corresponding oriented edge in some reciprocal, $`𝐜_F`$ is any point on $`F`$, and $`𝐱`$ is the variable vector. This gain map can be written as $`h_1(F)=h(F)+c(F)`$, where $`h(F)=𝐞_F𝐱`$ is a gain map in $`H\mathrm{Bal}(\mathrm{\Gamma },^d)`$. We know that $`H`$. Therefore, a state $`s`$ of $`(\mathrm{\Gamma },h_1,^{d+1},A_d)`$ corresponds to a lifting if and only if the gain map $`c(F)=𝐞_F𝐱`$ is balanced. It is easy to see that all cycles of $`\mathrm{\Gamma }`$ corresponding to ridges of $``$ are balanced with respect to this gain map. These cycles generate all of $`H_1(^{};_2)=H_1(;_2)`$. Therefore, by the Binary Cycle Test $`c`$ is balanced. Thus, by Lemma 5.4, $`\mathrm{Lift}(M)A_d^{d+2}`$.

###### Corollary 6.8

Let $``$ be a finite simple homology $`d`$-manifold, where $`d3`$, such that $`H_1(,_2)=0`$. Let $`M`$ be a non-degenerate generic PL-realization in $`^d`$ whose $`d`$-cells are convex. Then $`M`$ is a projection of a convex polyhedron in $`^{d+1}`$.

Proof. Since $``$ is $`(d3)`$-simple, there is a sharp lifting $`L`$ of $`M`$ to $`^{d+1}`$. Since all cells of $``$ are homeomorphic to convex polytopes, and there are $`dk+1`$ $`d`$-cells making contact at each $`k`$-face, $``$ is a topological manifold. The sharp lifting $`L`$ is then a simple PL-surface in $`^{d+1}`$, realizing abstract manifold $``$. $`L`$ must be an immersion, since each cell is embedded and the star of each vertex is embedded. So, we have a realization of a $`d`$-manifold in $`^{d+1}`$ which has the following properties: (1) it is an immersion, (2) it is locally (non-strictly) convex at each point, and (3) it is strictly convex at each vertex. By Van Heijenoort’s (1952) theorem $`L`$ is the boundary of a convex body. Since $``$ is finite and $`L`$ is piecewise-linear, $`L`$ is a convex polyhedron.

Although Theorem 6.7 is formulated for vertical projections, it, indeed, holds for a central projection from $`^{d+1}`$ to $`^d^{d+1}`$. It also holds for a central projection from the origin of $`d`$-manifolds realized in $`^{d+1}`$ to a $`d`$-sphere in $`^{d+1}`$ (see Rybnikov, 1999), or projection from $`(0,\mathrm{},0,1)`$ of $`d`$-manifolds realized in $`^{d+1}`$ to the Minkowski hyperboloid in $`^{d+1}`$. Of course, the reason for such universality is that the theorem is a theorem of projective geometry. The projective formulation is Theorem 6.9. There, orthogonality between the edges of the reciprocal and facets of $`M`$ is replaced by duality between lines and subspaces of codimension 1 in $`^d`$. Other terminology is essentially as in the affine version.

###### Theorem 6.9

Let $``$ be a finite $`(d3)`$-simple homology $`d`$-manifold with $`H_1(,_2)=0`$. Let $`M`$ be a non-degenerate generic piecewise-linear realization in $`^d`$. Then $`M`$ has a sharp piecewise-linear realization $`L`$ in $`^{d+1}`$ that is projectively equivalent to $`M`$. Such a realization is uniquely determined by choosing $`d+2`$ free real parameters.

###### Proposition 6.10

In fact, as follows from recent work of Rybnikov (2003a,b), even if in the above corollary $``$ is only $`(d3)`$-simple, it is still the projection of a convex polytope. This is a consequence of the fact that convexity at $`(d3)`$-faces (plus other van Heijenoort (1952) conditions ) is sufficient to establish global convexity.

## 7 Appendix

### 7.1 Counterexamples

###### Example 7.1

The graph is shown in Figure 1. We use the following notation for elements of $`Z_1(\mathrm{\Gamma })`$:

$$𝐞_k=D_kL_kD_{k+1}U_kD_k,𝐠_k=L_kL_{k+1}D_{k+1}L_k,𝐡_k=U_kD_{k+1}U_{k+1}U_k.$$

Then $`\{𝐞_k,𝐠_k,𝐡_k\}_{k1}`$ is an integral circle basis of $`\mathrm{\Gamma }`$. As usual, we denote an element of $`Z_1(\mathrm{\Gamma };_2)`$ corresponding to $`𝐱Z_1(\mathrm{\Gamma })`$ by $`[𝐱]`$. Let

$$𝐁=\{𝐞_k+𝐠_k+𝐡_k\}_{k1}\{𝐠_k+𝐞_{k+1}\}_{k1}\{𝐡_k+𝐞_{k+1}\}_{k1}$$

and let $`B=\{[𝐛]𝐛𝐁\}`$. $`B`$ is obviously a basis of $`Z_1(\mathrm{\Gamma };_2)`$, because $`[𝐞_k]=[𝐞_k+𝐠_k+𝐡_k]+[𝐠_k+𝐞_{k+1}]+[𝐡_k+𝐞_{k+1}]`$. Let $`H`$ denote the subgroup of $`Z_1(\mathrm{\Gamma })`$ (hence of $`E`$) generated by $`𝐁`$, and let $`\chi :EE/H`$ be the quotient map. Now, let us set the gain group to be $`E/H`$ and the gain map $`g`$ to be $`\chi a`$, where $`a`$ is the abelianization mapping from $`F_E`$ to $`E`$. Then the essential gain group $`g(\pi (\mathrm{\Gamma }))=\chi (Z_1(\mathrm{\Gamma }))=Z_1(\mathrm{\Gamma })/H`$. By construction, $`B`$ is a basis of the binary cycle space that consists of balanced circles. If we show that $`HZ_1(\mathrm{\Gamma })`$, then the constructed gain graph is not balanced, because $`Z_1(\mathrm{\Gamma })/H=\chi (𝐞_k),\chi (𝐠_k),\chi (𝐡_k)k1=g(\pi (\mathrm{\Gamma }))`$.

###### Lemma 7.1

In the above construction, $`HZ_1(\mathrm{\Gamma })`$.

Proof. The proof is based on the observation that there is no finite linear combination of elements of $`H`$ that is equal to $`𝐞_1`$. Suppose there is such a combination. Then the coefficient in front of $`𝐞_1+𝐠_1+𝐡_1`$ is 1. This, in turn, implies that the coefficients in front of $`𝐞_2+𝐡_1`$ and $`𝐞_2+𝐠_1`$ are $`1`$. Suppose we have shown that the coefficient in front of $`𝐞_i+𝐠_i+𝐡_i`$ must be $`(2)^{i1}`$. Then, obviously, the coefficients in front of $`𝐞_{i+1}+𝐡_i`$ and $`𝐞_{i+1}+𝐠_i`$ are $`(2)^{i1}`$. Therefore, the coefficient in front of $`𝐞_{i+1}+𝐠_{i+2}+𝐡_{i+2}`$ is $`(2)^i`$. Thus, there is no finite linear combination of elements of $`H`$ that gives $`𝐞_1`$.

We want to prove that the essential gain group $`g(\pi (\mathrm{\Gamma }))`$ is 2-divisible. Denote by $`[\frac{1}{2}]`$ the ring of dyadic rationals, i.e., the ring of rational numbers whose denominators are powers of 2. Its additive group $`[\frac{1}{2}]^+`$ is the unique smallest group that contains an infinitely 2-divisible element of infinite order.

###### Lemma 7.2

$`Z_1(\mathrm{\Gamma })/H`$ is isomorphic to $`[\frac{1}{2}]^+`$.

Proof. It is well known that $`[\frac{1}{2}]^+`$ can be written as $`d_1,d_2,\mathrm{}|d_1=2d_2,d_2=2d_3,\mathrm{}=A/D`$, where $`A`$ is the free abelian group with generators $`d_1,d_2,\mathrm{}`$ and $`D`$ is its subgroup generated by $`d_i2d_{i+1}`$. Let $`\phi `$ be the map from $`Z_1(\mathrm{\Gamma })/H`$ to $`A/D`$ defined by $`\phi (𝐞_i+H)=d_i+D`$, $`\phi (𝐠_i+H)=d_{i+1}+D`$, and $`\phi (𝐡_i+H)=d_{i+1}+D`$ for $`i1`$. It is easy to see that $`\phi `$ is an isomorphism.

Notice that a circle $`𝐞_i+𝐠_i+𝐡_i`$ has 5 edges. We do not know if one can construct an example of an unbalanced infinite abelian gain graph with a torsion-free gain group, where there is a basis of the binary cycle space that consists of balanced circles with at most 4 edges. We suspect that such an example exists. However, we have the following conjecture.

###### Conjecture 7.3

Let $`G`$ be a torsion-free abelian group, possibly 2-divisible, and suppose $`Z_1(\mathrm{\Gamma })`$ has a basis that consists of balanced circles with at most 3 edges. Then $`(\mathrm{\Gamma },g,G)`$ is balanced!

There are also finite counterexamples, but the gain group necessarily has an element of odd order.

###### Example 7.2

From Rybnikov and Zaslavsky (20xx), Theorem 6.16, we take the example of the wheel $`W_{2k}`$ with gain group $`_{2k1}`$ (Figure 3). The binary cycle basis consists of the $`2k`$ Hamiltonian circles. Switch so the spokes of the wheel have identity gain; then balance of the Hamiltonian circles implies that any $`2k1`$ consecutive edges along the outer circle have gain product 1. From this it follows that they all have the same gain $`a`$ and $`a^{2k1}=1`$. These gains with gain group $`_{2k1}`$ give an unbalanced gain graph that has a binary cycle basis composed of balanced circles.

Another example from Rybnikov and Zaslavsky (20xx), Theorem 6.16, is $`2C_{2k}`$, an even circle with all edges doubled, with the same gain group.

### 7.2 Joswig’s Projectivities and Combinatorial Topology of Manifolds

A special case of permutation gain graphs has been studied by Joswig (2002) and Izmestiev & Joswig (2003) in connection with coloring of tilings of manifolds and problems in geometric topology of covering spaces. Joswig considered gain graphs whose underlying graphs appear as dual graphs of simplicial PL-manifolds. In this case, the underlying graph $`\mathrm{\Gamma }`$ is the dual graph of some finite, pure, $`d`$-dimensional, strongly connected simplicial complex $`\mathrm{\Delta }`$ on $`n`$ vertices, and the gain group is $`S_n`$, the symmetric group on the vertices of $`\mathrm{\Delta }`$. The gain map $`g`$ is determined by the triangulation of $`\mathrm{\Delta }`$ as follows: an edge $`\sigma \tau `$ of $`\mathrm{\Gamma }`$, where $`\sigma `$ and $`\tau `$ are adjacent $`d`$-simplices of $`\mathrm{\Delta }`$, is mapped to the transposition that permutes two vertices of $`\sigma \tau `$ that do not belong to their common facet. Thus, $`g(\pi (\mathrm{\Gamma }))`$ is a subgroup of $`S_n`$, generated by a subset of transpositions on $`\{1,\mathrm{},n\}`$ that correspond to adjacent $`d`$-simplices (such transpositions are called “perspectivities” by Joswig). Let us fix a vertex $`v`$ of $`\mathrm{\Gamma }`$ (i.e. a $`d`$-simplex $`v=\{1,\mathrm{},d+1\}`$ of $`\mathrm{\Delta }`$) and consider the group of all closed paths on $`\mathrm{\Gamma }`$ which start and end at $`v`$; this group can be identified with $`\pi (\mathrm{\Gamma })`$. Then $`g(\pi (\mathrm{\Gamma }))`$ is the subgroup of all permutations that can be written as products of transpositions along closed paths starting at $`v`$. Such products of transpositions are called “projectivities” by Joswig (2002) and their group is denoted by $`\mathrm{\Pi }(\mathrm{\Delta },v)`$ and referred to as the group of projectivities. (Thus, Joswig’s $`\mathrm{\Pi }(\mathrm{\Delta },v)`$ is the same as $`g(\pi (\mathrm{\Gamma }))`$ in our notation.) If $`[v,v_1,\mathrm{},v_n,v]`$ is a closed path in the dual graph starting from simplex $`v`$, then it is clear that $`g([v,v_1,\mathrm{},v_n,v_o])`$, restricted to the vertices of $`v`$, is a permutation on $`\{1,\mathrm{},d+1\}`$. Therefore, $`g(\pi (\mathrm{\Gamma }))`$ is a subgroup of the set-stabilizer (also called isotropy subgroup) of $`1,\mathrm{},d+1`$. The main object of Joswig’s (2002) and Izmestiev & Joswig’s (2003) studies is the size and structure of this subgroup for various combinatorial manifolds. This group was implicitly considered earlier, in the special case where $`\mathrm{\Delta }`$ is a 3-sphere, by Goodman and Onishi (1978).

### 7.3 Remarks on Proof of Theorem 6.4

Let us denote by $`\text{C}^k(\mathrm{\Gamma },^d)`$ the $``$-space of $`k`$-co-chains with values in $`^d`$ of graph $`\mathrm{\Gamma }`$. From the algebraic standpoint a reciprocal for $`M`$ is a linear operator $`r`$ from the $``$-space of 0-cochains on $`\mathrm{\Gamma }(V,E)`$ with values in $`^d`$, with the property that $`\delta r(C_i,C_j)`$ is orthogonal to the oriented facet $`(C_i,C_j)`$, where $`\delta `$ is the coboundary map from $`\text{C}^0(\mathrm{\Gamma },^d)`$ to $`\text{C}^1(\mathrm{\Gamma },^d)`$, defined by $`\delta r(C_i,C_j)=r(C_j)r(C_i)`$ for each oriented facet $`(C_i,C_j)`$ (i.e. an oriented edge of $`\mathrm{\Gamma }`$).