Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: theory: applied category theory

Topic: Mixed graphs, categorically

David Michael Roberts (Jan 03 2024 at 08:44):

The nLab has a good structural description of both directed and undirected graphs, but not mixed graphs, where you can have both directed and undirected edges. One could take the presheaf point of view and take an appropriate pushout of the two categories whose presheaves are directed and undirected graphs, but I was wondering if something has already appeared in the literature?

Jade Master (Jan 03 2024 at 12:25):

Not sure of a reference, but I think mixed graphs should be presheafs on the category that looks like this:
image.png
(and where the isomorphism $\phi: E' \to E'$ satisfies $s' \circ \phi = t'\circ \phi$)

Jade Master (Jan 03 2024 at 12:27):

But now I understand that this is what you meant by "appropriate pushout...". I hope you like this picture of it.

Matteo Capucci (he/him) (Jan 03 2024 at 20:04):

Do you need to add $\phi^2=1$ or is it automatic? :thinking:

David Michael Roberts (Jan 04 2024 at 02:56):

I suspect it's not automatic. There's nothing that specifies that $\phi^{-1}=\phi$ from that description. (I agree you should have that $\phi$ is an involution - but it might need to also be fixed-point free)

Jade Master (Jan 04 2024 at 16:27):

And now I'm thinking I got the equations wrong as well. We should have $s' \circ \phi = t'$ and $t' \circ \phi = s'$. I don't think it needs to be fixed point free. With the above a equation, an edge can only be a fixed point if it's a loop. If that loop is a fixed point, it's like saying it is its own reversal.

Amar Hadzihasanovic (Jan 04 2024 at 17:04):

I think the idea is that $E'$ should be the set of pairs of an undirected edge and a direction of traversal of the edge, with the involution acting as reversal of direction, in which case it should, indeed, not have fixed points.

Another alternative is to impose that every loop be a fixed point. If you don't impose either of these alternatives, you end up with non-isomorphic representations of the "same" undirected graph.

Amar Hadzihasanovic (Jan 04 2024 at 17:07):

E.g. the graph with a single vertex and a single undirected loop would be represented both by a presheaf with $|E'| = 1$ and $\phi$ equal to the identity, and by one with $|E'| = 2$ and $\phi$ exchanging the two elements, which are non-isomorphic as presheaves.

Amar Hadzihasanovic (Jan 04 2024 at 17:13):

I guess the choice of "no fixed points" vs "all loops are fixed points" depends on whether you want an "undirected loop reversal" to be a trivial or a nontrivial automorphism of a graph :)

Amar Hadzihasanovic (Jan 04 2024 at 17:23):

(One thing to consider is, if you do the standard geometric realisation of an undirected graph, with the representable undirected edge interpreted as the interval $[0,1]$ with $\phi: t \mapsto 1-t$, then "non-fixed-point" loops will be realised as actual loops, whereas "fixed-point loops" will be collapsed to intervals by the imposition that point $t$ be identified with $1-t$, which "folds" the interval onto itself around the midpoint.)

Mike Shulman (Jan 04 2024 at 18:01):

I would make that point rather as: if you "geometrically realize" a presheaf on this category by taking a tensor product of functors with the evident functor $V\mapsto \{\ast\}$ and $E' \mapsto [0,1]$ with the involution being reversal, then the result only agrees with the standard geometric realization of undirected graphs if the latter are represented in the fixed-point-free manner.