Theory and Applications of Categories, Vol. 32, No. 23, 2017, pp. 780–802.

LEVI CATEGORIES AND GRAPHS OF GROUPS

MARK V. LAWSON AND ALISTAIR R. WALLIS

Abstract. We define a Levi category to be a weakly orthogonal category equipped with a suitable length functor and prove two main theorems about them. First, skeletal cancellative Levi categories are precisely the categorical versions of graphs of groups with a given orientation. Second, the universal groupoid of a skeletal cancellative Levi category is the fundamental groupoid of the corresponding graph of groups. These two results can be viewed as a co-ordinate-free refinement of a classical theorem of Philip Higgins.

1. Introduction

In this paper, categories are viewed as generalizations of monoids and then applied to solving some problems in group theory. This is an extension of the pioneering work to be found in [Higgins 1971] in which groups and groupoids were studied on an equal footing with groupoids being seen as generalizations of groups. This enabled some important theorems about groups to be proved in a particularly elegant way. In our paper, we show that cancellative categories enable the theory developed in [Higgins 1976] to be described in a more conceptual way. It arose from our attempt to generalize [Lawson 2008a, Lawson & Wallis 2015]. We briefly explain that work and why categories are such a natural next step from monoids.

In [Lawson 2008a], the first author described a correspondence between self-similar group actions [Nekrashevych 2005] and a class of monoids called left Rees monoids. A self-similar group action is an action of a group on a free monoid satisfying certain conditions (which are not relevant here). By using a Zappa-Szép product, a kind of two-sided semidirect product, the data of a self-similar group action can be encoded as a left Rees monoid and, significantly, conversely. In [Lawson & Wallis 2015], the authors set the above theory in a wider context. First, they introduced what they called Levi monoids. Left cancellative Levi monoids are left Rees monoids; Rees monoids are simply cancellative Levi monoids. They proved that all Levi monoids could be constructed from suitable group biactions.^{1} Second, the relationship between self-similar group actions and left Rees monoids was investigated in greater detail. Third, and significantly for this paper, so called irreducible Rees monoids were shown to be constructed from a group and an isomorphism between two of its subgroups — in other words, from a partial isomorphism. This was proved by constructing from the partial isomorphism a group biaction whose associated Levi monoid was, in fact, a Rees monoid. However, a partial isomorphism of a group is just the data needed to construct an HNN-extension. We proved that this HNN-extension was precisely the universal group of the corresponding Rees monoid showing that the theory of HNN-extensions is a part of the theory of Levi monoids. This immediately raised the question as to whether the free product of groups with amalgamation could be obtained in a similar way. We realised that the answer would be yes only if Levi monoids could be replaced by Levi categories but then if HNN-extensions and free products with amalgamation could be constructed so too could all graphs of groups [Serre 1980, Weidmann 2013]. This paper develops this idea. We prove two main theorems.

The first author was partially supported by an EPSRC grant EP/I033203/1. The second author was supported by an EPSRC Doctoral Training Account EP/P504945/1. Some of the material in this paper appeared in his PhD thesis.

Received by the editors 2016-02-29 and, in final form, 2017-07-11.

Transmitted by Richard Blute. Published on 2017-07-27.

2010 Mathematics Subject Classification: 18B40, 20E06.

Key words and phrases: Graphs of groups, self-similar groupoid actions, cancellative categories.

\begin{matrix}c \\ ◯ \end{matrix} Mark V. Lawson and Alistair R. Wallis, 2017. Permission to copy for private use granted.

1That is, a given group acting both on the left and the right on a given set in such a way that the

THEOREM 4.17 Skeletal cancellative Levi categories are a categorical way of describing graphs of groups with a given orientation.

Levi categories are defined in Section 2, whereas in Section 3 and Section 4 the structure of skeletal cancellative Levi categories is derived and the nature of their connection with graphs of groups explained.

THEOREM 5.4 A skeletal cancellative Levi category C can be embedded into its universal groupoid G where G is precisely the fundamental groupoid of the graphs of groups associated with C.

This is proved in Section 5.

This paper aims to be intelligible to both category theorists and semigroup theorists. This means that occasionally we will define a term that one camp will find obvious. We would ask the reader to bear with us, for in those situations it is a member of the other camp who is being addressed. Although this paper uses both semigroups and categories, it can hardly be said to use semigroup theory or category theory. Any theory we need is developed explicitly. Rather, the perspective of the paper is to treat categories as generalized monoids. Accordingly, we review some basic definitions here which combine the semigroup and category theory points of view.

The elements of a category C are called arrows and the set of identities of C is denoted by C_{o}. Each arrow a has a domain identity, denoted by d(a), and a codomain identity denoted by r(a). The product ab exists, written ∃ab, if and only if r(a) = d(b). Our products should be conceived of thus

e ⟶^{a} f ⟶^{b} i.

actions associate.

Given identities e and f, the set of arrows eCf is called a hom-set, and eCe is a monoid called the local monoid at e. Arrows in the same hom-set are said to be parallel. A category is called left (resp. right) cancellative if ax = ay (resp. xa = ya) implies that x = y. A cancellative category is one which is both left and right cancellative. An arrow a is invertible if there is an arrow a^{−1}, called an inverse, such that aa^{−1} = d(a) and a^{−1}a = r(a). A category in which every arrow is invertible is a groupoid. If a groupoid is the disjoint union of its local groups then it is totally disconnected. The set of invertible elements G of a category C forms a groupoid with the same set of identities called the groupoid of invertible elements. The group of invertible elements of the local monoid at e is called the local group at e, and is denoted by G_{e}. A category in which the only invertible elements belong to local monoids is called skeletal. The groupoid of invertible elements of a skeletal category is totally disconnected.

What gives this paper a semigroup flavour is that we study various kinds of ideals inside a category. In semigroup theory, ideals lead to Green’s relations [Lallement 1979]. They may also be defined for categories [Margolis & Pin 1987]. We define them from scratch and will prove any properties we need. No previous exposure to such relations is necessary to understand this paper. A principal right ideal in a category C is a subset of the form aC where a ∈ C. We may similarly define principal left ideals and principal ideals. The Green’s relations for categories needed for this paper are defined as follows. Define a ℛ b if and only if aC = bC and a 𝒥 b if and only if CaC = CbC. Both ℛ and 𝒥 are equivalence relations and ℛ ⊆ 𝒥. These two relations will play an important rôle in the co-ordinatization results of Section 5. If aC is any principal right ideal in a category C then aC ⊆ d(a)C. A principal right ideal aC is said to be maximal if aC ⊂ eC, where e is an identity, and there are no principal right ideals strictly between aC and eC. Likewise, if CaC is any principal ideal then CaC ⊆ Car(a)C ⊆ Cr(a)C. A principal ideal CaC is said to be maximal if CaC ⊂ CeC, where e is an identity, and there are no principal ideals strictly between CaC and CeC.

Finally, our thanks to the referee for prompting us to write a slightly different paper from the one first submitted.

2. Levi categories

In this section, we define the class of categories that are the subject of this paper.

2.1. Definition. A category C is said to be equidivisible (or weakly orthogonal) if for every commutative square

[figure: c; a; b; d]

either there exists an arrow, u, making the first diagram below commute or an arrow, v, making the second diagram below commute

[figure: c; a; b; d; u; c; a; b; v; d]

Next we define an appropriate notion of what it means for an element in a category to be irreducible.

2.2. Definition. An element a ∈ C of a category is said to be an atom if it is not invertible and if a = bc then either b or c is invertible.

2.3. Definition. A length functor is a functor λ: C → ℕ from a category C to the additive monoid of natural numbers satisfying the following two conditions.

