Universal and Topological Gains for Biased Graphs Preliminary Version. To Be Expanded.

by

Thomas Zaslavsky State University of New York University Center at Binghamton Binghamton, New York 13901 U.S.A.

October, 1986 Revised January, 1989

Abstract

A gain graph is a graph Γ together with a gain function, which assigns to each edge a value from a group so that reversing the orientation of an edge inverts its gain. Γ and the class of circles (edge sets of simple closed walks) whose edge gain product equals 1 (called balanced circles) constitute a gain-biased graph. We show that a gain-biased graph has a canonical gain function, of which any gain function is a homomorphic image; that every gain-biased graph can be embedded in a topological space so that the contractible circles are exactly the balanced ones; and related results.

Research partially supported by National Science Foundation grants DMS-8606102 and DMS-8808239.

Introduction

Suppose we assign to each edge of a graph Γ a gain, a value φ(e) belonging to a group 𝔊, with the rule that when e is taken in the opposite direction, its gain is inverted; that is, φ(e^{−1}) = φ(e)^{−1} . We call Φ = (Γ, φ, 𝔊) a gain graph, Γ the underlying graph, 𝔊 the gain group, and φ the gain function. Let B(Φ) be the class of circles (edge sets of simple closed walks) in which the product of the edge gains taken in cyclic order is the identity. (Such a circle is called balanced.) Then (Γ, B(Φ)) is a biased graph, meaning that if two of the circles in a theta subgraph of Γ are balanced, so is the third. A biased graph so derived from a gain graph Φ is called gain-biased; we denote it by [Φ].

In this article we show two things about gain-biased graphs. First, every gain-biased graph has a ‘universal’ gain function, whose gain group is the free group on the edge set of Γ modulo the relations C = 1 for C ∈ B(Φ). (We regard C as a word by taking its edges in cyclic order.) A topologically biased graph is a biased graph (Γ, B) such that Γ can be embedded in a topological space so a circle is contractible if and only if it is in B. Evidently a topologically biased graph is a kind of gain-biased graph. Our second main result is the converse: every gain-biased graph is topological. (Indeed every gain graph is topological, but that construction is more complicated.) We also develop results, related to the two main theorems, about graphs with arbitrarily distinguished circles.

Acknowledgement. I thank Craig Squier for a suggestion concerning universality.

1. Preliminaries.

We always denote by Γ a graph (N, E), whose node set is N and edge set is E.^{1} We do not assume finiteness. The class of circles of Γ is ℭ = C(Γ). A forest is a set of edges containing no circle. We denote by Φ a gain graph (Γ, φ, 𝔊), by Ψ a gain graph (Γ, ψ, ℌ), and by Ω a pair (Γ, B) where B ⊆ C is a class of distinguished circles. In general Ω need not be a biased graph. A gain graph is called abelian if its gain group is abelian.

1Every edge is a link or a loop.

By 𝔊 and ℌ we denote groups. If R ⊆ 𝔊, ⟨R⟩ is the subgroup generated by R. The free group generated by E is 𝔉(E); the free abelian group generated by E is 𝔄(E). The notation 𝔊/R means the quotient group of 𝔊 by the normal subgroup generated by R, where R ⊆ 𝔊. A circle in Γ, which strictly speaking is a set of edges, we also regard as a word in 𝔉(E) in the obvious way; this word is unique up to conjugation and inversion.

Switching Φ means replacing φ by a function φ^{λ}, where λ : N → 𝔊 is arbitrary, defined by φ^{λ}(e) = λ(v)^{−1}φ(e)λ(w), where v and w are the endpoints of e (possibly the same node) and e is oriented from v to w. We say φ and φ^{λ}, or Φ and Φ^{λ} = (Γ, φ^{λ}, 𝔊), are switching equivalent, written φ ∼ φ^{λ} or Φ ∼ Φ^{λ}; the equivalence classes of this relation are called switching classes. Conjugating Φ means switching by a constant function λ.

