On graph inverse semigroups

Abstract

We study the relationship between the graph inverse semigroups of two graphs when there is a directed immersion between the graphs and we provide structural information about graph inverse semigroups of finite graphs that admit a directed cover onto a bouquet of circles. We provide a topological characterization of the universal groups of the local submonoids of a graph inverse semigroup. We also find necessary and sufficient conditions for a homomorphic image of a graph inverse semigroup to be another graph inverse semigroup.

1 Introduction

All graphs under consideration in this paper will be directed graphs with either finitely many or countably infinitely many vertices and edges. We denote the set of vertices of a graph $\varGamma$ by ${\varGamma }^0$ and the set of edges of $\varGamma$ by ${\varGamma }^1$. If $e \in \varGamma ^1$ then e is a directed edge from a vertex that we will denote by s(e) to a vertex that we will denote by r(e). In fact, s and r can be considered as mappings of $\varGamma ^1$ into $\varGamma ^0$, respectively called the source mapping and the range mapping for $\varGamma$. Thus for each vertex $v \in \varGamma ^0, s^{-1}(v) = \{e \in \varGamma ^1 : s(e) = v\}$ and the out-degree of a vertex v is $|s^{-1}(v)|$, the number of directed edges with source v. (This is referred to as the index of v by some authors). We allow for the possibility that $s(e) = r(e) = v \in \varGamma ^0$, in which case e is a loop at v. A directed path in $\varGamma$ is a finite sequence $p = e_1e_2\ldots e_n$ of edges $e_i \in \varGamma ^1$ with $r(e_i) = s(e_{i+1})$ for $i = 1,\ldots ,n-1$. We define $s(p) = s(e_1)$ and $r(p) = r(e_n)$ and refer to p as a directed path from s(p) to r(p). We also consider a vertex v as being an empty (directed) path (i.e. a path with no edges) based at v and with $s(v) = r(v) = v$.

It is convenient to extend the notation so as to allow paths in which edges are read in either the positive or negative direction. To do this, we associate with each edge e an “inverse edge” $e^*$ (sometimes called a “ghost edge” by some authors) with $s(e^*) = r(e)$ and $r(e^*) = s(e)$. Also define $(e^*)^* = e$. We denote by $(\varGamma ^1)^*$ the set $\{e^* : e \in \varGamma ^1\}$ and assume that $\varGamma ^1 \cap (\varGamma ^1)^* = \emptyset$ and that the map $e \rightarrow e^*$ is a bijection from $\varGamma ^1$ to $(\varGamma ^1)^*$. With this convention, we can define a path in $\varGamma$ as a sequence $p = e_1e_2\ldots e_n$ with $e_i \in \varGamma ^1 \cup (\varGamma ^1)^*$ and $r(e_i) = s(e_{i+1})$ for $i = 1,\ldots ,n-1$ and for each path $p = e_1e_2\ldots e_n$ we define the inverse path to be $p^* = e_n^*\ldots e_2^*e_1^*$. As usual, $s(p) = s(e_1)$ and $r(p) = r(p_n)$. The graph $\varGamma$ is said to be connected if for all $v,w \in \varGamma ^0$ there is at least one path p with $s(p) = v$ and $r(p) = w$ while $\varGamma$ is said to be strongly connected if for all $v,w \in \varGamma ^0$ there is at least one directed path p with $s(p) = v$ and $r(p) = w$. A path p is a circuit at v if $s(p) = r(p) = v$. Thus, for example, a path of the form $ee^*$ where e is an edge with $s(e) = v$ is a circuit at v. A path $p = e_1e_2\ldots e_n$ is called reduced if $e_i \ne e_{i+1}^*$ for each i. A reduced circuit is a circuit $p = e_1e_2\ldots e_n$ that is a reduced path and such that $e_1 \ne e_n^*$. A directed circuit is a directed path that is a circuit. A cycle is a directed circuit $e_1e_2\ldots e_n$ such that $s(e_i) \ne s(e_j)$ if $i, j \in \{1,2,\ldots ,n\}$ and $i \ne j$. Two cycles $C_1$ and $C_2$ are said to be conjugate if $C_1 = e_1e_2\ldots e_n$ and $C_2 = e_ie_{i+1}\ldots e_ne_1\ldots e_{i-1}$ for some i. The graph $\varGamma$ is acyclic if it has no non-trivial cycles. $\varGamma$ is called a tree if it is connected and has no non-trivial reduced circuits. Equivalently (see for example Hatcher’s book [5]), $\varGamma$ is a tree if it is connected and its fundamental group $\pi _1(\varGamma )$ is trivial. Thus trees are connected acyclic graphs but connected acyclic graphs are not necessarily trees.

Graph inverse semigroups are semigroups naturally built from directed graphs. We recall that an inverse semigroup is a semigroup S such that for every $a \in S$ there exists a unique element $a^{-1} \in S$ such that $a = aa^{-1}a$ and $a^{-1} = a^{-1}aa^{-1}$. The book by Lawson [8] is a standard reference for the theory of inverse semigroups and their connections to other fields: any undefined notation and concepts about inverse semigroups that are used in this paper may be found in [8]. In particular, we shall make use (often without comment) of the elementary fact that idempotents of an inverse semigroup commute. We shall also make use of the natural partial order on an inverse semigroup S (defined by $a \le b$ if $a = eb$ for some idempotent e of S).

All of the inverse semigroups that arise in this paper (except non-trivial groups) have a zero, which we denote by 0 (or $0_S$ if we need to specify the inverse semigroup S under consideration) and all homomorphisms under consideration will map 0 to 0. Thus, (unless it is a non-trivial group), an inverse semigroup S will be assumed to have a zero, and a homomorphism $f: S \rightarrow T$ between inverse semigroups S and T will be assumed to map $0_S$ onto $0_T$.

Graph inverse semigroups were first introduced by Ash and Hall [2] (for a restricted class of directed graphs) in connection with their study of the partially ordered set of ${\mathcal {J}}$-classes of a semigroup. Graph inverse semigroups generalize the polycyclic monoids introduced by Nivat and Perrot [13] and arise very naturally in the extensive theories of graph $C^*$-algebras and Leavitt path algebras. Graph inverse semigroups have been studied in their own right by several authors, for example Costa and Steinberg [3], Jones and Lawson [6], Lawson [9], Krieger [7], Mesyan and Mitchell [12] and Wang [16].

Define the graph inverse semigroup $I({\varGamma })$ of a directed graph $\varGamma$ as the semigroup generated by ${\varGamma }^{0} \cup {\varGamma }^1 \cup (\varGamma ^1)^*$ together with a zero 0 subject to the relations

• (1) $s(e)e = er(e) = e$ for all $e \in \varGamma ^0 \cup {\varGamma }^{1} \cup (\varGamma ^1)^*$;

• (2) $u v = 0$ if $u,v \in {\varGamma }^{0}$ and $u \ne v$;

• (3) $e^{*} f = 0$ if $e,f \in {\varGamma }^1$ and $e \ne f$;

• (4) $e^{*} e = r(e)$ if $e \in {\varGamma }^1$.

We emphasize that condition (1) of the definition above implies that $v^2 = v$ for all $v \in \varGamma ^0$; that is, the vertices of $\varGamma$ are idempotents in $I(\varGamma )$. Condition (1) also implies that $e^*s(e) = r(e)e^* = e^*$ for all $e \in \varGamma ^1$.

It is not difficult to see that $I(\varGamma )$ is in fact an inverse semigroup. A straightforward argument shows that every non-zero element of a graph inverse semigroup $I(\varGamma )$ may be uniquely written in the form $pq^*$ where p and q are directed (possibly empty) paths with $r(p) = r(q)$. We refer to this as the canonical form of a non-zero element of $I(\varGamma )$. The inverse of an element $pq^*$ is of course $qp^*$. If $pq^*$ and $rs^*$ are non-zero elements of $I(\varGamma )$, then the product $pq^*rs^*$ is non-zero if and only if either q is a prefix of r (i.e. $r = qt$ for some directed (possibly empty) path t, in which case $pq^*rs^* = pts^*$), or else r is a prefix of q (i.e. $q = rt$ for some directed (possibly empty) path t, in which case $pq^*rs^* = p(st)^*$). The non-zero idempotents are of the form $pp^*$ for some (possibly empty) directed path p, and $pp^* \ge qq^*$ in the natural partial order on $I(\varGamma )$ if and only if $q = pt$ for some directed (possibly empty) path t. Thus the vertices of $\varGamma$ are the maximal idempotents in the natural partial order on $I(\varGamma )$.

If $\varGamma = R_1$ is the graph with one vertex and one directed edge, then $I({\varGamma })$ is the bicyclic monoid with a (removable) zero. We refer to this graph $R_1$ as a circle. If $\varGamma = R_n$ is the bouquet (or rose) of $n > 1$ circles (i.e. the graph with one vertex and n directed edges), then $I({\varGamma })$ is isomorphic to the polycyclic monoid $P_n$. This is the inverse monoid generated (as an inverse monoid) by a set A with $|A| = n$ subject to the defining relations $a^{-1}a = 1$ and $a^{-1}b = 0$ for all $a,b \in A$ with $b \ne a$. (Here we regard A as the set of directed edges of $R_n$. In fact it is sometimes convenient to denote $R_n$ by $R_A$ where A is a set with $|A| = n$ if we need to identify the edges of $R_n$). The monoid $P_n$ was introduced by Nivat and Perrot [13] as the syntactic monoid of the “correct parenthesis” language with n sets of parentheses. It was rediscovered in the operator algebra literature where it is referred to as the Cuntz monoid, used in the construction of the Cuntz algebra ${\mathcal {O}}_{n}$ (see Paterson’s book [14] for details). The algebra L(1, n) constructed from the graph $R_n$ in the original paper by Leavitt [10] is what is now referred to as the Leavitt path algebra of this graph (see [1] for details about Leavitt path algebras).

