6
$\begingroup$

Given a graph G, and the set of paths in G called PathG.

Is there a monoid structure on PathG? Will concatenation be the multiplication formula? even if it's not defined for some paths?
What about the identity?

$\endgroup$
  • 2
    $\begingroup$ If concatenation is the operation, and it is not defined for some paths, then it cannot be a monoid. $\endgroup$ – M. Vinay Jun 15 '16 at 4:36
8
$\begingroup$

No, in a monoid multiplication is always defined, so $\mathrm{Path}_G$ does not form a monoid under concatenation. However, it does form a category, with an object for each vertex. The set of morphisms between two vertices is then just the set of paths between them, and this works perfectly because you only need to be able to compose morphisms when they are paths that you can concatenate. The identity morphisms are the paths of length $0$ that start at a vertex and then don't go anywhere.

$\endgroup$
8
$\begingroup$

Eric's answer is correct, but there's a lot more to be said here.

Firstly, there's no need to start with a graph for this to work; we can start with an arbitrary digraph. Unfortunately, the term 'digraph' is a little ambiguous, so I prefer to call these things quivers. It basically means 'digraph, possibly with loops, possibly with multiple edges.'

Now to every quiver $X$, we can assign a category $\mathrm{Path}(X)$ as follows: the objects are just $X$-objects, the morphisms are composable sequences of $X$-morphisms, composition is by concatenation of sequences, and identities are empty sequences.

This process is functorial: given a morphism of quivers $$f:X \rightarrow Y,$$ we get a corresponding morphism of categories (i.e. a functor) $$\mathrm{Path}(f) : \mathrm{Path}(X) \rightarrow \mathrm{Path}(Y).$$ In other words, we have a functor $$\mathrm{Path} : \mathbf{Quiv} \rightarrow \mathbf{Cat}.$$ It turns out to be left-adjoint to the underlying quiver functor $\mathbf{Cat} \rightarrow \mathbf{Quiv}.$ This proves that the underlying quiver functor preserves limits, and that $\mathrm{Path}$ preserves colimits.

So the 'category of paths' construction can also be referred to as the 'free category on a quiver' construction.

Now suppose $S$ is a set. Then there's a free monoid on $S$, usually denoted $S^*$. This can be defined as the set of all finite words in the alphabet $S$. But note that $S^*$ isn't just a monoid; its actually an involutive monoid, with involution given by reversal of words. The involution satisfies $$(ab)^\dagger = b^\dagger a^\dagger, \qquad 1^\dagger = 1.$$

Involutive monoids should really be called 'dagger monoids', in my opinion, because there's also monoids equipped with an involution $x \mapsto \overline{x}$ satisfying $$\overline{xy} = \overline{x}\overline{y}, \qquad \overline{1} = 1,$$ and it seems unfair that these aren't 'involutive monoids' under the usual definition.

Anyway, in a similar way, $\mathrm{Path}(X)$ isn't just a category; in fact, its always a dagger category. (This is good terminology!)

Furthermore, $\mathrm{Path}(f)$ plays nice with the dagger structure. Hence, we get a functor $$\mathrm{Path} : \mathbf{Quiv} \rightarrow \mathbf{DagCat}.$$ Be wary: the above functor isn't left-adjoint to the forgetful functor $\mathbf{DagCat} \rightarrow \mathbf{Quiv}$.

Finally, note that $\mathrm{Path}$ generalizes the free monoid construction. It goes like this:

  • given a set $S$, we can build a quiver $\dot{S}$ with one object, and a morphism for each element of $S$.

  • given a monoid $M$, we can build a category $\mathbb{B}M$ with one object, and a morphism for each element of $M$. Composition of morphisms is given by the multiplication operation of $M$; the identity morphism is given by $1_M$.

Its clear that $$\mathrm{Path}(\dot{S}) \cong \mathbb{B}(S^*).$$ Hence, since $\mathbb{B}$ is an embedding of categories, we can write $$S^* \cong \mathbb{B}^{-1}(\mathrm{Path}(\dot{S}))$$ and thereby get free monoids as a special case of the $\mathrm{Path}$ construction.

$\endgroup$
  • 1
    $\begingroup$ One more thing; every category can be made into a semigroup with $0$ by defining that the composite of two morphisms that aren't tip-to-tail is $0$. So you can speak of 'the semigroup of paths in $X$' unambiguously. $\endgroup$ – goblin Jun 15 '16 at 16:22
  • 1
    $\begingroup$ this is very insightful. thanks for introducing me to the Dagger Category. The construction $$S^* \cong \mathbb{B}^{-1}(\mathrm{Path}(\dot{S}))$$ is great, however, it requires $$\dot{S}$$. It's a special case but it's still insightful. I appreciate it $\endgroup$ – Bassam Jun 16 '16 at 17:34
5
$\begingroup$

As explained in Eric wofsey's answer, we can view the graph $G$ as a category with $\mathrm{Path}_G$ as its set of morphisms, and simple concatenation of paths as composition — observe that with this definition, the composition of two paths may not be a path in the usual graph theory sense, but a walk. In this case, we must define $\mathrm{Path}_G$ to include all walks of $G$ and not merely paths, and it is then an infinite set. If we slightly modify the definition of composition, we can restrict $\mathrm{Path}_G$ to contain only proper paths, and obtain a groupoid (rather than a monoid, as the question asks).