Gain graphs Φ_{1} and Φ_{2} are isomorphic if there exist isomorphisms γ : Γ_{1} → Γ_{2} and g : 𝔊_{1} → 𝔊_{2} such that φ_{2} = g∘φ_{1}∘γ^{−1} . They are switching isomorphic if φ_{2} ∼ g∘φ_{1}∘γ^{−1} .

A gain graph Φ is proper if 𝔊 = ⟨Im φ⟩. It is strongly proper if every gain graph in its switching class is proper. To determine whether or not Φ is strongly proper, it is sufficient to examine one gain graph in its switching class, as we now show.

Proposition 1.1. A gain graph is strongly proper if and only if it switches to a proper gain graph whose gains are identically 1 on some maximal forest of the underlying graph.

Proof. Suppose Φ has the property that φ|_{F} ≡ 1 where F is some maximal forest. We show that every switching Φ^{λ} is proper; this establishes the result.

First suppose λ = constant. Then φ^{λ}(e) = λ^{−1}φ(e)λ so ⟨Im φ^{λ}⟩ = λ^{−1}𝔊λ = 𝔊.

Now let λ be arbitrary. We may suppose Γ is connected. Root it at r and let P_{v} be the unique path in F from r to v, for each v ∈ N. By conjugating we may take λ(r) = 1. Then φ^{λ}(P_{v}) = λ(v) and, for an edge e ∉ F oriented (say) from v to w, we have φ^{λ}(e) = φ^{λ}(P_{v})^{−1}φ(e)φ^{λ}(P_{w}). It follows that Im φ^{λ}|_{F} generates Im λ and consequently Im φ^{λ} generates Im φ. So Φ^{λ} is proper. ■

2. Universal and canonical gains.

A biased graph that arises from gains has a canonical gain function with a kind of universality. Moreover, given any graph and class of distinguished circles in it, there is a canonical gain function that yields a minimally balanced gain-biased graph in which the given class is balanced.

Given Ω, let 𝔊_{Ω} = 𝔉(E)/B, let φ_{Ω} be the natural mapping of E into 𝔊_{Ω} , and let Φ(Ω) be the gain graph (Γ, φ_{Ω}, 𝔊_{Ω}). We call Φ(Ω) the canonical gain graph associated with Ω.

We call a gain graph Φ quasi-universal for Ω if, whenever Ψ is a gain graph such that B(Ψ) ⊇ B, then ψ = h ∘ φ for some homomorphism h : 𝔊 → ℌ. If Φ is also proper it is a universal gain graph for Ω. Let us partially order all pairs (Γ, B), for fixed Γ, by the containment ordering of their classes B. Since B(Ψ) ⊇ B(Φ), [Φ] is the unique minimal gain-biased graph containing Ω. Notice that the homomorphism h is unique if Φ is universal, since Im φ generates 𝔊 and h(φ(e)) is thereby determined to be ψ(e).

Theorem 2.1. Let Ω = (Γ, B), where Γ is a graph and B ⊆ C(Γ). Then Φ(Ω) is a universal gain graph for Ω and every universal gain graph for Ω is isomorphic to Φ(Ω). If Ω is gain-biased, then [Φ(Ω)] = Ω.

Proof. Obviously, Φ(Ω) is proper. By definition B(Φ(Ω)) contains B. Let Ψ be a gain graph for which B(Ψ) ⊇ B. The gain function ψ : E → ℌ extends to a homomorphism ψ̄ : 𝔉(E) → ℌ and we have C ∩Ker ψ̄ = B(Ψ) ⊇ B. Therefore ψ̄ induces a homomorphism h : 𝔊_{Ω} → ℌ such that ψ = h ∘ φ_{Ω} . We conclude that Φ(Ω) is a universal gain graph for Ω.

Suppose Φ is also universal for Ω. Then there are homomorphisms g : 𝔊 → 𝔊_{Ω} and h : 𝔊_{Ω} → 𝔊 such that φ = h ∘ φ_{Ω} and φ_{Ω} = g ∘ φ. Therefore φ = h ∘ g ∘ φ and φ_{Ω} = g ∘h∘φ_{Ω} . Since Φ and Φ(Ω) are proper, h∘g and g ∘h are both identity functions. It follows that g and h are inverse isomorphisms under which Φ ≅ Φ(Ω).