(LF1) λ^{−1}(0) consists of all and only the invertible elements of C.

(LF2) λ^{−1}(1) consists of all and only the atoms of C.

2.4. Remark. We have phrased the above two axioms in their most convenient form, but it’s worth spelling out their actual content. Let λ: C → ℕ be any functor to the additive monoid of natural numbers. If a ∈ C is an invertible element then λ(a) is invertible and so λ(a) = 0. Thus the import of (LF1) is that λ^{−1}(0) only contains invertible elements. Assume now that (LF1) holds and that λ(a) = 1. If a = bc then λ(a) = λ(b) + λ(c). It follows that either b or c is invertible and so a is an atom. Thus in the presence of (LF1), the import of (LF2) is that if a is an atom then λ(a) = 1.

2.5. Definition. A Levi category is an equidivisible category equipped with a length functor. It is said to be non-trivial if it contains at least one non-invertible element.

Conceptually, Levi categories should be regarded as ℕ-graded categories.

2.6. Remark. In this paper, we shall only be interested in non-trivial Levi categories. From now on, all Levi categories will be assumed non-trivial.

2.7. Remark. The term equidivisible comes from semigroup theory and is the one we prefer in this paper. Free monoids are equidivisible and, in fact, can be characterized as those equidivisible monoids with a length function that have only trivial units, a theorem of Friedrich Wilhelm Daniel Levi (1888–1966) [Lallement 1979]. It is for this reason that ‘Levi categories’ are so named.

2.8. Example. Levi categories with one identity are precisely the Levi monoids introduced in [Lawson & Wallis 2015]. The theory of self-similar group actions can be encoded into suitable Levi monoids.

2.9. Example. Given any directed graph D, we may construct the free category D^{∗} on D. This has one identity for each vertex and consists of all finite directed paths in the graph. Multiplication is concatenation of paths. A free category with one identity is a free monoid. Free categories are Levi categories: the atoms are the edges of the graph; the length functor simply counts the number of edges in a path; the groupoid of invertible elements is trivial. The precise rôle that free categories play within the theory of Levi categories is described in Theorem 5.10.

The proofs of the following three lemmas are all trivial.

2.10. Lemma. If a is an atom in an arbitrary category and b = gah exists, where g and h are invertible, then b is an atom.

The above lemma is the basis of a description of Levi categories described in Section 3.

2.11. Lemma. Let C be a category equipped with a length functor with groupoid of invertible elements G.

1. a ℛ b ⇔ aG = bG.

2. a 𝒥 b ⇔ GaG = GbG.

3. If a is an atom and a 𝒥 b then b is an atom.

The proof of the following is immediate by Lemma 2.11.

2.12. Lemma. In a Levi category, the principal ideals generated by identities are precisely those generated by invertible elements.

We conclude this section with a result that says, in particular, that every element in a Levi category can be written as a finite product of atoms. It is also a first demonstration of the importance of the concept of ‘equidivisibility’.

2.13. Proposition. [Atomic factorization] Let C be a Levi category with length functor λ.

1. The element a is an atom if and only if aC is a maximal principal right ideal if and only if CaC is a maximal principal ideal.

2. Every non-invertible element a of C can be written as a product of atoms, where the number of atoms is equal to λ(a).

3. Let x = a_{1} … a_{m} and y = b_{1} … b_{n} where the a_{i} and b_{j} are atoms and m, n ≥ 2. Then x = y if and only if m = n and there exist invertible elements g_{1}, …, g_{n−1} such that

a_{1} = b_{1}g_{1}, a_{2} = g_{1}^{−1}b_{2}g_{2}, … a_{n} = g_{n−1}^{−1}b_{n}.

These equations are more clearly understood by means of the following interleaving diagram.

[figure: a_{2}; a_{3}; …; a_{n−1}; a_{n}; a_{1}; b_{1}; g_{1}; b_{2}; g_{2}; b_{3}; g_{3}; …; g_{n−2}; b_{n−1}; g_{n−1}; b_{n}]

Proof. (1). Suppose that a is an atom and that aC ⊆ bC. Then a = bc. But a is an atom and so either b is invertible or c is invertible. If b is invertible then bC = d(b)C whereas if c is invertible then aC = bC. Hence aC is maximal. Conversely, suppose that aC is maximal. Let a = bc. Then aC ⊆ bC. It follows that either aC = bC or bC = d(b)C. If the former occurs then λ(a) = λ(b) and if the latter occurs then b is invertible. It follows that in either case λ(c) = 0 and so c is invertible.

Suppose that a is an atom and that CaC ⊆ CbC. Then a = cbd. But a is an atom and so exactly one of c, b, d is an atom and the other two are invertible. Suppose that c is an atom. Then b is invertible and so by Lemma 2.12 the principal ideal CbC is generated by an identity. Suppose that b is an atom. Then c and d are invertible and CaC = CbC. Finally, suppose that d is an atom. Then b is invertible again and so CbC is generated by an identity. It follows that CaC is a maximal principal ideal. Conversely, suppose that CaC is maximal. Let a = bc. Then CaC ⊆ CbC. If CaC ≠ CbC then CbC is generated by an identity and so b is invertible be Lemma 2.12. If CaC = CbC then b is an atom and so c is invertible. It follows that a is an atom.

(2). Let a be a non-invertible element. We prove that either a is an atom or a = a_{1}a′, where a_{1} is an atom, a′ is non-invertible and λ(a′) < λ(a). If a is an atom then we are done. Otherwise a = b_{1}c_{1} for some b_{1} and c_{1} where neither b_{1} nor c_{1} are invertible. Observe that λ(b_{1}) < λ(a). If b_{1} is an atom then we are done, otherwise we may write b_{1} = b_{2}c_{2} again where neither b_{2} and c_{2} are atoms. Observe that λ(b_{2}) < λ(b_{1}). This process can only continue in a finite number of steps and so must terminate. It follows that if a is non-invertible and not itself an atom then we may write a = a_{1}a′ where a_{1} is an atom, λ(a′) < λ(a), and λ(a′) ≠ 0. If λ(a′) = 1 then a′ is an atom and we are done. If not, then we may repeat the above procedure with a′. The length functor ensures that this process will repeat only a finite number of times and we conclude with the desired factorization.

(3) Only one direction needs proving. Suppose that x = y. Then by applying the length functor m = n. We therefore have that

a_{1}(a_{2} … a_{m}) = b_{1}(b_{1} … b_{m}).

We now use equidivisibility. Either

a_{1} = b_{1}u and b_{2} … b_{m} = ua_{2} … a_{m} for some u

or

b_{1} = a_{1}v and a_{2} … a_{m} = vb_{2} … b_{m} for some v.

In either case, u and v are invertible since both a_{1} and b_{1} are atoms using the length functor. Thus a_{1} = b_{1}g_{1}, where v = g_{1} is invertible, and g_{1}a_{2} … a_{m} = b_{2} … b_{m}. We now repeat this procedure bracketing thus

g_{1}a_{2}(a_{3} … a_{m}) = b_{2}(b_{3} … b_{m}).

By the same argument as above, we get that g_{1}a_{2} = b_{2}g_{2} for some g_{2} invertible and g_{2}a_{3} … a_{m} = b_{3} … b_{m}. The process continues and we obtain the result.

3. The construction of Levi categories

Let C be a Levi category with groupoid of invertible elements G. By Lemma 2.10, the set of atoms of C is closed under left and right multiplication by G. This simple observation leads to the definition of what we term a ‘bimodule’. In this section, we describe how Levi categories can be constructed from bimodules in a way analogous to that in which the tensor algebra is constructed from a module. See [Lang 1993, Chapter XVI, Section 7] or [Street 2007, Chapter 6].