A groupoid is neither a special case, nor a generalization of a monoid. It is a generalization of a group (as is a monoid, but in a different direction). The composition in a groupoid is not (necessarily) a binary operation – it is a partial function. Similar to how a monoid can be defined as a category with one object, a groupoid can be defined as a (small) category in which every morphism is an isomorphism. These definitions also make it obvious how exactly a group is a special case of both these concepts – for a group is a one object category (thus a monoid) in which every morphism is an isomorphism (thus a groupoid).

Now, in order to define a groupoid using the paths of a graph, we need to be able to compose two paths and get a proper path (which is possibly smaller than the concatenation of the two). Consider two paths $\alpha$ and $\beta$, from vertex $u$ to vertex $v$, and from $v$ to $w$, respectively. Let the path $\alpha$ be given by $u = u_0, u_1, \ldots, u_m = v$, and similarly, let $\beta$ be $v = v_0, v_1, \ldots, v_n = w$. Let $i \ge 0$ be the least integer for which $u_i = v_j$, for some $j$ between $0$ and $n$. Thus, $u_i = v_j$ is the first vertex of $\alpha$ that is common to the path $\beta$. Define $\alpha \circ \beta$ to be the path $u = u_0, u_1, \ldots, u_i = v_j, v_{j+1}, \ldots, v_m = w$, from $u$ to $w$. Then $\alpha \circ \beta$ has no repeated vertices, and is therefore a proper path from $u$ to $w$. Notice that if $\alpha$ and $\beta$ have no common vertices except for $v$, this composition is merely concatenation. Also, if $u = w$, then $\alpha \circ \beta$ is the "empty" path from $u$ to itself.

Example

Path Composition

Here, $\alpha$ is the path $u = u_0, u_1, u_2, u_3, u_4 = v$, from $u$ to $v$; and $\beta$ is the path $v = v_0, v_1, v_2, v_3, v_4, v_5, v_6 = w$, from $v$ to $w$. The first vertex of $\alpha$ that is common to $\beta$ is $u_2 = v_4$ (so $i = 2$ and $j = 4$, in the definition). Therefore, the composition $\alpha \circ \beta$ is the path $u = u_0, u_1, u_2 = v_4, v_5, v_6 = w$, from $u$ to $w$. It is thus a path of length $4$, whereas $\alpha$ and $\beta$ are paths of length $4$ and $5$, respectively. The concatenation of $\alpha$ and $\beta$, on the other hand, is a walk of length $9$ (one that goes from $u$ to $v$ in four steps, and from $v$ to $w$ in five steps, revisiting the vertices $v_2 = u_3$ and $v_4 = u_2$ on the way).

We can impose a groupoid structure on $\mathrm{Path}_G$ by considering it as a category with vertices for objects, paths for morphisms, and with composition of these morphisms as defined above. This composition is associative, and for each path, there is an inverse path. The inverse of the path $v_0, v_1, \ldots, v_n$ from the vertex $v_0$ to the vertex $v_n$, is the path $v_n, v_{n-1}, \ldots, v_0$ from $v_n$ to $v_0$. The identity morphism of a vertex $u$ is the empty path from $u$ to itself.

In the example above, $\alpha^{-1}$ is the path $v = u_4, u_3, u_2, u_1, u_0 = u$, from $v$ to $u$; and $\beta^{-1}$ is $w = v_6, v_5, \ldots, v_1, v_0 = v$, from $w$ to $v$. Their composition $\beta^{-1} \circ \alpha^{-1}$ is $w = v_6, v_5, v_4 = u_2, u_1, u_0 = u$, from $w$ to $u$ (as $v_4 = u_2$ is the first vertex of $\beta^{-1}$ common to $\alpha^{-1}$). Note that $\beta^{-1} \circ \alpha^{-1} = (\alpha \circ \beta)^{-1}$, as we would expect.

$\endgroup$
  • $\begingroup$ @goblin I've added a correct definition of path composition which does the job. It is the only (meaningful) definition that works if $\mathrm{Path}_G$ is the set of all paths in the usual graph theoretic sense which does not allow repetition of vertices. $\endgroup$ – M. Vinay Jun 16 '16 at 6:00
  • $\begingroup$ That's fine - in fact, that part of the answer is good - but as far as I can tell, you still don't get a groupoid. $\endgroup$ – goblin Jun 16 '16 at 6:05
  • $\begingroup$ @goblin Hm, maybe I'm missing something then. With this definition, the converse path, as you call it is exactly the inverse morphism since the composition of a path and its converse gives the identity (zero) path. So we have a category in which every morphism is an isomorphism, which is exactly what a groupoid is (isn't it?). $\endgroup$ – M. Vinay Jun 16 '16 at 6:28
  • $\begingroup$ That's certainly the correct definition of a groupoid, but the composition of a walk and its converse doesn't give the identity walk. If I walk around $5$ steps, call this $f$, and then go ahead and retrace my steps, then the full journey is $f^\dagger \circ f$ - but this is not the identity journey in which I walk $0$ steps. $\endgroup$ – goblin Jun 16 '16 at 9:55
  • $\begingroup$ Google "dagger category" $\endgroup$ – goblin Jun 16 '16 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.