It is clear that B(Φ(Ω)) = B if Ω is gain-biased. ■

Supposing Φ in the preceding proof is only quasi-universal for Ω, then g ∘ h is the identity on 𝔊_{Ω} . It follows that h is a monomorphism and 𝔊 is the semidirect product of Ker g with Im h. Conversely, if a group 𝔊 is the semidirect product of 𝔊_{0} and 𝔊_{Ω} , and Φ = (Γ, φ, 𝔊) is defined by φ = i∘φ_{Ω} where i : 𝔊_{Ω} → 𝔊 is the embedding monomorphism, then Φ is clearly quasi-universal for Ω. This shows that the quasi-universal gain graphs for Ω are precisely the isomorphs of those gain graphs obtained from Φ(Ω) by enlarging the gain group through the above semidirect product construction.

Because switching classes rather than individual gain graphs are more crucial to balance theory, we may wish to relax the definition of universality. (This will also enable us to shrink the universal gain group.) We call Φ switching quasi-universal for Ω if, whenever Ψ is a gain graph such that B(Ψ) ⊇ B, then ψ ∼ h ∘ φ for some homomorphism h : 𝔊 → ℌ, and switching universal for Ω if it is also strongly proper. One switching quasi-universal gain graph is Φ(Ω).

Given Ω, let F be a forest in Γ. Let 𝔊_{Ω,F} = 𝔉(E)/(B ∪ F) (that is, 𝔊_{Ω} modulo the relations f = 1 for all f ∈ F), let φ_{Ω,F} be the natural mapping of E into 𝔊_{Ω,F} , and let Φ_{F} (Ω) = (Γ, φ_{Ω,F} , 𝔊_{Ω,F}). It is clear that [Φ_{F} (Ω)] = [Φ(Ω)]. In effect, Φ_{F} (Ω) is the quotient of Φ(Ω) by the forest F.

Theorem 2.2. Let Ω = (Γ, B), where Γ is a graph and B ⊆ C(Γ). If F is a maximal forest in Γ, then Φ_{F} (Ω) is a switching-universal gain graph for Ω, and every switching universal gain graph for Ω is switching isomorphic to Φ_{F} (Ω). If Ω is gain-biased, then [Φ_{F} (Ω)] = Ω.

Proof. We repeat the proof of Theorem 2.1, but noting that we may assume ψ|_{F} ≡ 1 since any gain function can be switched into this form. ■

Much as with quasi-universal gain graphs, every switching-quasi-universal gain graph for Ω is obtainable (up to switching isomorphism) from any Φ_{F} (Ω) by taking a semi-direct product. This applies in particular to Φ(Ω).

It follows from Theorem 2.2 that all Φ_{F} (Ω) for different maximal forests F are switching isomorphic. They are in a sense almost switching equivalent to each other and to Φ(Ω). Let φ_{Ω}^{F} be φ_{Ω} switched so it is the identity on F (φ_{Ω}^{F} is unique up to conjugation in each connected component of Ω), and extend it to a homomorphism 𝔊_{Ω} → 𝔊_{Ω} . This homomorphism induces a monomorphism μ_{F} : 𝔊_{Ω,F} → 𝔊_{Ω} which satisfies φ_{Ω}^{F} = μ_{F} ∘ φ_{Ω,F} . Thus μ_{F} is the homomorphism h appearing in the definition of switching universality when Ψ is taken to be Φ(Ω). If we regard φ_{Ω,F} and φ_{Ω}^{F} as essentially the same, differing only in that the former has gain group reduced from 𝔊_{Ω} to 𝔊_{Ω,F} so as to make Φ_{F} (Ω) proper, then we may say the φ_{Ω,F} are essentially all switching equivalent to each other and to φ_{Ω} .

Similar results hold for abelian gain graphs. Given Ω, let 𝔄_{Ω} = 𝔄(E)/B, let α_{Ω} be the natural mapping E → 𝔄_{Ω} , and let A(Ω) be the gain graph (Γ, α_{Ω}, 𝔄_{Ω}), called the canonical abelian gain graph associated with Ω.