3.1. Definition. Let G be a groupoid and let X be a set equipped with two functions

G_{0} ⟵^{s} X ⟶^{t} G_{o}.

We suppose that there is a left groupoid action G × X → X, defined by (g, x) ↦ gx when r(g) = s(x), and a right groupoid action X × G → X, defined by (x, g) ↦ xg when t(x) = d(g), such that the two actions associate meaning that (gx)h = g(xh) when defined. We write ∃gx and ∃xg if the actions are defined. We call the structure (G, X, G) or _{G}X_{G} a (G, G)-bimodule or simply a bimodule^{2}. If ∃xg together with xg = x implies that g is an identity, then we say the action is right free^{3}. We define left free dually. A bimodule which is both left and right free is said to be bifree. We define homomorphisms and isomorphisms between (G, G)-bimodules in the obvious way.

Our first result simply formalizes the observation that began this section. The proof is a straightforward verification.

3.2. Proposition. Let C be a Levi category with G as its groupoid of invertible elements. Denote by X the set of all atoms of C equipped with the maps d, r: X → C_{0}. A bimodule (G, X, G) is defined by the left and right actions of G on X. It is right free bimodule if and only if C is left cancellative, and bifree if and only if C is cancellative

2We use the terminology bimodule rather than simply module to accord with that used in the theory of self-similar group actions [Nekrashevych 2005] which this paper is generalizing.

3Such a bimodule would be called a covering bimodule in the theory of self-similar group actions. The use of the word ‘right’ reminds us that the definition is made with respect to the right groupoid action.

We call (G, X, G) constructed as in the above proposition, the bimodule associated with C or the bimodule of atoms of C.

Our goal now is to show that from each bimodule we may construct a Levi category. We recall the standard definitions and results we need first. Let G be a groupoid that acts on the set X on the right and the set Y on the left. Define the set X ∗Y to consist of those pairs (x, y) where t(x) = s(y). A function α: X ∗ Y → Z to a set Z is called a bi-map or a 2-map if α(xg, y) = (x, gy) for all (xg, y) ∈ X ∗ Y where g ∈ G. We may construct a universal such bimap λ: X ∗ Y → X ⊗ Y in the usual way [Elkins & Zilber 1976]. However, the theory simplifies because groupoids are acting. The element x ⊗ y in X ⊗ Y is the equivalence class of (x, y) ∈ X ∗Y under the relation ∼ where (x, y) ∼ (x′, y′) if and only if (x′, y′) = (xg^{−1}, gy) for some g ∈ G. Observe that we may define s(x ⊗ y) = s(x) and t(x ⊗ y) = t(y) unambiguously. Suppose now that X is a (G, G)-bimodule. We may therefore define the tensor product X ⊗ X as a set. This set is equipped with maps s, t: X ⊗ X → G_{o}. We define g(x ⊗ y) = gx ⊗ y and (x ⊗ y)g = x ⊗ yg when this makes sense. Observe that x ⊗ y = x′ ⊗ y′ implies that gx ⊗ y = gx′ ⊗ y′, and dually. It follows that X ⊗ X is a also a bimodule. Put X^{⊗2} = X ⊗ X. More generally, we may define X^{⊗n} for all n ≥ 1 using n-maps, and we define X^{⊗0} = G where G acts on itself by multiplication on the left and right.

3.3. Lemma. Let n ≥ 2. Then

x_{1} ⊗ … ⊗ x_{n} = y_{1} ⊗ … ⊗ y_{n}

if and only if there are elements g_{1}, …, g_{n−1} ∈ G such that y_{1} = x_{1}g_{1}, y_{2} = g_{1}^{−1}x_{2}g_{2}, y_{3} = g_{2}^{−1}x_{3}g_{3}, …, y_{n} = g_{n−1}^{−1}x_{n}.

Proof. When n = 2 the results follows from the definition of ∼. For n > 2, the proof follows by induction.

3.4. Remark. Observe that if x_{1} ⊗…⊗x_{n} = y_{1} ⊗…⊗y_{n} then x_{1} … x_{n} and y_{1} … y_{n} are parallel. In addition, there is an interleaving diagram between (x_{1}, …, x_{n}) and (y_{1}, …, y_{n}) as in part (3) of Proposition 2.13.

3.5. Definition. Let X be a (G, G)-bimodule. Define

T(_{G}X_{G}) = ⋃_{n=0}^{∞} X^{⊗n}.

We shall call this the tensor category associated with the bimodule (G, X, G). Observe that we may regard X as a subset of T(_{G}X_{G}).

The justification for this terminology will follow from (1) below. The next theorem describes how to construct all Levi categories from bimodules. It will be refined in subsequent sections.

3.6. Theorem. [Levi categories from bimodules] Let (G, X, G) be a bimodule.

1. T(_{G}X_{G}) is a Levi category whose associated bimodule is (G, X, G).

2. The category T(_{G}X_{G}) is left (resp. right) cancellative if and only if (G, X, G) is right (resp. left) free.

3. Let C be a category whose groupoid of invertible elements is G. Regard C as a (G, G)-bimodule under left and right multiplication. Let θ: X → C be any bimodule morphism to C. Then there is a unique functor Θ: T(_{G}X_{G}) → C extending θ.

4. Every Levi category is isomorphic to the tensor category of its associated bimodule.

Proof. (1). The identities of the category are the same as the identities of G. The element x_{1} ⊗ … ⊗ x_{n} has domain d(x_{1}) and codomain r(x_{n}). Define λ(g) = 0, when g ∈ G, and λ(x_{1} ⊗ … ⊗ x_{n}) = n, when n ≥ 1. The elements of length 0 are precisely the elements of G and so the invertible elements; the elements of length 1 are precisely the elements of X. Multiplication is tensoring of sequences that begin and end in the right places and left and right actions by elements of G. Formally, we are using the fact that there is a canonical isomorphism

X^{⊗p} ⊗ X^{⊗q} ≅ X^{⊗(p+q)}.

The proof of equidivisibility is essentially the same as that of [Lawson 2008a, Proposition 5.6]. Let u, v, x, y ∈ T(_{G}X_{G}) be such that

[figure: x; u; v; y]

Thus u ⊗ v = x ⊗ y. Let u = u_{1} ⊗ … ⊗ u_{m}, v = v_{1} ⊗ … ⊗ v_{m}, x = x_{1} ⊗ … ⊗ x_{s} and y = y_{1} ⊗ … ⊗ y_{t} where m + n = s + t. There is an interleaving diagram connecting u ⊗ v with x ⊗ y. Suppose that λ(u) < λ(x). Then m < s. Define w = g_{m}^{−1}x_{m+1} ⊗ … ⊗ x_{s}. Then x = u ⊗ w and a simple verification shows that v = w ⊗ y. The cases where λ(u) = λ(x) and λ(u) > λ(x) can be dealt with similarly. The case where some of the elements are invertible poses no new problems.

(2). Suppose that the category is left cancellative and that xg = x = xd(g) in the bimodule. But this can also be interpreted as a product in the category and so g = d(g), as required. Conversely, suppose that the bimodule is right free. Let x ⊗ y = x ⊗ z. From Lemma 3.3 and the fact that lengths match, we have that (x, y) = (xg, g^{−1}z) for some g ∈ G. But using the fact that the action is right free, we get that g is an identity and so y = z, as required.