In Sect. 2 we study the relationship between the graph inverse semigroups $I({\tilde{\varGamma }})$ and $I(\varGamma )$ when there is a directed cover or directed immersion $f : {\tilde{\varGamma }} \rightarrow \varGamma$. In this case the map f induces homomorphisms between corresponding local submonoids of the graph inverse semigroups (Theorem 3). We prove a structural property of finite directed covers of a bouquet of circles (Theorem 5). Section 3 is concerned with groups naturally associated with graph inverse semigroups. We examine the universal group of a graph inverse semigroup and provide a topological description of the universal groups of its local submonoids (Theorems 10 and 14). In Sect. 4 we determine necessary and sufficient conditions for a quotient of a graph inverse semigroup $I(\varGamma )$ to be another graph inverse semigroup (Theorem 17) and as a consequence we show that the quotient graph inverse semigroup is a retract of $I(\varGamma )$ (Corollary 19).

2 Directed covers and directed immersions

A morphism from the (directed) graph ${\tilde{\varGamma }}$ to the (directed) graph $\varGamma$ is a function $f : {\tilde{\varGamma }} \rightarrow \varGamma$ that takes vertices to vertices and edges to edges, and preserves incidence and orientation of edges; that is, $f(s({\tilde{e}})) = s(f({\tilde{e}}))$ and $f(r({\tilde{e}})) = r(f({\tilde{e}}))$ for all ${\tilde{e}} \in {\tilde{\varGamma }}^1$. (Here we abuse notation slightly by using the same symbol f to denote the corresponding function that takes vertices to vertices and the function that takes edges to edges.) We extend the notation by defining $f({\tilde{e}}^*) = f({\tilde{e}})^*$ for all ${\tilde{e}} \in {\tilde{\varGamma }}^1$ and $f({\tilde{e}}_1{\tilde{e}}_2\ldots {\tilde{e}}_n) = f({\tilde{e}}_1)f({\tilde{e}}_2)\ldots f({\tilde{e}}_n)$ for each path ${\tilde{p}} = {\tilde{e}}_1{\tilde{e}}_2\ldots {\tilde{e}}_n$. In fact we will often use the notation $f({\tilde{p}}) = p$ to denote the image of a path ${\tilde{p}} = {\tilde{e}}_1{\tilde{e}}_2\ldots {\tilde{e}}_n$ in ${\tilde{\varGamma }}$, where it is understood that p is the path $p = e_1e_2\ldots e_n$ in $\varGamma$ and $e_i = f({\tilde{e}}_i)$.

A morphism $f : {\tilde{\varGamma }} \rightarrow \varGamma$ between directed graphs induces maps $f_{{\tilde{v}}} : s^{-1}({\tilde{v}}) \rightarrow s^{-1}(f({\tilde{v}}))$ in the obvious way. We say that f is a directed cover if the induced maps $f_{{\tilde{v}}}$ are bijections for each ${\tilde{v}} \in {\tilde{\varGamma }}^0$ and that f is a directed immersion if the induced maps $f_{{\tilde{v}}}$ are injections for each ${\tilde{v}} \in {\tilde{\varGamma }}^0$.

This is closely related to the classical notion of covers and immersions of graphs in Stallings’ paper [15], the distinction being that Stallings defines f to be a cover if the induced maps $f_{{\tilde{v}}} : s^{-1}({\tilde{v}}) \cup r^{-1}({\tilde{v}}) \rightarrow s^{-1}(f({\tilde{v}})) \cup r^{-1}(f({\tilde{v}}))$ are bijections for each ${\tilde{v}} \in {\tilde{\varGamma }}^0$ and f is an immersion if these induced maps $f_{{\tilde{v}}}$ are injections for each ${\tilde{v}} \in {\tilde{\varGamma }}^0$.

There is a significant difference between directed immersions (or directed covers) of graphs and immersions (or covers) of graphs in the classical sense. Connected covers of a connected graph $\varGamma$ are classified via conjugacy classes of subgroups of the fundamental group $\pi _1(\varGamma )$ of the graph (see [5] or [15]). For example, connected covers of the circle $R_1$ are classified via subgroups of ${\mathbb {Z}}$. This yields the circuits $C_n$ with n edges (the finite covers of $R_1$) and the universal cover of $R_1$ (the Cayley graph of ${\mathbb {Z}}$ relative to the usual presentation ${\mathbb {Z}} = Gp \langle a : \emptyset \rangle$). The only connected immersions into $R_1$ are the connected covers and the connected subgraphs of the universal cover. However, the description of directed covers and directed immersions into $R_1$ is somewhat more complicated. It is obvious that a graph $\varGamma$ admits a directed immersion to $R_1$ if and only if every vertex of $\varGamma$ has out-degree at most 1. It is routine to show that connected components of such a graph have at most one sink and at most one non-trivial cycle (up to cyclic conjugates). We omit the relatively straightforward description of these graphs since we will not need this description in the present paper. A detailed description of such graphs may be found in our forthcoming paper [11].

If f is a graph morphism from ${\tilde{\varGamma }}$ to $\varGamma$ with $f({\tilde{v}}) = s(p)$ for some path p in $\varGamma$ and some vertex ${\tilde{v}}$ in ${\tilde{\varGamma }}$, then we say that p lifts to ${\tilde{v}}$ if there is a path ${\tilde{p}}$ in ${\tilde{\varGamma }}$ with $f({\tilde{p}}) = p$ and $s({\tilde{p}}) = {\tilde{v}}$. Note that directed paths must lift to directed paths if they lift, by the definition of a graph morphism. It is well-known and easy to prove that if $f : {\tilde{\varGamma }} \rightarrow \varGamma$ is a covering map between graphs, then every path in $\varGamma$ starting at a vertex v lifts to a path at ${\tilde{v}}$ for every vertex ${\tilde{v}} \in f^{-1}(v)$. This is a very special case of the path lifting theorem in topology. See Hatcher’s book [5] for details. The following easy lemma is the analogous version of this for directed paths in directed graphs.

Lemma 1

(Path lifting lemma for directed covers) A graph morphism $f: {\tilde{\varGamma }} \rightarrow \varGamma$ is a directed cover if and only if, for every vertex $v \in \varGamma ^0$ and every vertex ${\tilde{v}} \in f^{-1}(v)$, every directed path p in $\varGamma$ with $s(p) = v$ lifts to a unique path ${\tilde{p}}$ with $s({\tilde{p}}) = {\tilde{v}}$.

Proof

If f is a directed cover and e is an edge in $\varGamma$ with $s(e) = v$ then by the definition of a directed cover, there is a unique edge ${\tilde{e}}$ in ${\tilde{\varGamma }}$ with $f({\tilde{e}}) = e$ and $s({\tilde{e}}) = {\tilde{v}}$. This is the basis for an easy inductive proof that directed paths starting at v lift uniquely to directed paths starting at ${\tilde{v}}$. The proof of the converse statement is equally straightforward.

The directed path lifting lemma above does not hold for directed immersions that are not directed covers in general, but it is easy to see that maximum initial segments of directed paths in $\varGamma$ lift uniquely to directed paths in ${\tilde{\varGamma }}$, as described in the following lemma, the proof of which is a simple adaptation of the proof of Lemma 1. The analogous observation for immersions between graphs may be found in [4].

Lemma 2

(Path lifting lemma for directed immersions) Let $f: {\tilde{\varGamma }} \rightarrow \varGamma$ be a directed immersion between graphs, let v be a vertex of $f({\tilde{\varGamma }})$ and let p be a directed path in $\varGamma$ with $s(p) = v$. Then for every vertex ${\tilde{v}} \in f^{-1}(v)$ there is a unique (possibly empty) maximum initial segment $p_1$ of p that lifts to a directed path at ${\tilde{v}}$. Furthermore, the lift of $p_1$ at ${\tilde{v}}$ is unique.

For each vertex v of a graph $\varGamma$, let $vI(\varGamma )v$ be the local submonoid of $I(\varGamma )$ with identity v. Since $vpq^*v = 0$ if $pq^*$ is not a circuit at v it follows that the non-zero elements of $vI(\varGamma )v$ are the circuits of the form $pq^*$ where p and q are directed (possibly empty) paths with $r(p) = r(q)$ and $s(p) = s(q) = v$. Clearly $vI(\varGamma )v$ is non-trivial (i.e. does not consist of just v and 0) if and only if v is not a sink in the graph $\varGamma$ since if e is an edge of $\varGamma$ with $s(e) = v$, then $ee^* \in vI(\varGamma )v$ and $ee^* \ne v$.

Recall our convention that if $f : S \rightarrow T$ is a homomorphism between inverse semigroups then $f(0_S) = 0_T$. The homomorphism f is called a 0-restricted homomorphism from S to T if in addition $f^{-1}(0_T) = \{0_S\}$. We call a function $f : S \rightarrow T$ a 0-morphism if $f(0_S) = 0_T$ and $f(st) = f(s)f(t)$ if $st \ne 0$ and we say that it is a 0-restricted morphism if in addition $f^{-1}(0_T) = \{0_S\}$. Note that a homomorphism from S to T is a 0-morphism, but not every 0-morphism is a homomorphism since we may have non-zero elements $s,t \in S$ with $st = 0$ but $f(s)f(t) \ne 0$. For example, let S be the three-element semilattice $S = \{e_1,e_2,0\}$ where $e_1$ and $e_2$ are idempotents with $e_1e_2 = 0$ and let T be the two-element semilattice $T = \{1,0\}$. The function $f : S \rightarrow T$ that takes $e_1$ and $e_2$ to 1 and 0 to 0 is a 0-morphism that is not a homomorphism. In general, it is clear that a function $f : S \rightarrow T$ is a homomorphism if and only if it is a 0-morphism with the property that $f(s)f(t) = 0$ if $st = 0$.