An abelian gain graph Φ is abelian quasi-universal for Ω if it satisfies quasi-universality (as defined earlier) when Ψ is restricted to being abelian. If Φ is proper it is a universal abelian gain graph for Ω. Since A(Ω) is merely Φ(Ω) with abelianized gain group, we have

Corollary 2.3. Let Ω(Γ, B), where Γ is a graph and B ⊆ C(Γ). Then A(Ω) is a universal abelian gain graph for Ω and every universal abelian gain graph for Ω is isomorphic to A(Ω). If Ω is gain-biased by abelian gains, then [A(Ω)] = Ω. ■

The abelian quasi-universal gain graphs Φ are precisely the gain graphs obtained from A(Ω) by enlarging the gain group 𝔄_{Ω} to a direct product 𝔄_{Ω} × 𝔄_{0} with an abelian group 𝔄_{0} . This follows from the remark after Theorem 2.1.

We call Φ abelian switching-quasi-universal for Ω if it satisfies switching quasi-universality when Ψ is restricted to be abelian. (One example is A(Ω).) If Φ is strongly proper it is a switching-universal abelian gain graph for Ω (or abelian switching-universal for Ω). If we abelianize 𝔊_{Ω,F} we get a group 𝔄_{Ω,F} and gain graph A_{F} (Ω). From Theorem 2.2 we have

Corollary 2.4. Let Ω = (Γ, B), where Γ is a graph and B ⊆ C(Γ). If F is a maximal forest in Γ, then A_{F} (Ω) is a switching-universal abelian gain graph for Ω, and every switching-universal abelian gain graph for Ω is switching isomorphic to A_{F} (Ω). If Ω is abelian gain-biased, then [A_{F} (Ω)] = Ω. ■

Again, any switching-quasi-universal abelian gain graph is obtained (up to isomorphism) from any A_{F} (Ω) by taking a direct product; this applies in particular to A(Ω).

3. Topological gains.

All gain-biased graphs can be obtained by topological means. The first thing to note is that embedding a graph yields gains.

Theorem 3.1. Let Γ be a graph embedded in a topological space X. Let B_{X} be the class of circles of Γ that are contractible in X and N_{X} the class of circles which are homologically null. Then (Γ, B_{X}) is gain-biased and (Γ, N_{X}) is abelian gain-biased.

Proof. We assume X is pathwise connected; if it is not, we may work separately in each path component. We describe the construction of a gain graph Ψ_{F} (Γ, X) for (Γ, B_{X}), from which the theorem follows since the homology group H_{1}(X) is the abelianized fundamental group.

Let F be a maximal forest in Γ. In each component F_{i} (indexed by a set I) let r_{i} be a root node. For definiteness say that 0 ∈ I. Our gain group will be the fundamental group π_{1}(X, r_{0}). Let Q_{i}, for i ∈ I, be a topological path from r_{0} to r_{i}; and let R_{v}, for v ∈ N, be the concatenation of Q_{i} with the unique simple walk in F from r_{i} to v (regarded as a topological path). (We assume Q_{0} is the constant path.) We assign to f ∈ F the gain φ(f) = 1 and to e ∉ F the gain φ(e) = [R_{v}eR_{w}^{−1}], where e is oriented from v to w (these being its endpoints) and [P] denotes the homotopy class of a topological path P. This defines Ψ_{F} (Ω, X).

It is easy to see that C ∈ B_{X} if and only if C has gain 1. ■

We call Ψ_{F} (Γ, X) a topological gain graph and (Γ, B_{X}) a topologically biased graph. Abelianizing Ψ_{F} (Γ, X) yields a gain graph Ξ_{F} (Γ, X) whose gain group is H_{1}(X); the gains are χ_{F} (e) = 0 for e ∈ F, χ_{F} (e) = homology class of R_{v}eR_{w}^{−1} for e ∉ F. We call Ξ_{F} (Γ, X) a homology gain graph and (Γ, N_{X}) a homologically biased graph. Theorem 3.1 says that topologically and homologically biased graphs are examples of gain-biased graphs. The main result of this section is the converse.