(3). Define Θ(g) = g when g ∈ G and Θ(x_{1} ⊗ x_{2} ⊗ … ⊗ x_{n}) = θ(x_{1})θ(x_{2}) … θ(x_{n}). This is well-defined by Lemma 3.3. It is routine to check that this defines a functor.

(4). This now follows from (3) above, Lemma 3.3 and Proposition 2.13.

3.7. Remark. The construction of the tensor category T(_{G}X_{G}) from a bimodule (G, X, G) is a generalization of the construction of the free category from a directed graph as we now explain. Let D be a directed graph and denote by G_{o} the set of vertices of D. There are two maps

G_{0} ⟵^{s} D ⟶^{t} G_{o}

which give the source of an edge and its target, respectively. We now let the groupoid G = G_{o}, so it just consists of identities. Because the groupoid consists only of identities it follows that a tensor x ⊗ y can be identified with the product xy. Thus the elements of T(_{G}D_{G}) are just finite composable paths in D. It is now straightforward to check that T(_{G}D_{G}) = D^{∗} as in Example 2.9. In fact, Levi categories were introduced specifically as the generalizations of free categories that contain invertible elements.

4. Skeletal cancellative Levi categories and graphs of groups

In this section, we shall describe how to construct all skeletal (left) cancellative Levi categories and, as a result, we shall show that graphs of groups with a given orientation can be encoded by skeletal cancellative Levi categories. This will prove Theorem 4.17. We begin by formalizing what we mean by a set of partial homomorphisms between a collection of groups.

4.1. Definition. Let D be a directed graph. An edge x from the vertex e to the vertex f will be written e →^{x} f. With each vertex e of D we associate a group G_{e}, called the vertex group, and with each edge e →^{x} f, we associate a surjective homomorphism ϕ_{x}: (G_{e})_{x}^{+} → (G_{f})_{x}^{−} where (G_{e})_{x}^{+} ≤ G_{e} and (G_{f})_{x}^{−} ≤ G_{f}. More informally, with each edge e →^{x} f, we associate a partial homomorphism ϕ_{x} from G_{e} to G_{f}. We call this structure a diagram of partial homomorphisms. If all the ϕ_{x} are isomorphisms then we shall speak of a diagram of partial isomorphisms.

4.2. Remark. The identity of the group G_{e} will often be denoted by e.

4.3. Example. The simplest example of a diagram of partial homomorphisms is where the directed graph has one vertex and one loop. This means that there is one group G along with two subgroups G^{+}, G^{−} ≤ G and a surjective homomorphism ϕ: G^{+} → G^{−}.

4.4. Example. The next simplest example of a diagram of partial homomorphisms is where the directed graph has two vertices e and f and one edge x from e to f. In this case, this means that there are two groups G_{e}, G_{f} along with two subgroups G_{e}^{+} ≤ G_{e} and G_{f}^{−} ≤ G_{f} and a surjective homomorphism ϕ: G_{e}^{+} → G_{f}^{−}.

In this section, we shall prove the following.

4.5. Theorem. Each skeletal cancellative (resp. left cancellative) Levi category may be constructed from a diagram of partial isomorphisms (resp. homomorphisms).

Because of our work in Section 3, specifically Theorem 3.6, we need only prove the above theorem at the level of right free bimodules. To do this, we generalize a construction in [Nekrashevych 2005] from groups to groupoids using an idea of [Cohn 1985].

4.6. Lemma. [From diagrams to bimodules] Let D be a diagram of partial homomorphisms with set of edges E, vertices V and groups G_{e} where e ∈ V. Put G = ⨆_{e∈V} G_{e}. Then G is a totally disconnected groupoid. Define

G ∗ E ∗ G = {(g, x, h): where e →^{x} f and g ∈ G_{e} and h ∈ G_{f}}.

Define the relation ≡ on the set G ∗ E ∗ G by

(g_{1}, x_{1}, h_{1}) ≡ (g_{2}, x_{2}, h_{2}) ⇔ x_{1} = x_{2} = x(say), g_{2}^{−1}g_{1} ∈ (G_{e})_{x}^{+} and ϕ_{x}(g_{2}^{−1}g_{1}) = h_{2}h_{1}^{−1}.

Then ≡ is an equivalence relation. Denote the ≡-class containing (g, x, h) by [g, x, h]. Define a left action by g[g_{1}, x, h_{1}] = [gg_{1}, x, h_{1}] when ∃gg_{1} and a right action by [g_{1}, x, h_{1}]h = [g_{1}, x, h_{1}h] when ∃h_{1}h. Then the set G ∗ E ∗ G with the above two actions is a right free bimodule which we denote by B(D). This bimodule is bifree if and only if D is a diagram of partial isomorphisms.

Proof. The proof is a sequence of routine verifications. We simply prove the last claim. Suppose that D is a diagram of partial isomorphisms. Then g[g_{1}, x, h] = [g_{1}, x, h] if and only if ϕ_{x}(g_{1}^{−1}gg_{1}) = 1 which implies that g = 1 as required. Conversely, suppose that B(D) is bifree. We prove that the diagram D is of partial isomorphisms. Suppose not. Then for some edge x from vertex e to vertex f the homomorphism ϕ_{x} is not injective. Let g ≠ 1 be such that ϕ_{x}(g) = 1. Observe that g[1, x, 1] = [1, x, 1] which contradicts our assumption.

4.7. Example. We give an example of the above construction in the case where our graph has two vertices e and f and one edge x from e to f. This means there are two groups G_{e}, G_{f} along with two subgroups G_{e}^{+} ≤ G_{e} and G_{f}^{−} ≤ G_{f} and a surjective homomorphism ϕ: G_{e}^{+} → G_{f}^{−}. Since G_{e}^{+} ≤ G_{e} we can consider left cosets gG_{e}^{+} and since G_{f}^{−} ≤ G_{f} we can consider right cosets G_{f}^{−}h. Because there is only one edge in this graph, the set G ∗ X ∗ G is just the set G_{e} × G_{f}. Then (g_{1}, h_{1}) ≡ (g_{2}, h_{2}) if and only if g_{2}^{−1}g_{1} = g ∈ G_{e}^{+} and h_{2}h_{1}^{−1} = ϕ(g) ∈ G_{f}^{−}. In particular, g_{1} and g_{2} belong to the same left coset of G_{e}^{+}, and h_{1} and h_{2} belong to the same right coset of G_{f}^{−}. Explicitly

[g, h] = {(gk, ϕ(k^{−1})h): k ∈ G_{e}^{+}}.

We now show how to go in the opposite direction.

4.8. Definition. Let (G, X, G) be a right free bimodule where G is totally disconnected.^{4} Define a relation 𝒞 on X by x 𝒞 y if and only if y = gxh for some g, h ∈ G.

Clearly, 𝒞 is an equivalence relation on the set X. Because G is totally disconnected, if x 𝒞 y then s(x) = s(y) and t(x) = t(y).

4.9. Lemma. [From bimodules to diagrams] Let (G, X, G) be a right free bimodule where G is totally disconnected. With each transversal of the 𝒞 -classes, we may associate a diagram D(_{G}X_{G}) of partial homomorphisms. This is a diagram of partial isomorphisms if and only if the bimodule is bifree.

Proof. Choose a transversal E of the 𝒞 -classes. Define the directed graph D = D(_{G}X_{G}) to have as vertices the set of identities of G and edges the elements of E where if x ∈ E then s(x) →^{x} t(x). With each vertex e we associate the group G_{e}. Consider now the edge

e →^{x} f. Define

(G_{e})_{x}^{+} = {g ∈ G_{e}: gx = xh for some h ∈ G_{f}},

where the + means right-moving, and