A graph morphism $f :{\tilde{\varGamma }} \rightarrow \varGamma$ induces a natural function (which we denote by $f_*$) from $I({\tilde{\varGamma }})$ to $I(\varGamma )$ in the obvious way. This induced function $f_*$ maps 0 to 0 and maps a nonzero element ${\tilde{p}}{\tilde{q}}^*$ of $I({\tilde{\varGamma }})$ to $pq^*$ (where $f({\tilde{p}}) = p$ and $f({\tilde{q}}) = q$). By the definition of a graph morphism it is clear that $pq^*$ is a non-zero element of $I(\varGamma )$ if and only if ${\tilde{p}}{\tilde{q}}^*$ is a non-zero element of ${\tilde{\varGamma }}$ since $r(p) = r(q)$ if and only if $r({\tilde{p}}) = r({\tilde{q}})$. The induced function $f_*$ is well-defined by the uniqueness of canonical forms for elements of $I({\tilde{\varGamma }})$ but it is not in general a homomorphism: in fact by Theorem 20 of [12] it is a homomorphism if and only if the graph morphism $f :{\tilde{\varGamma }} \rightarrow \varGamma$ is injective. However, we have the following fact.

Theorem 3

Let$f : {\tilde{\varGamma }} \rightarrow \varGamma$ be a morphism of graphs with $f({\tilde{v}}) = v$ for vertices ${\tilde{v}} \in {\tilde{\varGamma }}$ and $v \in \varGamma$. Then the following hold.

• (a) $f_*$ is a 0-restricted morphism from $I({\tilde{\varGamma }})$ to $I(\varGamma )$.

• (b) $f_*$ induces a 0-restricted morphism of ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ into $vI(\varGamma )v$ for all vertices ${\tilde{v}}$ of ${\tilde{\varGamma }}$.

• (c) f is a directed immersion if and only if the 0-morphisms from ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ into $vI(\varGamma )v$ induced by $f_*$ are all injective homomorphisms (i.e. embeddings).

• (d) f is a directed cover if and only if the induced embeddings from ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ to $vI(\varGamma )v$ are all full embeddings: that is, the image of ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ is a full inverse submonoid of $vI(\varGamma )v$ for all vertices ${\tilde{v}}$ of ${\tilde{\varGamma }}$.

Proof

(a) Suppose that ${\tilde{p}}{\tilde{q}}^*$ and ${\tilde{p}}'{\tilde{q}}'^*$ are non-zero elements of $I({\tilde{\varGamma }})$ and denote their images under $f_*$ by $pq^*$ and $p'q'^*$ respectively. If ${\tilde{p}}{\tilde{q}}^*{\tilde{p}}'({\tilde{q}}')^*$ is non-zero in $I({\tilde{\varGamma }})$, then from the multiplication of canonical forms in graph inverse semigroups we either have ${\tilde{q}}$ is a prefix of ${\tilde{p}}'$ or ${\tilde{p}}'$ is a prefix of ${\tilde{q}}$. This easily implies that either q is a prefix of $p'$ or $p'$ is a prefix of q. From this and the definition of the multiplication of canonical forms it is easy to see that the induced map $f_*$ is a 0-morphism. It is in fact a 0-restricted morphism since $f_*({\tilde{p}}{\tilde{q}}^*) \ne 0$ if ${\tilde{p}}{\tilde{q}}^* \ne 0$.

(b) If ${\tilde{p}}{\tilde{q}}^*$ is a non-zero element of ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ then clearly $pq^*$ is a non-zero element of $vI(\varGamma )v$. It follows from part (a) that the restriction of $f_*$ to ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ is a 0-restricted morphism to $vI(\varGamma )v$.

(c) Now suppose that f is a directed immersion from ${\tilde{\varGamma }}$ to $\varGamma$ and let $f({\tilde{v}}) = v$. Let ${\tilde{p}}{\tilde{q}}^*$ and ${\tilde{p}}'{\tilde{q}}'^*$ be non-zero elements of ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ and denote their images under $f_*$ by $pq^*$ and $p'q'^*$ respectively. Suppose that ${\tilde{p}}{\tilde{q}}^*{\tilde{p}}'({\tilde{q}}')^* = 0$ in $I({\tilde{\varGamma }})$. Then ${\tilde{q}}$ is not a prefix of ${\tilde{p}}'$ and ${\tilde{p}}'$ is not a prefix of ${\tilde{q}}$. Hence we may write ${\tilde{q}} = {\tilde{e}}_1\ldots {\tilde{e}}_k{\tilde{e}}_{k+1}\ldots {\tilde{e}}_n$ and ${\tilde{p}}' = {\tilde{e}}_1\ldots {\tilde{e}}_k{\tilde{e}}'_{k+1}\ldots {\tilde{e}}'_m$ for some edges ${\tilde{e}}_i$ and ${\tilde{e}}'_j$ in ${\tilde{\varGamma }}$ with $s({\tilde{e}}_1) = {\tilde{v}}$ and ${\tilde{e}}_{k+1} \ne {\tilde{e}}'_{k+1}$. (We allow for the possibility that the common prefix ${\tilde{e}}_1\ldots {\tilde{e}}_k$ of ${\tilde{q}}$ and ${\tilde{p}}'$ might be empty.) It follows that $f_*({\tilde{q}}) = e_1\ldots e_ke_{k+1}\ldots e_n$ and $f_*({\tilde{p}}') = e_1\ldots e_ke'_{k+1}\ldots e'_m$ (where $f({\tilde{e}}_i) = e_i$ and $f({\tilde{e}}'_j) = e'_j$). Then since f is a directed immersion and ${\tilde{e}}_{k+1} \ne {\tilde{e}}'_{k+1}$ it follows that $e_{k+1} \ne e'_{k+1}$, whence q is not a prefix of $p'$ and $p'$ is not a prefix of q. Hence $pq^*p'q'^* = 0$. This implies that the restriction of $f_*$ to ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ is a 0-restricted homomorphism since it is a 0-restricted morphism by part (b).