Theorem 3.2. Every gain-biased graph is topologically biased. Every abelian gain-biased graph is homologically biased.

This is a corollary of a more general statement. By attaching a 2-cell simply to a topological space we mean attaching a disk by means of a homeomorphism from the boundary into the space. We regard a graph as defining a topological space in the obvious way.

Proposition 3.3. Let Ω = (Γ, B), where Γ is a graph and B ⊆ C(Γ). Let X(Ω) be the topological space obtained by attaching a 2-cell simply to each circle in B. Then (Γ, B_{X(Ω)}) = [Φ(Ω)]. Indeed, Ψ_{F} (Γ, X(Ω)) ≅ Φ_{F} (Ω).

Proof. It suffices to prove the last assertion. We may assume Γ is connected.

Let P denote a walk in Γ. A combinatorial homotopy is a sequence of transformations by the following two operations and their inverses.

(H1) If P = Qee^{−1}R, replace P by QR.

(H2) If P = QCR, where C is a simple closed walk along a balanced circle, replace P by QR.

Let [P] denote the combinatorial-homotopy equivalence class of P. For r ∈ N, the group π(Ω, r) of combinatorial homotopy classes of walks from r to r (where multiplication is concatenation) is generated by the classes [P_{v}eP_{w}^{−1}] for e ∉ F, where e has endpoints v and w and is oriented from v to w.

If a walk in Γ is regarded as an element of 𝔉(E), a combinatorial homotopy class is an element of 𝔊_{Ω} . Thus, we may define ψ : E → 𝔊_{Ω} by ψ(e) = [P_{v}eP_{w}^{−1}]. Evidently ψ ∼ φ_{Ω} ; since ψ|_{F} ≡ 1, ψ is a possible choice for φ_{Ω}^{F}. It follows that π(Ω, r) = Im μ_{F} , where μ_{F} : 𝔊_{Ω,F} → 𝔊_{Ω} is the monomorphism associated to φ_{Ω}^{F} = ψ. Therefore Ψ_{F} (Ω, r) = (Γ, ψ, π(Ω, r)) is isomorphic via μ_{F}^{−1} to Φ_{F} (Ω).

The obvious way of regarding a walk as a topological path yields an isomorphism of π(Ω, r) with π(X(Ω), r). This follows directly from the analogous statement about simplicial complexes (see for instance [1, Theorem 6.3.2] or [2, Section 3.6]). Thus, Ψ_{F} (Γ, X(Ω)) is naturally isomorphic to Ψ_{F} (Ω, r). But we have observed the isomorphism of the latter to Φ_{F} (Ω). Thus, we are done. ■

Proof of Theorem 3.2. The first part is obvious from Proposition 3.3. The second part follows because A_{F} (Ω) and Ξ_{F} (Γ, X(Ω)) are just the commutative versions of Φ_{F} (Ω) and Ψ_{F} (Γ, X(Ω)). ■

Proposition 3.4. Any gain graph is switching isomorphic to a topological gain graph. Any abelian gain graph is switching isomorphic to a homological gain graph.

Sketch of Proof. One can attach 2-cells to the gain graph Φ (if Φ is connected and strictly proper) in order to make a space X(Φ) whose fundamental group is 𝔊 and such that Φ ∼ Φ_{F} (Γ, X(Φ)), where F is a spanning tree. The technique is essentially the one used to prove that every group is a fundamental group; cf. [1, p. 245] or [2, Theorem 3.8.10 et seq.]. If Φ is disconnected or not strongly proper, one replaces it by a suitable extension graph.

The abelian result is immediate from the non-abelian one. ■

References 1. P.J. Hilton and S. Wylie, “Homology Theory,” Cambridge University Press, Cambridge,

1960.

2. E.H. Spanier, “Algebraic Topology,” McGraw-Hill, New York, 1966.

3. T. Zaslavsky, Biased graphs. I. Bias, balance, and gains, J. Combin. Theory Ser. B 47 (1989), 32-52.