(G_{f})_{x}^{−} = {h ∈ G_{f}: gx = xh for some g ∈ G_{e}},

where the − means left-moving. Define ϕ_{x}(g) = h if g ∈ (G_{e})_{x}^{+} and gx = xh where h ∈ G_{f}. In a right free bimodule the right action is free and so ϕ_{x} is a function. A simple computation shows that it is, in fact, a homomorphism. We have therefore constructed a diagram of partial homomorphisms.

Assume the bimodule is bifree. By definition gx = xϕ_{x}(g) where g ∈ G_{x}^{+}. Suppose that g_{1}x = g_{2}x. Then x = (g_{1}^{−1}g_{2})x and so by left freeness we have that g_{1}^{−1}g_{2} is an identity and so g_{1} = g_{2}. Thus ϕ_{x} is injective and so an isomorphism. The proof of the converse is straightforward.

The above construction depends on the choice of transversal E of the 𝒞 -classes. We show that this is not really important.

4.10. Definition. Let D_{1} and D_{2} be two diagrams of partial homomorphisms having the same vertex sets, the same vertex groups, and edge sets that differ only in labelling. We say these two diagrams of partial homomorphisms are conjugate if for each edge e →^{x} f in D_{1} and corresponding edge e →^{y} f in D_{2} there are inner automorphisms α_{x,y}: G_{e} → G_{e} and β_{x,y}: G_{f} → G_{f} such that α_{x,y}((G_{e})_{x}^{+}) = (G_{e})_{y}^{+} and β_{x,y}((G_{f})_{x}^{−}) = (G_{f})_{y}^{−} and β_{x,y}ϕ_{x} = ϕ_{y}α_{x,y}.

4.11. Lemma. Let _{G}X_{G} be a right free bimodule. Then the diagrams of partial homomorphisms associated with two transversals E and E′ of the 𝒞 -classes are conjugate.

4This is the case needed in our categorical approach to Bass-Serre theory.

Proof. We denote the elements of E by x_{i} where i ∈ I and the elements of E′ by y_{i} where i ∈ I and assume that x_{i} 𝒞 y_{i}. Choose g_{i}, h_{i} ∈ G such that x_{i} = g_{i}y_{i}h_{i}. Let e →^{x_{i}} f and g ∈ (G_{e})_{x_{i}}^{+}. Then

(g_{i}^{−1}gg_{i})y_{i} = y_{i}(h_{i}ϕ_{x_{i}}(g)h_{i}^{−1}).

Thus

h_{i}ϕ_{x_{i}}(g)h_{i}^{−1} = ϕ_{y_{i}}(g_{i}^{−1}gg_{i}).

Define inner automorphisms β_{i}(−) = h_{i}(−)h_{i}^{−1} and α_{i}(−) = g_{i}^{−1}(−)g_{i} where α_{i}: G_{e} → G_{e} and β_{i}: G_{f} → G_{f}. We therefore have β_{i}ϕ_{x_{i}} = ϕ_{y_{i}}α_{i} and α_{i}((G_{e})_{x_{i}}^{+}) = (G_{e})_{y_{i}}^{+} and β_{i}((G_{f})_{x_{i}}^{−}) = (G_{f})_{y_{i}}^{−}. Thus the two diagrams are conjugate

We have described two constructions

D ↦ B(D) and _{G}X_{G} ↦ D(_{G}X_{G}).

We now describe what happens when they are iterated.

4.12. Proposition. [Diagrams and bimodules]

1. Let _{G}X_{G} be a right free bimodule and let E be a transversal of the 𝒞 -classes. Then GX_{G} is isomorphic to B(D(_{G}X_{G})).

2. Let D be a diagram of partial homomorphisms. Then D is conjugate to D(B(D)).

Proof. (1) Let x ∈ X. Then x 𝒞 y for a unique y ∈ E. By definition, x = g_{1}yh_{1} for some g_{1}, h_{1} ∈ G. Suppose also that x = g_{2}yh_{2}. Then g_{2}^{−1}g_{1}y = yh_{2}h_{1}^{−1}. It follows that (g_{1}, y, h_{1}) ≡ (g_{2}, y, h_{2}). We may therefore define a function θ: X → B(D) by θ(x) = [g_{1}, x, h_{1}]. It remains to show that this is a bijection and an isomorphism of bimodules both of which are now straightforward.

(2) Choose the specific transversal of those elements of the form [e, x, f] where e →^{x} f is an edge of the diagram D. It is easy to check that we get back exactly the diagram of partial homomorphisms we started with. If we choose a different transversal then Lemma 4.11, and what we have just proved, tell us that the corresponding diagram of partial homomorphisms is conjugate to D.

We shall now show explicitly how to construct a diagram of partial homomorphisms from a skeletal left cancellative Levi category. The proof of the following is immediate from the definitions and Lemma 2.11 and simply justifies our use of the 𝒥 -relation.

4.13. Lemma. Let C be a skeletal left cancellative Levi category. If x and y are atoms then x 𝒥 y if and only if x 𝒞 y.

4.14. Definition. Let C be a skeletal left cancellative Levi category. Choose a transversal E of the set of 𝒥 - classes of the atoms. We call this an atomic 𝒥 -transversal.

4.15. Proposition. [From category to diagram] Let C be a skeletal left cancellative Levi category with atomic 𝒥 -transversal E. Construct a diagram D(C) of partial homomorphisms from C as follows.

1. The set of identities of C is the set of vertices of D(C).

2. At each vertex e in D(C), we attach the local group G_{e} of C.

3. The edges of D(C) are the elements x ∈ E.

4. If x ∈ E and e →^{x} f define

(G_{e})_{x}^{+} = {g ∈ G_{e}: gx = xh for some h ∈ G_{f}},

and

(G_{f})_{x}^{−} = {h ∈ G_{f}: gx = xh for some g ∈ G_{e}},

and

ϕ_{x}(g) = h if g ∈ (G_{e})_{x}^{+} and h ∈ (G_{f})_{x}^{−} and gx = xh.

Then (G_{e})_{x}^{+} ≤ G_{e} and (G_{f})_{x}^{−} ≤ G_{f} and ϕ_{x} is a surjective homomorphism.

In addition, C is right cancellative if and only if all the homomorphisms ϕ_{x} in D(C) defined above are also injective and so in fact isomorphisms.

Proof. By Lemma 4.13 and Lemma 4.9, we have therefore defined a diagram D(C) of partial homomorphisms from C based on our choice of transversal E. By Proposition 4.12 and part (4) of Theorem 3.6, the category C is isomorphic to the category T(B(D(C))). The proof of the last assertion is immediate by part (2) of Theorem 3.6 and Lemma 4.9.

The following is standard [Higgins 1976, Serre 1980, Weidmann 2013]. A graph of groups consists of the following data. It is a directed graph with vertices V and edges Y. If y ∈ Y, we write s(y) →^{y} t(y). The set Y is equipped with an involution y ↦ ȳ so that y ≠ ȳ and s(ȳ) = t(y). For each vertex e ∈ V there is a group G_{e} and for each edge y ∈ E there is a group G_{y} such that Gȳ = G_{y}. For each edge y ∈ Y, there is an injective group homomorphism μ_{y}: G_{y} → G_{t(y)}, denoted by g ↦ g^{y} for g ∈ G_{y}. A graph of groups is a symmetric description of a set of partial isomorphisms between groups. We now break that symmetry by choosing an orientation X for the set of edges. By this we mean a subset X ⊆ Y such that Y = X ∪ \overline{X} is a disjoint union. Let x ∈ X where e →^{x} f. Define

