Re: Monoidal structure on graphs

Re: Monoidal structure on graphs

[John G. Stell]

A structure closely related to the one which Francois Lamarche
asked about appeared in my thesis (1992) [see below] as a simple example of
a sesqui-category which is not a 2-category. I too would expect
it's appeared elsewhere, but I don't know where.

John Stell

\subsubsection{An Example of a Sesqui-Category}
We include an example to show that there are naturally occurring
sesqui-categories other than in connection with modelling
term rewriting. The underlying 
category is {\bf Graph}. Suppose there are graphs $G$ and $H$, and
graph morphisms $g,h : G \rightarrow H$. In this situation, the 2-cells
$\alpha : g \rightarrow h$ are assignments to each node $n$ of $G$ of a
path of edges from $ng$ to $nh$ in $H$. 

The compositions $\circ_R$ and 
$\circ_L$ are readily defined. If $f : F \rightarrow G$ then 
$f \circ_R \alpha$ assigns to a node $m$ of $F$ the path $(mf)\alpha$ in $H$.
For the left composition, suppose we have $k : H \rightarrow K$.
Since $n\alpha$ is a path in $H$, we obtain a path $(n\alpha)k$ by applying
$k$ to each of the edges in the path $n \alpha$. Thus we define 
$\alpha \circ_L k$ to be the assignment to $n$ of the path $(n \alpha)k$.

The vertical composition is the usual concatenation of paths. The identity
2-cells are assignments of zero length paths. 

Monoidal structure on graphs

[Francois Lamarche]

Greetings, fellow categorists.

I'm wondering, if anybody has ever described the following monoidal
structure on the category of oriented multigraphs, what MacLane calls
graphs, the most common kind of graph in category theory (but not
everywhere) :

Given mgs X, Y, the set |X-oY| of vertices on  X-oY  is the set of mg
morphisms
X --> Y.

Given f,g : X --> Y the set of arrows f-->g is the set of pairs
(p_0,p_1) of functions such that

forall  x in |X|, p_0(x) : f-->g

forall  k: x-->y in X, p_1(k) : f(x)-->g(y)

This co-contra bifunctor has a tensor left adjoint, which is symmetric
and monoidal. 

I would be quite surprised if this structure had never been seen before.
Enriched universal algebra in there has applications in computer
science.

Thanks,

Francois Lamarche