Conversely, suppose that the restriction of $f_*$ to ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ is a homomorphism for all ${\tilde{v}}$. Suppose that there are two edges ${\tilde{e}}_1$ and ${\tilde{e}}_2$ in ${\tilde{\varGamma }}$ with $s({\tilde{e}}_1) = s({\tilde{e}}_2) = {\tilde{v}}$ and $f({\tilde{e}}_1) = f({\tilde{e}}_2) = e \in \varGamma ^1$. Then ${\tilde{e}}_1{\tilde{e}}_1^* \, , \, {\tilde{e}}_2{\tilde{e}}_2^* \in {\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ and $f_*({\tilde{e}}_1{\tilde{e}}_1^*) = f_*({\tilde{e}}_2{\tilde{e}}_2^*) = ee^* \in vI(\varGamma )v$. If ${\tilde{e}}_1 \ne {\tilde{e}}_2$ then ${\tilde{e}}_1^*{\tilde{e}}_2 = 0$ and so ${\tilde{e}}_1{\tilde{e}}_1^*{\tilde{e}}_2{\tilde{e}}_2^* = 0$. But $f_*({\tilde{e}}_1{\tilde{e}}_1^*{\tilde{e}}_2{\tilde{e}}_2^*) = (ee^*)(ee^*) = ee^* \ne 0$. This violates the assumption that $f_*$ is a homomorphism, and so we must have ${\tilde{e}}_1 = {\tilde{e}}_2$. Hence f is a directed immersion.

Now suppose that f is a directed immersion and $f_*({\tilde{p}}{\tilde{q}}^*) = f_*({\tilde{r}}\tilde{s}^*) = pq^*$ for some non-zero elements ${\tilde{p}}{\tilde{q}}^*$ and ${\tilde{r}}\tilde{s}^*$ of ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$. Since f maps directed edges to directed edges, $f({\tilde{p}}) = p = f({\tilde{r}})$. That is, ${\tilde{p}}$ and ${\tilde{r}}$ are lifts of p at ${\tilde{v}}$. By the “uniqueness” part of Lemma 2, this forces ${\tilde{p}} = {\tilde{r}}$. Similarly we have $f_*({\tilde{q}}^*) = f_*(\tilde{s}^*)$ so $f({\tilde{q}}) = f(\tilde{s})$ and since ${\tilde{q}}$ and $\tilde{s}$ both start at ${\tilde{v}}$ and are both lifts of q this forces ${\tilde{q}} = \tilde{s}$, so ${\tilde{p}}{\tilde{q}}^* = {\tilde{r}}\tilde{s}^*$. Hence $f_*$ is an injective map from ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ to $vI(\varGamma )v$.

(d) Suppose now that f is a directed covering map from ${\tilde{\varGamma }}$ to $\varGamma$, let ${\tilde{v}}$ be a vertex in ${\tilde{\varGamma }}$ and $f({\tilde{v}}) = v$. By part (c), $f_*$ is an injective map from ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ to $vI(\varGamma )v$. From the multiplication in $I(\varGamma )$ it follows that the non-zero idempotents of $I(\varGamma )$ are of the form $pp^*$ for some directed path p starting at v. By Lemma 1, the path p lifts to a unique path ${\tilde{p}}$ at ${\tilde{v}}$ and so $pp^*$ lifts to ${\tilde{p}}{\tilde{p}}^*$, an idempotent of $I({\tilde{\varGamma }})$, so f induces a full embedding of ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ into $vI(\varGamma )v$. Conversely, suppose that $f_*$ induces a full embedding of ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ into $vI(\varGamma )v$. Then if p is a directed path in $\varGamma$ starting at v, the circuit $pp^*$ is an idempotent in $vI(\varGamma )v$, so it is the image under $f_*$ of some idempotent in ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$, which must be of the form ${\tilde{p}}{\tilde{p}}^*$ for some lift ${\tilde{p}}$ of p at ${\tilde{v}}$. Hence all directed paths in $\varGamma$ starting at all vertices $v \in \varGamma ^1$ lift to all preimages ${\tilde{v}} \in f^{-1}(v)$, whence f is a directed covering map by Lemma 1.

We remark that the induced maps from ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ to $vI(\varGamma )v$ are in general not surjective since directed circuits in $\varGamma$ do not necessarily lift to directed circuits in ${\tilde{\varGamma }}$, even when f is a cover. However powers of directed circuits do lift to directed circuits via finite directed covers of $\varGamma$.

Lemma 4

Let $f: {\tilde{\varGamma }} \rightarrow \varGamma$ be a directed cover of finite graphs, let v be a vertex in $f({\tilde{\varGamma }})$ and let p be a directed circuit at v. Then there is a vertex ${\tilde{v}}' \in f^{-1}(v)$ and a positive integer n such that $p^n$ lifts to a directed circuit at ${\tilde{v}}'$.

Proof

Let ${\tilde{v}}$ be any vertex in $f^{-1}(v)$. By the directed path lifting lemma (Lemma 1), p lifts to a directed path ${\tilde{p}}_1$ from ${\tilde{v}}$ to some vertex ${\tilde{v}}_1$. Then $f({\tilde{v}}_1) = v$ so again p lifts to a directed path ${\tilde{p}}_2$ from ${\tilde{v}}_1$ to some vertex ${\tilde{v}}_2$. Continue like this to obtain a sequence of lifted paths ${\tilde{p}}_i$ from ${\tilde{v}}_{i-1}$ to ${\tilde{v}}_i$. By finiteness of ${\tilde{\varGamma }}$ we must have ${\tilde{v}}_i = {\tilde{v}}_{i+n}$ for some $n > 0$ and $i \ge 1$. Then $p^n$ lifts to the directed circuit ${\tilde{p}}_{i+1}\ldots {\tilde{p}}_{i+n}$ at ${\tilde{v}}' = {\tilde{v}}_i$.

Theorem 5

Let $f : {\tilde{\varGamma }} \rightarrow R_A$ be a finite directed cover of the bouquet of $|A| = n$ circles, where $A = \{a_1,a_2,\ldots ,a_n\}$ denotes the set of loops in $R_A$. Then for every vertex ${\tilde{v}}$ in ${\tilde{\varGamma }}$, ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ contains a submonoid isomorphic to the polycyclic monoid $P_A$ if $|A| > 1$, and ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ contains a submonoid isomorphic to the bicyclic monoid if $|A| = 1$.

Proof

For each $a_i \in A$ let $V_{a_{i}}$ be the set of vertices $\tilde{w}$ in ${\tilde{\varGamma }}$ that lie on a non-trivial cycle ${\tilde{e}}_1\ldots {\tilde{e}}_s$ such that $s({\tilde{e}}_1) = \tilde{w}$ and $f({\tilde{e}}_1) = a_i$. Let $V_m = \bigcap _{i = 1,\ldots ,m}V_{a_i}$ for $m \le n$. We claim that $V_m \ne \emptyset$ and that if ${\tilde{v}}$ is any vertex in ${\tilde{\varGamma }}$ and ${\tilde{e}}'$ is any edge with $s({\tilde{e}}') = {\tilde{v}}$, then there is a directed path ${\tilde{p}} = {\tilde{e}}'{\tilde{e}}'_2\ldots {\tilde{e}}'_t$ from ${\tilde{v}}$ to some vertex ${\tilde{v}}'_1 \in V_m$. By the proof of Lemma 4, some power of the loop $a_1$ lifts to a directed path ${\tilde{p}}'$ starting at $r({\tilde{e}}')$ and ending at a vertex in $V_1$, so the directed path ${\tilde{e}}'{\tilde{p}}'$ leads from ${\tilde{v}}$ to a vertex in $V_1$, and hence the claim is true if $m = 1$. Assume inductively that it is true if $m = k$. Let ${\tilde{v}}$ be any vertex in ${\tilde{\varGamma }}$, ${\tilde{e}}'$ an edge starting at ${\tilde{v}}$, and let ${\tilde{e}}_1'$ be the (unique) edge in ${\tilde{\varGamma }}$ with $s({\tilde{e}}_1') = r({\tilde{e}}')$ and $f({\tilde{e}}_1') = a_{k+1}$. By the induction assumption, ${\tilde{e}}_1'$ can be extended to some directed path ${\tilde{p}}_0$ from ${\tilde{v}}_0 = r({\tilde{e}}'_1)$ to a vertex ${\tilde{v}}_1 \in V_k$. But then again by the induction hypothesis there is a directed path ${\tilde{p}}_1$ from ${\tilde{v}}_1$ to some vertex ${\tilde{v}}_2 \in V_k$ whose first edge projects by f to $a_{k+1}$. Continue in this fashion to obtain a sequence of directed paths ${\tilde{p}}_1,{\tilde{p}}_2,\ldots, {\tilde{p}}_i,\ldots$ whose first edge projects onto $a_{k+1}$ and with ${\tilde{v}}_i = s({\tilde{p}}_i) \in V_k$ for all $i \ge 1$. By finiteness of ${\tilde{\varGamma }}$ there must be a directed circuit ${\tilde{p}}_i{\tilde{p}}_{i+1}\ldots {\tilde{p}}_j$ based at ${\tilde{v}}_i$ for some $i < j$. If the first edge of ${\tilde{p}}_i$ is a loop at ${\tilde{v}}_{i}$ (that projects onto $a_{k+1}$) then ${\tilde{v}}_{i} \in V_{k+1}$. So assume this is not the case. Choosing i and j minimal, we may assume that this circuit ${\tilde{p}}_i{\tilde{p}}_{i+1}\ldots {\tilde{p}}_j$ is a cycle. But then since the first edge of ${\tilde{p}}_{i}$ projects onto $a_{k+1}$ we see that in fact ${\tilde{v}}_i \in V_{k+1}$. The claim then follows by induction on k.

Thus for every vertex ${\tilde{v}}$ in ${\tilde{\varGamma }}$ there is a directed path ${\tilde{p}}$ from ${\tilde{v}}$ to some vertex $\tilde{w} \in V_n$. For each $a \in A$, denote by ${\tilde{q}}_a$ a cycle at $\tilde{w}$ whose first edge projects onto the edge a in $R_A$. Then we see that the paths ${\tilde{r}}_a = {\tilde{p}}{\tilde{q}}_a{\tilde{p}}^*$ are in ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ for all $a \in A$. From the relations in $I(\varGamma )$ it easily follows that ${\tilde{r}}_a^*{\tilde{r}}_a = {\tilde{p}}{\tilde{p}}^*$ and ${\tilde{r}}_a^*{\tilde{r}}_b = 0$ if $a \ne b$, so the inverse subsemigroup of ${\tilde{v}}I({\tilde{\varGamma }}){\tilde{v}}$ generated by the elements ${\tilde{r}}_a$ (for $a \in A)$ is a homomorphic image of the copy of the polycyclic monoid $P_A$ with identity ${\tilde{p}}{\tilde{p}}^*$ (provided $|A| > 1$). Since the polycyclic monoid is congruence free (see [8]) it follows that this monoid is isomorphic to $P_A$. A similar argument yields a copy of the bicyclic monoid if $|A| = 1$.

Remarks

• (a) The conclusion of Theorem 5 is in general false if ${\tilde{\varGamma }}$ is an infinite directed cover of $R_A$. For example, if ${\tilde{\varGamma }}$ is the universal cover of the circle $R_1$ and ${\tilde{v}}$ is any vertex of ${\tilde{\varGamma }}$, then no power of the loop in $R_1$ lifts to a circuit at ${\tilde{v}}$ and $I({\tilde{\varGamma }})$ does not contain a copy of the bicyclic monoid.

• (b) The conclusion of Theorem 5 also fails if f is a directed immersion that is not a directed cover. For example, if ${\tilde{\varGamma }}$ is the graph with two vertices ${\tilde{v}}_1$ and ${\tilde{v}}_2$ and one directed edge ${\tilde{e}}$ from ${\tilde{v}}_1$ to ${\tilde{v}}_2$, then there is a directed immersion of ${\tilde{\varGamma }}$ into the circle $R_1$, but $I({\tilde{\varGamma }})$ is finite and so does not contain a copy of the bicyclic monoid.

• (c) It is not true in general that if ${\tilde{\varGamma }}$ is a finite directed cover of $\varGamma$, then $I(\varGamma )$ embeds in $I(\tilde{\varGamma )}$. For example, let $\varGamma$ be the graph with two vertices v and w and two edges a and b from v to w, and let ${\tilde{\varGamma }}$ be graph with three vertices, $v_1,w_1$ and $w_2$ and two edges, namely $a_1$ from $v_1$ to $w_1$ and $b_1$ from $v_1$ to $w_2$. Then the map that sends $v_1$ to $v, \, w_i$ to $w, \, a_1$ to a and $b_1$ to b is a directed cover but $I(\varGamma )$ does not embed in $I(\tilde{\varGamma )}$. Thus Theorem 5 is specific to finite directed covers of a graph $R_A$.

3 Universal groups

Recall that if S and T are inverse semigroups with 0, then a function $\theta : S \rightarrow T$ is called a 0-morphism if $\theta (0) = 0$ and $\theta (st) = \theta (s)\theta (t)$ if $st \ne 0$. We define the universal group ${\mathcal {U}}(S)$ of an inverse semigroup S with 0 to be the group generated by the set $S^*= S \setminus \{0\}$ of non-zero elements of S subject to the relations $s \cdot t = st$ if $st \ne 0$. Equivalently ([9]), ${\mathcal {U}}(S)$ may be defined (up to isomorphism) by the following universal property. Namely, ${\mathcal {U}}(S)$ is the group with the property that there is a 0-morphism $\tau _S : S \rightarrow {\mathcal {U}}(S)^0$ such that if $\alpha : S \rightarrow H^0$ is a 0-morphism from S to a group H with 0 adjoined, then there exists a unique 0-restricted homomorphism $\beta : \mathcal {U}(S)^0 \rightarrow H^0$ such that $\beta \circ \tau _S = \alpha$. We say that S is strongly $E^*$-unitary if the 0-morphism $\tau _S$ is idempotent-pure, that is $\tau _S^{-1}(1_{{\mathcal {U}}(S)})$ is the set of non-zero idempotents of S. Lawson shows in [9] that graph inverse semigroups are strongly $E^*$-unitary.

A homomorphism $\phi : S \rightarrow T$ between inverse semigroups is called idempotent-pure if, for every idempotent a in T, $\phi ^{-1}(a)$ is a semilattice (i.e. every preimage of an idempotent of T is an idempotent of S). An inverse monoid S is called factorizable if for all $a \in S$ there is an element b in the group of units of S such that $a \le b$.

Proposition 6

Let S and T be inverse semigroups with zero and $\phi$ a 0-restricted homomorphism from S to T. Then

• (a) $\phi$ induces a homomorphism $\phi _{\mathcal {U}}$ from ${\mathcal {U}}(S)$ to ${\mathcal {U}}(T)$ such that the following diagram commutes;

  

• (b) $\phi _{\mathcal {U}}$ is surjective if $\phi$ is surjective;

• (c) If $\phi _{\mathcal {U}}$ is injective and S is strongly $E^*$-unitary, then $\phi$ is idempotent-pure;

• (d) If S is factorizable and T is strongly $E^*$-unitary, then $\phi _{\mathcal {U}}$ is injective if $\phi$ is idempotent-pure.

Proof

Since $\phi$ is 0-restricted it follows that $\tau _T \circ \phi$ is a 0-morphism from S to ${\mathcal {U}}(T)$. Hence by the universal property of ${\mathcal {U}}(S)$, there is a unique homomorphism $\phi _{\mathcal {U}}$ from ${\mathcal {U}}(S)$ to ${\mathcal {U}}(T)$ such that $\phi _{\mathcal {U}}(\tau _S(a)) = \tau _T(\phi (a))$ for all $a \in S^*$. Since $\tau _S$ maps $S^*$ onto the generators of ${\mathcal {U}}(S)$ and $\tau _T$ maps $T^*$ onto the generators of ${\mathcal {U}}(T)$, it follows that $\phi _{\mathcal {U}}$ is surjective if $\phi$ is surjective.

Suppose that $\phi _{\mathcal {U}}$ is injective and S is strongly $E^*$-unitary. If $\phi (a)$ is an idempotent of T then $\tau _T(\phi (a)) = \phi _{\mathcal {U}}(\tau _S(a))$ is the identity of ${\mathcal {U}}(T)$. Hence a is an idempotent of S, and so $\phi$ is idempotent-pure.

Now suppose that S is factorizable and T is strongly $E^*$-unitary and that $\phi$ is idempotent-pure. Note that if S is factorizable, then for every element $a \in S^*$, there exists an element $a'$ in the group of units of S such that $a = e a'$ for some idempotent e. Hence, $\tau _S(a) = \tau _S(a')$. It follows that, if $a, b \in S^*$, then $\tau _S(a) \tau _S(b) = \tau _S(a') \tau _S(b') = \tau _S(a'b')$. So every element of ${\mathcal {U}}(S)$ is of the form $\tau _S(a)$ for some element a in the group of units of S. If $\phi _{\mathcal {U}}(\tau _S(a)) = \phi (\tau _T(a))$ is the identity of ${\mathcal {U}}(T)$ then since $\phi$ and $\tau _T$ are both idempotent-pure it follows that a is the identity of S, and so $\tau _S(a)$ is the identity of ${\mathcal {U}}(S)$, whence $\phi _{\mathcal {U}}$ is injective.

Remarks

• (1) The converse of part (b) of Proposition 6 is false in general. For example, let S be the two element semilattice $S = \{e,0\}$ and let T be the three element semilattice $T = \{e,f,0\}$ with $ef = 0$. Then ${\mathcal {U}}(S) \cong {\mathcal {U}}(T)$ is the trivial group but the obvious embedding of S into T is a homomorphism that is not surjective.

• (2) The converse of part (c) of Proposition 6 is also false in general. For example, let $S = SIM(a,b)$, the symmetric inverse monoid on two letters, and let $T = SIM(a,b,c)$, the symmetric inverse monoid on three letters. The identity map on S extends in the obvious way to an idempotent-pure homomorphism $\phi : S \rightarrow T$. By Example 2.1 in [9], S is strongly $E^*$-unitary with maximal group image ${\mathcal {U}}(S) \cong {{\mathbb {Z}}}_2$, the cyclic group of order 2, while ${\mathcal {U}}(T)$ is the trivial group. The homomorphism $\phi _{\mathcal {U}}$ is not injective.

The following fact is implicit in Lawson’s paper [9]. We provide a proof for completeness.

Theorem 7

For any graph $\varGamma$, the universal group $\mathcal {U}(I(\varGamma ))$ is isomorphic to $FG(\varGamma ^1)$, the free group on $\varGamma ^1$.

Proof

First recall that the non-zero elements of $\varGamma$ consists of all elements of form $pq^*$ where p, q are directed paths satisfying $r(p) = r(q)$. For each edge $e \in \varGamma ^1$ define $\tau (e) = e$, regarded as a generator for $FG(\varGamma ^1)$ and define $\tau (e^*) = e^{-1} \in FG(\varGamma ^1)$. By the uniqueness of the canonical form for non-zero elements of $I(\varGamma )$, this extends in the obvious way to a well-defined function $\tau : I(\varGamma ) \rightarrow FG(\varGamma ^1)^0$ with $\tau (0) = 0$ and $\tau (pq^*) = \text{ red }(pq^{-1})$, the reduced form of $pq^{-1}$, if $r(p) = r(q)$. For any $p_1 q_1^*, p_2 q_2^*\in I(\varGamma )^*$, $(p_1 q_1^*) (p_2 q_2^*) \in I(\varGamma )^*$ if and only if either $q_1$ is a prefix of $p_2$ or $p_2$ is a prefix of $q_1$. In either case, it is routine to see that $\tau ((p_1 q_1^*) (p_2 q_2^*)) = \tau (p_1 q_1^*) \tau (p_2 q_2^*)$. That is to say, $\tau$ is a 0-morphism. Now for any group H and any 0-morphism $\alpha : I(\varGamma ) \rightarrow H^0$, we easily see that $\alpha (e^*) = \alpha (e)^{-1}$ for every $e \in \varGamma ^1$. Since $FG(\varGamma ^1)$ is freely generated by the elements $e \in \varGamma ^1$, the map $e \mapsto \alpha (e)$ for $e \in \varGamma ^1$ extends to a unique homomorphism $\beta : FG(\varGamma ^1) \rightarrow H$ and clearly $\alpha = \beta \circ \tau$. Hence $FG(\varGamma ^1) \cong {\mathcal {U}}(I(\varGamma ))$.

Corollary 8

If $\varDelta$ is a subgraph of $\varGamma$ then ${\mathcal {U}}(I(\varDelta ))$ is a free factor of ${\mathcal {U}}(I(\varGamma ))$.

Proof

Clearly the set of edges of $\varDelta$ is a subset of the set of edges of $\varGamma$, so the result is immediate from Theorem 7.

We turn to a description of the universal groups of the local submonoids in $I(\varGamma )$. The non-zero idempotents of $I(\varGamma )$ are of the form $pp^*$ where p is a directed path in $\varGamma$. We denote by ${\mathcal {U}}(\varGamma ,pp^*)$ the universal group of the local submonoid $pp^*I(\varGamma )pp^*$. In particular, when p is the trivial path at the vertex v, ${\mathcal {U}}(\varGamma ,v)$ denotes the universal group of the local submonoid $vI(\varGamma )v$. Recall that the non-zero elements of the local submonoid $vI(\varGamma )v$ are of the form $pq^*$ where p and q are directed (or empty) paths with $s(p) = s(q) = v$ and $r(p) = r(q)$.

Let $V_v = \{w \in \varGamma ^0 :$ there is a (possibly empty) directed path p in $\varGamma$ from v to $w\}$ and let $\varGamma _v$ denote the subgraph of $\varGamma$ induced by the vertices in $V_v$. A subtree T of $\varGamma _v$ is called a directed tree at v if T contains the vertex v and every geodesic path in T from v to some other vertex w in T is directed. T is called a directed spanning tree of $\varGamma _v$ at v if T is a directed tree at v that contains all of the vertices of $\varGamma _v$.

Lemma 9

Let v be a vertex of a graph $\varGamma$ and let T be a directed subtree of $\varGamma _v$ containing the vertex v. Then T extends to a directed spanning tree $T_v$ of $\varGamma _v$.

Proof

The proof of this is a straightforward application of Zorn’s Lemma. Let $\mathcal T$ be the set of all subtrees $T'$ of $\varGamma _v$ such that $T'$ contains the tree T and $T'$ is directed at v. Then $\mathcal T$ is a partially ordered set with respect to inclusion (i.e. $T_1 \le T_2$ if and only if $T_1$ is a subtree of $T_2$). It is easy to see that the union of a chain of trees in $\mathcal T$ is another tree in $\mathcal T$, so by Zorn’s Lemma $\mathcal T$ has a maximal element $T_v$. If $T_v$ is not a spanning tree of $\varGamma _v$, then there is some vertex w of $\varGamma _v$ that is not in $T_v$. Since there is a directed path in $\varGamma _v$ from v to w, there is some directed path p that starts at a vertex $w'$ in $T_v$ and ends at w and has no edge or vertex other than $w'$ in $T_v$. Then $T_v \cup \{p\}$ is a tree strictly containing $T_v$ as a subtree. If $p'$ is the geodesic path in $T_v$ from v to $w'$, then $p'p$ is the geodesic path in $T_v \cup \{p\}$ from v to w and $p'p$ is directed, so $T_v \cup \{p\} \in \mathcal T$. This contradicts the maximality of $T_v$, so $T_v$ is a directed spanning tree at v.

Theorem 10

If v is a vertex of a graph $\varGamma$ then ${\mathcal {U}}(\varGamma ,v) \cong \pi _1(\varGamma _v,v)$.

Proof

It follows from Lemma 9 (with $T = \{v\}$) that $\varGamma _v$ has a directed spanning tree $T_v$ at v. Denote the geodesic path in $T_v$ from v to a vertex w in $\varGamma _v$ by $p_w$. Thus each path $p_w$ is a directed path from v to w. The group $\pi _1(\varGamma _v,v)$ is generated by the homotopy classes [c(e)] of circuits of the form $c(e) = p_{s(e)}ep_{r(e)}^*$ for each edge e of $\varGamma _v$ that is not in $T_v$ (see [15] or [5] for basic information about homotopy of graphs). We claim that the set $S_v$ consisting of these circuits, together with $\{0\}$ and the circuits of the form $pp^*$, for p a directed path in $T_v$ starting at v, generates the local submonoid $vI(\varGamma )v$ as an inverse submonoid of $I(\varGamma )$.

To see this, suppose first that w is a vertex in $\varGamma _v$, $q' = e'_1e'_2\ldots e'_m$ is the geodesic path in $T_v$ from v to w and $p = e_1e_2\ldots e_n$ is any other directed path from v to w. We prove by induction on n that $pq'^*$ can be expressed as a product of elements in $S_v$ and their inverses. The result is clearly true if $p = q'$ or if $n = 0$ so assume $p \ne q'$ and $n \ge 1$. If $n = 1$ then $e_1 \ne q'$ and so $e_1$ is not an edge in $T_v$. So in this case $pq'^* = c(e_1) \in S_v$. So assume that $n > 1$ and that the result is true for all directed paths p of length less than n from v to some vertex w in $\varGamma _v$. Since $p \ne q'$ we may write $p = e_1e_2\ldots e_je'_ie'_{i+1}\ldots e'_m$ for some $j \le n$ and $e_j \ne e'_{i-1}$. (We allow for the case that $e'_i\ldots e'_m$ is empty). Let $p_1$ be the geodesic in $T_v$ from v to $s(e_j)$. By the induction assumption, the circuit $e_1e_2\ldots e_{j-1}p_1^*$ can be written as a product of elements of $S_v$ and their inverses. Also $p_1e_j(e'_1\ldots e'_{i-1})^* = c(e_j)$, so $e_1\ldots e_{j-1}e_j(e'_1\ldots e'_{i-1})^* = e_1\ldots e_{j-1}p_1^*p_1e_j(e'_1\ldots e'_{i-1})^*$ is a product of elements in $S_v$ and their inverses. But then $pq'^* = (e_1\ldots e_j(e'_1\ldots e'_{i-1})^*)(q'q'^*)$ is a product of elements of $S_v$ and their inverses. Now let w be any vertex in $\varGamma _v$ and p, q any directed paths from v to w in $\varGamma _v$. Let $q'$ be the geodesic in $T_v$ from v to w. Then by the argument above, the circuits $pq'^*$ and $qq'^*$ can be written as products of elements in $S_v$ and their inverses. It follows that the circuit $pq^* = (pq'^*)(q'q^*)$ is in the inverse submonoid of $I(\varGamma )$ generated by $S_v$. So $vI(\varGamma )v$ is generated as an inverse monoid by the elements of $S_v$.

We now claim that every non-zero element of $vI(\varGamma )v$ can be written uniquely in the form $c(e_1)\ldots c(e_k)pp^*c(e_{k+1})^*\ldots c(e_{k+s})^*$ for some edges $e_i$ in $\varGamma _v$ that are not in $T_v$ and some directed path p in $T_v$ starting at v such that both $p_{r(e_{k})}$ and $p_{r(e_{k+1})}$ are prefixes of p. (We allow for the possibility that either k or s (or both) might be zero). To prove this, we first make three observations.

Observation 1

If p is a directed path in $T_v$ starting at v, e is an edge of $\varGamma _v$ that is not in $T_v$ and $pp^*c(e) \ne 0$, then $pp^*c(e) = c(e)$. To see this, note that if $pp^*c(e) = pp^*p_{s(e)}ep_{r(e)}^* \ne 0$, then p is a prefix of $p_{s(e)}e$ since e is not an edge in $T_v$. Hence p is a prefix of $p_{s(e)}$ (again since e is not an edge in $T_v$). Observation 1 follows easily from this.

Observation 2

If e and f are edges of $\varGamma _v$ that are not in $T_v$ and $c(e)^*c(f) \ne 0$, then $c(e)^*c(f) = p_{r(e)}p_{r(e)}^*$. To see this, note that if $c(e)^*c(f) \ne 0$ then

$$p_{r(e)}e^*p_{s(e)}^*p_{s(f)}fp_{r(f)}^* \ne 0.$$

Since neither e nor f is an edge in $T_v$ it follows that $p_{s(e)}e = p_{s(f)}f$ and so $e = f$. This implies that $c(e)^*c(f) = c(e)^*c(e)$, which easily yields Observation 2.

Observation 3

The set of elements $pp^*$ where p is a directed path in $T_v$ starting at v is a submonoid of $vI(\varGamma )v$. This follows easily since if $p_1p_1^*p_2p_2^* \ne 0$ then either $p_1$ is a prefix of $p_2$ or $p_2$ is a prefix of $p_1$.

It follows from these three observations and the fact that $vI(\varGamma )v$ is generated as an inverse monoid by $S_v$ that every element of $vI(\varGamma )v$ can be written as a product of the form $c(e_1)\ldots c(e_k)pp^*c(e_{k+1})^*\ldots c(e_{k+s})^*$ for some edges $e_i$ in $\varGamma _v$ that are not in $T_v$ and some directed path p in $T_v$ starting at v. If p is a prefix of $p_{r(e_{k})}$ then $p_{r(e_{k})}pp^* = p_{r(e_{k})} = p_{r(e_{k})}p_{r(e_{k})}^*p_{r(e_{k})}$ and similarly if p is a prefix of $p_{r(e_{k+1})}$ then $pp^*p_{r(e_{k+1})} = p_{r(e_{k+1})}p_{r(e_{k+1})}^*p_{r(e_{k+1})}$. So we may assume without loss of generality that both $p_{r(e_{k})}$ and $p_{r(e_{k+1})}$ are prefixes of p, verifying the claim.

Note that if $c(e_1)c(e_{2}) \ne 0$, then either $p_{s(e_2)}e_2$ is a prefix of $p_{r(e_1)}$ or $p_{r(e_1)}$ is a prefix of $p_{s(e_2)}e_2$. Since $e_2$ is not an edge in $T_v$, we must have $p_{r(e_1)}$ is a prefix of $p_{s(e_2)}e_2$. Applying this to all products $c(e_i)c(e_{i+1})$ we see that if $c(e_1)c(e_2)\ldots c(e_k) \ne 0$ then we must have

$$c(e_1)c(e_2)\ldots c(e_k) = p_{s(e_1)}e_1p_{1,2}e_2p_{2,3}e_3\ldots e_kp_{r(e_k)}^*$$

for some directed paths $p_{i,i+1}$ in $T_v$ from $r(e_i)$ to $s(e_{i+1})$. A similar argument applies to $c(e_{k+1})^*\ldots c(e_{k+s})^*$. Hence we have

$$\begin{aligned}&c(e_1)\ldots c(e_k)pp^*c(e_{k+1})^*\ldots c(e_{k+s})^* \\ \quad =&p_{s(e_1)}e_1p_{1,2}e_2p_{2,3}e_3\ldots e_kp_{r(e_k)}^*pp^*p_{r(e_{k+1})}e_{k+1}^*p_{k+1,k+2}^*e_{k+2}^*\ldots e_{k+s}^*p_{s(e_{k+s})}^* \end{aligned}$$

where the $p_{i,i+1}$ are paths in $T_v$. The uniqueness of canonical forms in $I(\varGamma )$ and the fact that each $e_i$ is not in $T_v$ implies that if

$$\begin{aligned} c(e_1)\ldots c(e_k)pp^*c(e_{k+1})^*\ldots c(e_{k+s})^* = c(e'_1)\ldots c(e'_m)p'p'^*c(e'_{m+1})^*\ldots c(e'_{m+n})^* \end{aligned}$$

then $k = m, s = n, p = p'$ and $e_i = e'_i$ for all i.

For e an edge of $\varGamma _v$ not in $T_v$ define $\theta (c(e)) = [c(e)] \in \pi _1(\varGamma _v,v)$ and also define $\theta (pp^*) = 1$ (the identity of $\pi _1(\varGamma _v,v)$) for p a geodesic path in $T_v$ from v to some vertex $w = r(p)$. By the uniqueness of the expression for non-zero elements of $vI(\varGamma )v$ established above, it follows that $\theta$ extends to a well-defined function (again denoted by $\theta$) from $vI(\varGamma )v$ to $\pi _1(\varGamma _v,v)^0$. A routine argument, using Observations 1, 2 and 3 above, shows that $\theta$ defines a 0-morphism from $vI(\varGamma )v$ to $\pi _1(\varGamma _v,v)^0$. If $\alpha$ is any other 0-morphism from $vI(\varGamma )v$ to $G^0$, for some group G with 0, then since $\pi _1(\varGamma _v,v)$ is freely generated by the $\theta (c(e))$’s we see, as in the proof of Theorem 7, that there is a unique homomorphism $\beta : \pi _1(\varGamma _v,v) \rightarrow G$ that satisfies $\alpha = \beta \circ \tau$. Hence ${\mathcal {U}}(\varGamma ,v) \cong \pi _1(\varGamma _v,v)$.

Corollary 11

If v is a vertex in a graph $\varGamma$ then ${\mathcal {U}}(\varGamma ,v)$ is a free group. If u and v are vertices in the same strongly connected component of $\varGamma$, then ${\mathcal {U}}(\varGamma ,v) \cong {\mathcal {U}}(\varGamma ,u)$. In particular, if $\varGamma$ is a strongly connected graph, then ${\mathcal {U}}(\varGamma ,v) \cong \pi _1(\varGamma ,v)$ is a free group with rank independent of the choice of v.

Proof

Clearly ${\mathcal {U}}(\varGamma ,v)$ is a free group since it is the fundamental group of a graph by Theorem 10. If u and v are in the same strongly connected component of $\varGamma$ then there is a directed path p from u to v and a directed path q from v to u. If w is any vertex in $\varGamma _v$, there is a directed path $p'$ from v to w and hence there is a directed path $pp'$ from u to w, whence w is a vertex in $\varGamma _u$. Hence $\varGamma _v$ is a subgraph of $\varGamma _u$. Similarly $\varGamma _u$ is a subgraph of $\varGamma _v$, so $\varGamma _u = \varGamma _v$. Hence by Theorem 10, ${\mathcal {U}}(\varGamma ,v) \cong \pi _1(\varGamma _v,v) \cong \pi _1(\varGamma _u,u) \cong {\mathcal {U}}(\varGamma ,u)$. The result about strongly connected graphs follows immediately since if $\varGamma$ is strongly connected then $\varGamma _v = \varGamma$.

Corollary 12

If $\varDelta$ is a subgraph of a graph $\varGamma$ and v is a vertex of $\varDelta$, then ${\mathcal {U}}(\varDelta ,v)$ is a free factor of ${\mathcal {U}}(\varGamma ,v)$.

Proof

If there is a directed path in $\varDelta$ from v to some vertex w in $\varDelta$, then the same path lies in $\varGamma$, so $\varDelta _v$ is a subgraph of $\varGamma _v$. Let $T_v$ be a directed spanning tree for $\varDelta _v$ at v. By Lemma 9, $T_v$ can be extended to a directed spanning tree $T'_v$ for $\varGamma _v$ at v. Notice that if e is an edge of $\varDelta _v$ that is not in $T_v$ then it is not in $T'_v$ either. Hence the set of free generators for ${\mathcal {U}}(\varDelta ,v)$ obtained from $T_v$ is contained in the set of free generators for ${\mathcal {U}}(\varGamma ,v)$ obtained from $T'_v$. It follows from Theorem 10 that ${\mathcal {U}}(\varDelta ,v)$ is a free factor of ${\mathcal {U}}(\varGamma ,v)$.

Remarks

We remark that in general if $\varDelta$ is a subgraph of the graph $\varGamma$, then there may be vertices of $\varDelta$ that are in $\varGamma _v$ but not in $\varDelta _v$ since there may be directed paths in $\varGamma$ from v to a vertex in $\varDelta$ but no such directed path in $\varDelta$. Also, while the proof of Corollary 12 shows that every directed spanning tree of $\varDelta _v$ at v may be extended to a directed spanning tree of $\varGamma _v$ at v, it is not necessarily true that every directed spanning tree of $\varGamma _v$ restricts to a directed spanning tree of $\varDelta _v$. This is because in general a geodesic path from v to some other vertex w in $\varDelta$ in a directed spanning tree for $\varGamma _v$ may pass through vertices and edges of $\varGamma \setminus \varDelta$.

Lemma 13

If a and b are $\mathcal D$-related idempotents in an inverse semigroup S with 0, then ${\mathcal {U}}(aSa) \cong {\mathcal {U}}(bSb)$.

Proof

There exists an element $x \in S$ such that $xx^{-1} = a$ and $x^{-1}x = b$. So u is a non-zero element of aSa if and only if $x^{-1}ux$ is a non-zero element of bSb. It follows that the map defined by $u \mapsto x^{-1}ux$ induces an isomorphism from ${\mathcal {U}}(aSa)$ onto ${\mathcal {U}}(bSb)$.

Theorem 14

Let p be a directed path from a vertex v to a vertex w in a graph $\varGamma$. Then

• (a) ${\mathcal {U}}(\varGamma ,pp^*) \cong {\mathcal {U}}(\varGamma ,w)$.

• (b) ${\mathcal {U}}(\varGamma ,w)$ is isomorphic to a free factor of ${\mathcal {U}}(\varGamma ,v)$.

Proof

(a) Note that $pp^* \, \mathcal D \, r(p) = w$ in $I(\varGamma )$ since $p^*p = r(p)$, so the result of part (a) follows immediately from Lemma 13.

(b) If v and w are in the same strongly connected component then the result follows from Corollary 11. So we may assume that there is a directed path from v to w but no directed path from w to v. Let $p = e_1e_2\ldots e_n$ be a directed path from v to w and suppose that k is the largest index such that $s(e_k) \notin \varGamma _w$. That is, there is a directed path from w to $r(e_k)$ but no directed path from w to $s(e_i)$ for $i = 1,\ldots , k$. Clearly every vertex $s(e_i)$ for $i = k+1,\ldots ,n$ is in the same strongly connected component as w, so $\varGamma _w = \varGamma _{s(e_i)}$ for all of these vertices. By Lemma 9, we may choose a directed spanning tree $T_{r(e_k)}$ for $\varGamma _w$ at $r(e_k) = s(e_{k+1})$.

If in the directed path $e_1e_2\ldots e_{k}$ from v to $r(e_k)$ we have $s(e_i) = s(e_j)$ for some $i \ne j$, then we may omit the subpath $e_i\ldots e_{j-i}$ to obtain a shorter directed path $e_1\ldots e_{i-1}e_j\ldots e_{k}$ from v to $r(e_k)$. By omitting all such circuits in the path $e_1\ldots e_{k}$ we obtain a directed geodesic path $p'$ from v to $r(e_k)$ consisting of some of the vertices and edges of the path $e_1\ldots e_{k}$. Let $T'$ be the subgraph of $\varGamma$ consisting of all of the vertices and edges of $\varGamma$ contained in the paths $p'q$, for q a geodesic path in $T_{r(e_k)}$ starting at $r(e_k)$. Since no vertex in $p'$ other than $r(e_k)$ lies in $\varGamma _w = \varGamma _{r(e_k)}$, it follows that $T'$ is a tree with the property that every geodesic path in $T'$ from v to some vertex in $T'$ is directed. Clearly, $T'$ contains all of the vertices in $\varGamma _w = \varGamma _{r(e_k)}$. By Lemma 9 we may extend $T'$ to a directed spanning tree $T_v$ for $\varGamma _v$ at v. If e is an edge in $\varGamma _w$ that is not in $T_{r(e_k)}$, then e is not in $T_v$ either, so the free generators for ${\mathcal {U}}(\varGamma ,r(e_k))$ obtained from the spanning tree $T_{r(e_k)}$ are among the free generators for ${\mathcal {U}}(\varGamma ,v)$ obtained from the spanning tree $T_v$. It follows that ${\mathcal {U}}(\varGamma ,r(e_k))$ is a free factor of ${\mathcal {U}}(\varGamma ,v)$. The result then follows since ${\mathcal {U}}(\varGamma ,r(e_k)) \cong {\mathcal {U}}(\varGamma ,w)$ by Corollary 11.

4 Quotients which are also graph inverse semigroups

Recall that if J is an ideal of an inverse semigroup S, then S/J denotes the Rees quotient of S by the corresponding Rees congruence $\rho _J$, where $a \rho _J b$ if $a = b$ or $a,b \in J$. Rees quotients of graph inverse semigroups are again graph inverse semigroups as described in the following theorem [12, Theorem 7].

Theorem 15

Let J be an ideal of $I(\varGamma )$. Then $I(\varGamma ) / J \cong I(\varDelta )$, where $\varDelta ^0 = \varGamma ^0 \setminus (J \cap \varGamma ^0)$, $\varDelta ^1 = \{e \in \varGamma ^1 : r(e) \not \in J\}$, and the source mapping and range mapping of $\varDelta$ are restrictions of those for $\varGamma$.

Recall that a congruence $\rho$ on an inverse semigroup S with 0 is called 0-restricted if $0 \rho = \{0\}$. Notice that if $\rho$ is an arbitrary congruence on a graph inverse semigroup $I(\varGamma )$ and $J = 0 \rho$, then J is an ideal of $I(\varGamma )$ and $\rho$ induces in the obvious way a 0-restricted congruence on the Rees quotient $I(\varGamma )/J \cong I(\varDelta )$ where $\varDelta$ is the graph constructed in Theorem 15. Thus the discussion of general congruences (other than Rees congruences) on graph inverse semigroups may be reduced to that of 0-restricted congruences on graph inverse semigroups.

For any $v \in {\varGamma }^0$, with out-degree 1 we denote the unique edge in $s^{-1}(v)$ by $e_v$. Let W be a set of vertices with out-degree 1, let ${{\mathbb {Z}}}^+$ be the set of all positive integers and let C(W) be the set of all cycles whose vertices lie in W. Since all vertices in W have out-degree one, any two cycles in C(W) are either disjoint or cyclic conjugates of each other. A cycle function $f : C(W) \rightarrow {{\mathbb {Z}}}^+ \cup \{\infty \}$ is a function that is invariant under cyclic conjugation. A congruence pair (W, f) of $\varGamma$ consists of a subset W of vertices of out-degree 1 and a cycle function f.

Let $\rho$ be a 0-restricted congruence on $I(\varGamma )$ and $W = \{v \in \varGamma ^0 : e e^{*} \, \rho \, v = s(e)\}$. Then all vertices of W have out-degree 1. For $c \in C(W)$, let f(c) be the smallest positive integer m such that $c^m \, \rho \, s(c)$. If no power of c is equivalent to s(c), then we define $f(c) = \infty$. Then $T(\rho ) = (W, f)$ is a congruence pair. Conversely, let (W, f) be a congruence pair of $\varGamma$ and let $\wp (W, f)$ denote the congruence generated by the relation $\mathbf {R}$ consisting of all pairs $(e_v e_v^{*}, v)$ for $v \in W$ and $(c^{f(c)}, s(c))$ for $c \in C(W)$ with $f(c) \in {{\mathbb {Z}}}^+$. Then the following theorem is proved in  [16, Theorem 1.3].

Theorem 16

The mapping T from the set of all 0-restricted congruences on $I(\varGamma )$ to the set of all congruence pairs of $\varGamma$ and the mapping $\wp$ from the set of all congruence pairs of $\varGamma$ to the set of all 0-restricted congruences on $I(\varGamma )$ are inverses. In particular, there exists a one-to-one correspondence between 0-restricted congruences on $I(\varGamma )$ and congruence pairs of $\varGamma$.

Theorem 16 enables us to describe all 0-restricted congruences on a graph inverse semigroup for which the quotient is another graph inverse semigroup.

Theorem 17

Let $\rho$ be a 0-restricted congruence on $I(\varGamma )$ determined by the congruence pair (W, f). Then $I(\varGamma ) / \rho$ is isomorphic to a graph inverse semigroup if and only if

• (1) $W \subseteq \{v \in {\varGamma }^0 : v \text{ has } \text{ out-degree } 1, e_v \text{ is } \text{ a } \text{ loop } \text{ at } v\}$; and

• (2) for any $v \in W$, $f(e_v) = 1$.

Proof

Sufficiency. Suppose that conditions (1) and (2) are satisfied. We proceed to prove that $I(\varGamma ) / \rho$ is isomorphic to the graph inverse semigroup $I(\varDelta )$, where $\varDelta$ is the graph with $\varDelta ^0 = \varGamma ^0$, $\varDelta ^1 = \varGamma ^1 \setminus \{e_v : v \in W \}$, and the source mapping for $\varDelta$ is the restriction of the source mapping for $\varGamma$ and the range mapping for $\varDelta$ is the restriction of the range mapping for $\varGamma$. By conditions (1), (2) and Theorem 16, $\rho$ is generated by all pairs $(e_v e_v^{*}, v)$ and $(e_v, v)$ where $v \in W$. However, in the inverse semigroup $I(\varGamma )$, the relation $(e_v, v) \in \rho$ implies the relation $(e_v e_v^{*}, v) \in \rho$. Hence $\rho$ is generated by all pairs $(e_v,v)$ where $v \in W$. Let $\phi$ be the function that maps a loop $e_v$ of $\varGamma$ at a vertex v in W to the vertex v and fixes all other vertices and edges of $\varGamma$. Then $\phi$ is a function that maps the generators of $I(\varGamma )$ to the generators of $I(\varDelta )$. This function $\phi$ extends to a homomorphism which we again denote by $\phi$ from $I(\varGamma )$ onto $I(\varDelta )$. To see this, note that if $pq^*$ is a non-zero element of $I(\varGamma )$ then $\phi (pq^*) = pq^*$ if neither p nor q contains an edge $e_v$ that is a loop at some vertex $v \in W$. If $pq^*$ does contain such a loop $e_v$ then we must have $p = e_1e_2 \ldots e_ne_v^k$ and $q = f_1f_2\ldots f_m e_v^t$ for some $k, t \ge 0$ (with at least one of k or t greater than 0). Then we see that $\phi (pq^*)$ is obtained from $pq^*$ by removing the path $e_v^k(e_v^*)^t$ at the vertex $r(p) = r(q) = v$. Then from the definition of the multiplication of canonical forms in $I(\varGamma )$ it is easy to see that $\phi$ is a homomorphism from $I(\varGamma )$ onto $I(\varDelta )$. But then since $\rho$ is generated by the pairs $(e_v,v)$ where $e_v$ is a loop at some vertex $v \in W$, it follows that the kernel of $\phi$ is $\rho$ and so the inverse semigroups $I(\varGamma ) / \rho$ and $I(\varDelta )$ are isomorphic.

Necessity. We may assume that W is nonempty or else the congruence $\rho$ determined by the pair (W, f) is the identity congruence. Suppose that $I(\varGamma )/{\rho } \cong I(\varDelta )$ for some graph $\varDelta$.

Recall first that the idempotents of a graph inverse semigroup $I(\varGamma )$ are of the form $pp^*$ for some directed (or possibly empty) path p and that the maximal idempotents in the partial order correspond to the vertices of $\varGamma$ by [12, Lemma 15(3)]. Recall also that in any homomorphism between inverse semigroups, idempotents lift, and so the idempotents of the inverse semigroup $I(\varGamma )/{\rho }$ are of the form $(pp^*) \rho$ for some directed (or possibly empty) path p in $\varGamma$. Suppose that $(pp^*)\rho \ge v\rho$ for some vertex v and directed path p in $\varGamma$. Then $(pp^*v)\rho = (vpp^*)\rho = v\rho$. Since $\rho$ is 0-restricted, $v\rho \ne 0\rho$ and so we must have $s(p) = v$, in which case it follows that $(pp^*)\rho = v\rho$. Hence $v\rho$ is maximal in the partial order in the graph inverse semigroup $I(\varDelta ) \cong I(\varGamma )/{\rho }$, and so we may view $v\rho$ as a vertex of $\varDelta$ for each vertex v of $\varGamma$.

Now suppose that condition (1) fails. Then there exists a vertex v in W such that $s(e_v) = v$ and $r(e_v)v = 0$. We have $e_v^*e_v = r(e_v)$ and $(e_ve_v^*,v) \in \rho$, and so $v\rho \, \mathcal D \, r(e_v)\rho$ in $I(\varGamma )/{\rho }$. But since $\rho$ is 0-restricted, we cannot have $v\rho = r(e_v)\rho$ since $r(e_v) v= 0$ in $I(\varGamma )$. Hence $v\rho$ and $r(e_v)\rho$ are distinct vertices of $\varDelta$ that are ${\mathcal D}$-related in $I(\varDelta ) \cong I(\varGamma )/{\rho }$. This, together with condition (1) of the theorem and Theorem 16, contradicts [12, Corollary 2], and so condition (1) must hold. Then for any vertex $v \in W$ the edge $e_v$ is a loop at v. This implies that $(e_ve_v^*)\rho = (e_v^*e_v)\rho = v\rho$, and so $e_v\rho$ is in the $\mathcal H$-class of the idempotent $v\rho$ in the graph inverse semigroup $I(\varDelta )$. But it is routine to see that if $pq^*qp^* = qp^*pq^*$ in a graph inverse semigroup, then $p = q$ and so $pq^* = pp^*$, and so graph inverse semigroups are combinatorial. From this it follows that $e_v\rho = v\rho$, that is $f(e_v) = 1$. Hence condition (2) must also hold.

Corollary 18

Let $\rho$ be a congruence on $I(\varGamma )$ such that $I(\varGamma ) / \rho$ is isomorphic to a graph inverse semigroup $I(\varDelta ')$ and let $J = 0\rho$. Then $\varDelta '$ is a subgraph of $\varGamma$ with set $\varGamma ^0\setminus (\varGamma ^0 \cap J)$ of vertices. If v is a vertex of $\varDelta '$, then the universal group ${\mathcal {U}}(\varDelta ',v)$ is a free factor of ${\mathcal {U}}(\varGamma ,v)$.

Proof

J is an ideal of $I(\varGamma )$ and $I(\varGamma )/J$ is a graph inverse semigroup $I(\varDelta )$ as described in Theorem 15. Since $\varDelta$ is obtained from $\varGamma$ by omitting some of the vertices and edges of $\varGamma$, we see that $\varDelta$ is a subgraph of $\varGamma$ with $\varDelta ^0 = \varGamma ^0 \setminus (\varGamma ^0 \cap J)$. Furthermore, if $pq^*$ and $p'q'^*$ are non-zero elements of $I(\varGamma )$ that are $\rho$-related, either $pq^*, p'q'^* \in J$ or $(pq^*,p'q'^*) \in \rho '$ where $\rho '$ is the 0-restricted congruence on $I(\varDelta )$ that is the restriction of $\rho$ to $I(\varDelta )$. The quotient $I(\varDelta )/{\rho '}$ is the graph inverse semigroup $I(\varDelta ')$ isomorphic to $I(\varGamma )/{\rho }$ as described in Theorem 17. By the proof of Theorem 17, the graph $\varDelta '$ is obtained from $\varDelta$ by removing the loops at some of the vertices of $\varDelta$, so $\varDelta '$ is a subgraph of $\varDelta$ with the same set of vertices as $\varDelta$. Hence $\varDelta '$ is a subgraph of $\varGamma$ with set $\varGamma ^0\setminus (\varGamma ^0 \cap J)$ of vertices. The description of the universal groups then follows from Corollary 12.

Corollary 19

Let $\rho$ be a congruence on $I(\varGamma )$ such that $I(\varGamma ) / \rho$ is isomorphic to a graph inverse semigroup $I(\varDelta ')$. Then $I(\varDelta ')$ is a retract of $I(\varGamma )$ and ${\mathcal {U}}(I(\varDelta '))$ is a free factor of ${\mathcal {U}}(I(\varGamma ))$.

Proof

From the proof of Corollary 18 we see that $\varDelta '$ is a subgraph of $\varGamma$ so $I(\varDelta ')$ is an inverse subsemigroup of $I(\varGamma )$. Again using the notation of Theorem 17 and Corollary 18, let $\phi$ be the map from $I(\varGamma )$ to $I(\varDelta ')$ defined by $\phi (pq^*) = 0$ if $r(p) \in J$ and $\phi (pe_v^k(e_v^*)^tq^*) = pq^*$ if $r(p) \not \in J, \, v \in W$, $e_v$ is a loop at v and $f(e_v) = 1$. It is routine to check that $\phi$ is a semigroup homomorphism from $I(\varGamma )$ onto $I(\varDelta ')$. Clearly the restriction of $\phi$ to the inverse subsemigroup $I(\varDelta ')$ of $I(\varGamma )$ is the identity map, so $\phi$ is a retraction map and $I(\varDelta ')$ is a retract of $I(\varGamma )$. The fact that ${\mathcal {U}}(I(\varDelta '))$ is a free factor of ${\mathcal {U}}(I(\varGamma ))$ follows from Corollary 8.