(G_{e})_{x}^{+} = μx̄(G_{x}) and (G_{f})_{x}^{−} = μ_{x}(G_{x})

and define

ϕ_{x}: (G_{e})_{x}^{+} → (G_{f})_{x}^{−} by ϕ_{x}(gx̄) = g^{x}.

We have therefore constructed a diagram of partial isomorphisms. It is clear that we can recapture the original graph of groups from this diagram with the small proviso that the groups G_{y} will be replaced by isomorphic copies. We have therefore proved the following.

4.16. Lemma. A graph of groups with a chosen orientation is just a diagram of partial isomorphisms.

4.17. Theorem. [Graphs of groups as categories] From a graph of groups equipped with a chosen orientation we may construct a skeletal cancellative Levi category C and the original oriented graph of groups may be read off from the structure of C.

Proof. We summarize the steps in this construction below.

1. Input a graph of groups with a given orientation.

2. This is nothing other that a diagram of partial isomorphisms by Lemma 4.16.

3. From the diagram of isomorphisms, we may construct a bifree bimodule whose acting groupoid is totally disconnected by Lemma 4.6.

4. From the bifree bimodule whose acting groupoid is totally disconnected, we may construct a skeletal cancellative Levi category by Theorem 3.6.

5. The diagram of partial isomorphisms in step (2) may be constructed from the skeletal cancellative Levi category constructed in step (4) by Theorem 4.15.

5. The fundamental groupoid of a graph of groups

A necessary condition for a category to be embeddable into a groupoid is that it be cancellative. Though sufficient this is far from necessary. However, skeletal cancellative Levi categories can be embedded into groupoids. To understand why, we need the following definition.

5.1. Definition. A category C is said to be right rigid if aC ∩ bC ≠ ∅ implies that aC ⊆ bC or bC ⊆ aC.

This notion was defined in [Cohn 1985] in the case of monoids.

5.2. Definition. Let aC ⊆ bC. Denote by [aC, bC] the set of principal right ideals xC such that aC ⊆ xC ⊆ bC.

5.3. Lemma.

1. A left cancellative category is right rigid if and only if it is equidivisible.

2. In a left cancellative Levi category the set [aC, bC] is linearly ordered by inclusion and contains only a finite number of elements.

Proof. (1) Suppose that the category C is right rigid and that ab = cd. Then aC∩cC ≠ ∅. We may assume without loss of generality that aC ⊆ cC. Thus a = cu. But then cub = cd and ub = d. Thus the category is equidivisible. The proof of the converse is immediate.

(2) The fact that this set is linearly ordered is immediate by part (1). Suppose that aC ⊆ xC ⊆ yC ⊆ bC. Then λ(a) ≥ λ(x) ≥ λ(y) ≥ λ(b). Suppose that λ(x) = λ(y). Then x = yu where u is invertible and so xC = yC.

In the light of the above result, it now follows from [von Karger 1997] that every cancellative Levi category may be embedded in a groupoid.^{5} This result makes it interesting to characterize what the universal groupoid of a skeletal cancellative Levi category might be. Associated with a graph of groups is its fundamental groupoid studied in [Higgins 1976]. In this section, we prove the following theorem which is the second main theorem proved in this paper.

5.4. Theorem. [The universal groupoid] The universal groupoid G of a skeletal cancellative Levi category C is the fundamental groupoid of the graph of groups with given orientation associated with C. The category C is embedded into G.

Our goal, therefore, is to make explicit the theory of skeletal cancellative categories that is implicit in [Higgins 1976]. To do this, we shall need to refine our result on the decomposition of the elements of such a category into a product of atoms and we shall need to study the multiplication in such a category in more detail.

5.5. Definition. Let C be a left cancellative Levi category. A basis B for C is a transversal of the generators of the maximal principal right ideals of C.

5.6. Remark. By part (1) of Proposition 2.13, the elements of a basis are all atoms. Let C be a left cancellative Levi category with set of atoms X. Then X is a disjoint union of 𝒥 -classes by Lemma 2.11. Also using the fact that ℛ ⊆ 𝒥, it follows that each such 𝒥 -class is a union of ℛ-classes. In particular, a basis is a transversal of the ℛ-classes of X.

In what follows, we fix a basis B. Denote the subcategory of C generated by B by B^{∗}. The proof of the following is a generalization of the monoid case described in [Lawson 2008a, Proposition 3.1].

5.7. Theorem. Let C be a left cancellative Levi category with length functor λ, basis B, and groupoid of invertible arrows G.

1. Each arrow of C can be written uniquely as a finite product of elements from the basis followed by an invertible element. Thus C = B^{∗}G.

2. B^{∗} is a free category Proof. (1) Let a ∈ C which is not invertible. By Lemma 5.3 the set [aC, d(a)C] is linearly ordered by inclusion and finite. Thus it contains a maximal element bC. By the definition of the basis B, there is a unique atom a_{1} ∈ B such that bC = a_{1}C. We may therefore write a = a_{1}b where λ(b) < λ(a). This process can therefore only continue a finite number of times until we have written a = a_{1} … a_{m}g where g is invertible and m = λ(a). Suppose now that

5We do not use this result directly in this paper but it did help to motivate the theory.

a = a_{1} … a_{m}g = b_{1} … b_{m}h

where a_{i}, b_{i} ∈ B and g, h ∈ G. Observe that aC ⊆ a_{1}C, b_{1}C. But by Lemma 5.3, the category C is right rigid and so a_{1}C and b_{1}C are comparable. But both principal right ideals are maximal and so a_{1}C = b_{1}C. Since a_{1} and b_{1} have both been chosen from the transversal B, we must have that a_{1} = b_{1}. By left cancellation, a_{2} … a_{m}g = b_{2} … b_{m}h. The above argument may be repeated and so we deduce that a_{1} = b_{i} for 1 ≤ i ≤ m. It follows from this that g = h, as well.

(2) Define a directed graph to have vertices the identities of C and directed edges defined by the elements of the basis B. It is immediate from part (1) that B^{∗} is the free category generated by this directed graph.

Let C be a left cancellative Levi category and let B be a basis. We want to calculate the following product in the category

(a_{1} … a_{m}g)(b_{1} … b_{n}h)

where g, h are invertible and a_{i}, b_{j} ∈ B. Clearly, the first step is to calculate gb_{1}. By the above theorem, this can be written as a unique element in B^{∗}G. However λ(gb_{1}) = 1. It follows that we can write gb_{1} = b′g′ for a uniquely determined invertible element g′ and a uniquely determined element b′ ∈ B. We need better names for b′ and g′. This leads to the following definition which now makes sense.

5.8. Definition. Let C be a Levi category with basis B and groupoid of invertible elements G. Let g ∈ G and a ∈ B. Define g · a ∈ B and g|_{a} ∈ G to be the unique elements such that

ga = (g · a)g|_{a}.

We call the operation · action and the operation | restriction.

5.9. Remark. The properties satisfied by action and restriction are well-known in the theory of Zappa-Szép products of categories but will be omitted here.

In terms of the above definition, we therefore have that

(a_{1} … a_{m}g)(b_{1} … b_{n}h) = a_{1} … a_{m}(g · b_{1})(g|_{b_{1}}b_{2}) … b_{n}h

and we need to calculate (g|_{b_{1}}b_{2}). It’s now clear that the two operations of action and restriction are enough to allow us to compute all products with repeated application causing changes to ripple through the sequence of symbols.

This is all we need to know in what follows but for completeness we conclude by stating a theorem not used in this paper but included for interest. See [Brin 2005] for the definition of Zappa-Szép products, and [Lawson 2008b] for a proof in a more general setting. The hard direction of the proof follows from Theorem 5.7, whereas the easy direction is by direct verification.

5.10. Theorem. A category is a left cancellative Levi category if and only if it is isomorphic to the Zappa-Szép product of a free category by a groupoid.

This result enables us to regard left cancellative Levi categories as encoding information about self-similar groupoid actions. We shall not pursue this idea here, but see [Lawson 2008b, Wallis 2013]. The following is now immediate and describes the rôle played by free categories within the class of Levi categories.

5.11. Corollary. Free categories are the left cancellative Levi categories with trivial groupoids of invertible elements.

We now describe a co-ordinatization result of a type common in semigroup theory^{6}. Let C be a skeletal cancellative Levi category with groupoid of invertible elements G. Let a ∈ C be a non-invertible element where e →^{a} f. We shall be interested in the structure of the 𝒥 -class 𝒥_{a} containing a. If b ∈ 𝒥_{a} then b = gah for some g, h ∈ G. The elements g and h need not be unique. Suppose therefore that a = gah = kal. Then (k^{−1}g)a = a(lh^{−1}). This motivates us to define

H = {g ∈ G_{e}: ga = ag′ for some g′ ∈ G_{f}},

a subgroup of G_{e}.

5.12. Lemma. [Co-ordinatization lemma] With the above definitions, there is a bijection between the sets 𝒥_{a}/ℛ and G_{e}/H.

Proof. Let G_{e} = ⋃_{i∈I} g_{i}H be any coset decomposition. We prove that {g_{i}a: ∈∈ I} is a transversal for J_{a}/ℛ. Clearly, g_{i}a ∈ J_{a} for all i ∈ I. Suppose that g_{i}a ℛ g_{j}a. Then g_{i}a = g_{j}ag for some g ∈ G_{f}. Thus (g_{j}^{−1}g_{i})a = ag and so by definition g_{j}^{−1}g_{i} ∈ H. It follows that g_{i} = g_{j} giving g_{i}a = g_{j}a. Now let b ∈ J_{a}. Then b = gah for some g ∈ G_{e} and h ∈ G_{f}. We may write g = g_{i}l where l ∈ H. But then

b = gah = (g_{i}l)ah = (g_{i}a)l′h

for some l′ from the definition of H. We have therefore proved that b ℛ g_{i}a.

6The first author is grateful to Stuart Margolis for some email exchanges on this issue.

Motivated by the above lemma, we now define a special kind of basis for a skeletal left cancellative Levi category.

5.13. Definition. Let C be a skeletal left cancellative Levi category. We define a basis B of C, called a co-ordinatization, as follows.

1. Choose an atomic 𝒥 -transversal Y. By Proposition 4.15, there is a corresponding diagram of partial homomorphisms such that for each x ∈ Y where e →^{x} f, there are partial homomorphisms ϕ_{x}(g) = g|_{x} where g ∈ (G_{e})_{x}^{+} for each x ∈ Y.

2. For each x ∈ Y where e →^{x} f, choose a coset decomposition G_{e} = ⋃_{i∈I} g_{i}(G_{e})_{x}^{+}. Denote by T_{x}^{+} the transversal {g_{i}: i ∈ I}. We shall require that e be an element of this transversal. Recall that e is to be regarded as the identity of G_{e}.

3. For each x ∈ Y, we have, by Lemma 2.10, a set of atoms B_{x} = {kx: k ∈ T_{x}^{+}}. Define B = ⋃_{x∈Y} B_{x}.

The fact that B is, in fact, a basis for C is immediate by Lemma 5.12.

5.14. Remark. Once we have fixed a basis, there are then well-defined defined operations of action and restriction as defined in Definition 5.8.

5.15. Lemma. Let C be a skeletal left cancellative Levi category with co-ordinatization B, atomic 𝒥 -transversal Y and groupoid of invertible arrows G. Let x ∈ Y where e →^{x} f.

1. (G_{e})_{x}^{+} = {g ∈ G_{e}: g · x = x}, the stabilizer of x under the ·-action.

2. ϕ_{x}(g) = g|_{x}.

Proof. We use the fact that C = B^{∗}G and the decomposition of elements that arises is unique. (1) Let g ∈ (G_{e})_{x}^{+}. Then by definition gx = xh for some h. But gx = (g · x)g|_{x}. Thus by uniqueness, we have that x = g · x. On the other hand, if g · x = x then gx = (g · x)g_{x} and so gx = xg|_{x}. Thus g ∈ (G_{e})_{x}^{+}.

(2) This follows by our calculations in (1).

The significance of our co-ordinatization becomes apparent in our next result.

5.16. Proposition. [Normal forms] Let C be a skeletal left cancellative Levi category with a co-ordinatization B and associated atomic 𝒥 -transversal Y.

1. If e →^{a} f is an arbitrary element of C, we may write

a = (g_{1}x_{1}) … (g_{m}x_{m})g

uniquely where x_{i} ∈ Y, g_{i} ∈ T_{x_{i}}^{+}, and g ∈ G_{f}. We call this a normal form.

2. The product of two elements in normal form is determined only by the multiplication in the local groups G_{e} and the homomorphisms ϕ_{x}.

Proof. (1) This is immediate by Theorem 5.7 and the definition of a co-ordinatization.

(2) Let

a = (g_{1}x_{1}) … (g_{m}x_{m})g and b = (h_{1}y_{1}) … (h_{m}y_{m})h

be elements of a skeletal left cancellative Levi category written as normal forms such that ∃ab. We may calculate the normal form of ab as follows. Since f = d(b), we have that g ∈ G_{f} and so we may write gh_{1} = k_{1}l where k_{1} ∈ T_{y_{1}}^{+} and l ∈ (G_{f})_{y_{1}}^{+}. Thus

g(h_{1}y_{1}) = k_{1}ly_{1} = k_{1}y_{1}l|_{y_{1}} = k_{1}y_{1}ϕ_{y_{1}}(l)

using the fact that l · y_{1} = y_{1} and l|_{y_{1}} = ϕ_{y_{1}}(l) by Lemma 5.15. This process can now be repeated with the effect rippling rightwards through the product until we get

ab = (g_{1}x_{1}) … (g_{m}x_{m})(k_{1}y_{1}) … (k_{n}y_{n})p

for some invertible arrow p in a local group.

The proposition above leads to the following. Let D be a diagram of partial homomorphisms. We shall define a category ⟨D⟩ by means of a presentation constructed from D. We first construct a new directed graph D′ from D. This contains the directed graph D but at each vertex we adjoin additional loops labelled by the elements of G_{e}. As a notational device, elements of this graph will be written [a] where a is either an edge of D or an element of one of the groups G_{e}. We construct the free category (D′)^{∗}. We now factor out by two kinds of relations:

1. [g][h] = [gh] if g, h ∈ G_{e}.

2. [g][x] = [x][ϕ_{x}(g)] where g ∈ (G_{e})_{x}^{+}.

The resulting category is denoted by ⟨D⟩. The proof of the following is now immediate by Proposition 5.16.

5.17. Theorem. [Presentation theorem] Let D be a diagram of partial homomorphisms. Then ⟨D⟩ is a skeletal left cancellative Levi category isomorphic to the category T(B(C)). It is cancellative if and only if D is a diagram of partial isomorphisms.

PROOF OF THEOREM 5.4

Observe that our proof is in all essentials equivalent to the proof of the main theorem of [Higgins 1976] and we refer to his proof at a number of points below. Recall that we have to prove that the universal groupoid G of a skeletal cancellative Levi category C is the fundamental groupoid of the graph of groups with given orientation associated with C. The category C is embedded into G.

We may assume, without loss of generality, by Section 4 that the category C arises from a graph of groups. The edges of this graph of groups are Y = X ∪ \overline{X} where here X is our chosen orientation^{7}. We construct the fundamental groupoid of this graph of groups as in [Higgins 1976]. This is the groupoid G freely generated by the arrows in Y and the elements of the local groups G_{e} subject to the following relations 1. [g][h] = [gh] whenever g, h ∈ G_{e}.

7Note that [Higgins 1976] uses X for his set of vertices whereas for us this is the set C_{o}.

2. If y ∈ Y where e →^{y} f then the relation [ȳ][g][y] = [ϕ_{y}(g)] holds for each g ∈ (G_{e})_{y}^{+}.

In the groupoid G, we have that ȳ is the inverse of y. Thus in G, we also have that

(2)′ [g][y] = [y][ϕ_{y}(g)].

The elements of G are described by normal forms in the same way as described in Proposition 5.16. By a positive normal form we mean a sequence of the form

a = (g_{1}x_{1}) … (g_{m}x_{m})g

where the x_{i} ∈ X. These are certainly normal forms in the sense of Higgins [Higgins 1976] and so are pairwise distinct. They form a category isomorphic to C by Theorem 5.17 and so C is embedded in the groupoid G. But G is the universal groupoid of C because C is generated by the relations (1) and (2)′ and G arises only by forcing the edges x to become invertible.

5.18. Remark. We may restate the above theorem in another way. A graph of groups, considered with a given orientation X, has fundamental groupoid G. The elements of G that have positive normal forms, in the sense of the above proof, form a subcategory C of C. Perforce cancellative, C is a skeletal cancellative Levi category whose universal groupoid is G, and every skeletal cancellative Levi category arises in this way.

The following two examples show that the basic building blocks of graphs of groups fit comfortably within our theory in that they arise from skeletal cancellative Levi categories with one identity and two identities, respectively.

5.19. Example. HNN extensions. A Rees monoid is a cancellative Levi category with one identity. It is automatically skeletal. Such a monoid is said to be irreducible if it has a single maximal 𝒥 -class. The universal groups of irreducible Rees monoids are precisely HNN extensions with one stable letter and was the subject of [Lawson & Wallis 2015] and motivated the work of the current paper.

5.20. Example. Amalgamated free products. Let X be a bifree (G, H)-bimodule where both G and H are groups which is irreducible in the sense that GxH = X for some x ∈ X. Such bimodules correspond to partial isomorphisms from θ_{x} from G to H. In this case, the tensor product construction is degenerate and C = G ∪ X ∪ H is a skeletal cancellative Levi category with two identities. The universal groupoid of C is connected and any local group is isomorphic to G ∗_{θ} H, the amalgamated free product of G and H via the identifying partial isomorphism θ_{x}.

The approach we have adopted to studying graphs of groups in Section 4 might be termed co-ordinate-free whereas in this section we have shown how to obtain an explicit coordinatization which relates to the choices in the classical theory of coset representatives. It now remains for later work to investigate the way in which the classical theory of graphs of groups can be developed from this categorical perspective.

LEVI CATEGORIES AND GRAPHS OF GROUPS  801

References

M. G. Brin, On the Zappa-Szép product, Comm. Algebra 33 (2005), 393–424. P. M. Cohn, Free rings and their relations, Second Edition, Academic Press, 1985. B. Elkins, J. A. Zilber, Categories of actions and Morita equivalence, Rocky Mountain J.

Math. 6 (1976), 199–225. Ph. J. Higgins, Notes on categories and groupoids, Van Nos-

trand  Reinhold  Company,  1971.  Freely  available  at

    http://www.tac.mta.ca/tac/reprints/articles/7/tr7abs.html.

Ph. J. Higgins, The fundamental groupoid of a graph of groups, J. Lond. Math. Soc. (2)

13 (1976), 145–149. G. Lallement, Semigroups and combinatorial applications, John Wiley, 1979. S. Lang, Algebra, third edition, Addison-Wesley, 1993. M. V. Lawson, A correspondence between a class of monoids and self-similar group actions

I, Semigroup Forum 76 (2008), 489–517. M. V. Lawson, Semigroups related to subshifts of graphs, in Semigroups, acts and cate-

gories with applications to graphs, Math. Stud. (Tartu), 3, Est. Math. Soc., Tartu, (2008), 92–107.

M. V. Lawson, A. Wallis, A correspondence between a class of monoids and self-similar

group actions II, Inter. J. Algebra Comput. 25 (2015), 633–668. S. W. Margolis, J. E. Pin, Inverse semigroups and extensions of groups by semilattices,

J. Algebra 110 (1987), 277–297. V. Nekrashevych, Self-similar groups, AMS, 2005. J.-P. Serre, Trees, Springer, 1980. R. Street, Quantum groups, CUP, 2007. B. von Karger, Temporal algebra, Habilitationsschrift, Christian-Albrechts-Universität,

Kiel, 1997. A. Wallis, Semigroup and category-theoretic approaches to partial symmetry, PhD Thesis,

Heriot-Watt University, July 2013. R. Weidmann, Combinatorial and geometric group theory, lecture notes, Christian-

Albrechts-Universität, Kiel, 2013.

Mark V. Lawson, Department of Mathematics and the Maxwell Institute for Mathematical Sciences, Heriot-Watt University, Riccarton, Edinburgh EH14 4AS, UK

Alistair R. Wallis, School of Mathematical and Computer Sciences, Heriot-Watt University, No 1 Jalan Venna P5/2, Precinct 5, 62200 Putrajaya, MALAYSIA

Email: M.V.Lawson@hw.ac.uk
      A.Wallis@hw.ac.uk
This article may be accessed at http://www.tac.mta.ca/tac/

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods. Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication. Full text of the journal is freely available from the journal’s server at http://www.tac.mta.ca/tac/. It is archived electronically and in printed paper format.

Subscription information Individual subscribers receive abstracts of articles by e-mail as they are published. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors The typesetting language of the journal is TEX, and L^{A}TEX2e is required. Articles in PDF format may be submitted by e-mail directly to a Transmitting Editor. Please obtain detailed information on submission format and style files at http://www.tac.mta.ca/tac/.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: barr@math.mcgill.ca

Assistant TEX editor. Gavin Seal, Ecole Polytechnique Fédérale de Lausanne:

gavin seal@fastmail.fm

Transmitting editors.

Clemens Berger, Université de Nice-Sophia Antipolis: cberger@math.unice.fr Richard Blute, Université d’ Ottawa: rblute@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: ronnie.profbrown(at)btinternet.com Valeria de Paiva: Nuance Communications Inc: valeria.depaiva@gmail.com Ezra Getzler, Northwestern University: getzler(at)northwestern(dot)edu Kathryn Hess, Ecole Polytechnique Fédérale de Lausanne: kathryn.hess@epfl.ch Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk Anders Kock, University of Aarhus: kock@imf.au.dk Stephen Lack, Macquarie University: steve.lack@mq.edu.au F. William Lawvere, State University of New York at Buffalo: wlawvere@buffalo.edu Tom Leinster, University of Edinburgh: Tom.Leinster@ed.ac.uk Ieke Moerdijk, Utrecht University: i.moerdijk@uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Giuseppe Rosolini, Università di Genova: rosolini@disi.unige.it Alex Simpson, University of Ljubljana: Alex.Simpson@fmf.uni-lj.si James Stasheff, University of North Carolina: jds@math.upenn.edu Ross Street, Macquarie University: ross.street@mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Université du Québec à Montréal : tierney.myles4@gmail.com R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca