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: learning: questions

Topic: Is there a coalgebra formalism for a directed multigraph?

Adittya Chaudhuri (Mar 18 2025 at 12:33):

In the talk ((Co)algebraic analysis of social systems: from graphs to hypergraphs) https://www.youtube.com/watch?v=nnBg4haKyF0, Nina Otter mentioned about representing a directed graph $G=(V, E \subseteq V \times V)$ as a coalgebra of the covariant power set endofunctor $P \colon Set \to Set$ given by $(V, N^{o}_{G} \colon V \to P(V))$, where $N^{o}_{G}$ is the out neighbourhood function. However, I do not see a way to generalise this definition to multigraphs unless (we suitably talk about multisets). Are there any exisiting coalgebra formalisms for multigraphs? Or, am I misunderstanding something fundamentally?

Kevin Carlson (Mar 18 2025 at 15:36):

There are! Ordinary directed multigraphs, i.e. parallel pairs $E\rightrightarrows V,$ form a presheaf category, and all presheaf categories are comonadic over sets, with the forgetful functor given in this case by $E(G)\sqcup V(G),$ the disjoint union of all the elements of the presheaf; the analogous formula works in general. But you mentioned multisets, so maybe this isn't quite the kind of multigraph you mean? Most possibilities are comonadic, if you'd like to pin one down.

Adittya Chaudhuri (Mar 18 2025 at 19:11):

Thanks!! Yes, I meant the ordinary directed multigraph $G=( E \rightrightarrows V)$ only.

I wanted to see explicitly, whether it can be seen as function $\phi (G)\colon X \to T(X)$, for an endofunctor $T \colon Set \to Set$ and a set $X$.

For a directed graph(not a multigraph) $G'=(V', E' \subseteq V' \times V')$, Nina considered $T$ as the covariant power set endofunctor $P \colon Set \to Set$, $X=V'$ and the $\phi(G')$ is the out-neighbourhood function. The function $\phi(G')$ completely determine $G'$.

Now, we are talking about the covariant presheaf $G \colon Sch \to Set$, where $Sch$ is the category freely generated on $E \rightrightarrows V$ ( parallel pairs). Are you saying that for this covariant presheaf $G$ , we have $T=P \colon Set \to Set$, $X= G(V) \sqcup G(E)$ and a function $\phi(G) \colon G(V) \sqcup G(E) \to P(G(V) \sqcup G(E))$ [Need to define $\phi(G)$]

I am new to the formalism of graphs as coalgebras. So, I may sound naive. Sorry for that!

Kevin Carlson (Mar 18 2025 at 20:27):

No, $G(V)\sqcup G(E)$ is the left adjoint of the comonadic adjunction. The right adjoint sends a set $X$ to the chaotic graph $X^3\rightrightarrows X$ which has edges between each $x_1,x_2$ labeled by each $x_3\in X.$ Thus the comonad is carried by the composite endofunctor, $X\mapsto X+X^3.$ A coalgebra structure $X\to X+X^3$ gives a decomposition of $X$ into disjoint pieces that’ll correspond to vertices and edges, and the coalgebra axioms make sure every vertex is mapped to itself and every edge is mapped to itself as an edge between two vertices, producing a well defined graph.

Kevin Carlson (Mar 18 2025 at 20:28):

So the powerset functor doesn’t appear here at all; you can’t describe a directed multigraph in terms of a vertex’s mere set of out-neighbors, nor does an edge have a mere set of adjacent vertices, so it has no role to play.

Kevin Carlson (Mar 18 2025 at 20:29):

This is a special case of Ahman-Uustalu’s theorem that polynomial comonads are the same as small categories, which you can find explained in much more detail in David and Nelson Niu’s book on Poly, if you’re curious.

Adittya Chaudhuri (Mar 18 2025 at 20:30):

Thank you so much!

Jonas Forster (Mar 19 2025 at 17:07):

Another approach would be to use the multiset (or bag) functor $\mathcal{B}\colon Set \to Set$, acting like $\mathcal{P}$, but every element can be contained an arbitrary number of times in each subset, so $\mathcal{B}X$ essentially consists of functions of type $X \to \mathbb{N}$. This is maybe a bit closer in spirit to what happens in the presentation, since this style of coalgebra does usually not involve comonads.

Though this does give you a different notion of graph homomorphism compared to presheaf graphs.

Adittya Chaudhuri (Mar 20 2025 at 02:20):

Thanks!! Yes, I agree. I think we may also think of $\mathcal{B} \colon Set \to Set$ as the free commutative monoid monad i.e. $\mathcal{B}= U \circ \phi$, where $\phi \colon Set \to CommMon$ is the free commutative monoid functor ($X \mapsto \mathbb{N}[X]$) and $U \colon CommMon \to Set$ is the forgetful functor, that takes a commutative monoid to its underlying set. Then, any graph $G=[E \rightrightarrows V]$ can be described as the coalgebra $V \xrightarrow{N^{o}} U(\mathbb{N}[V])$, where the function $N^{o}$ takes a vertex $v$ to the formal linear combination $\alpha_1v_1 + \ldots \alpha_nv_n$ , where $\alpha_1$ is the number of edges from $v$ to $v_1$, $\alpha_2$ is the number of edges from $v$ to $v_2$, and so on.

Kevin Carlson (Mar 20 2025 at 06:35):

This is true-ish, but the categories are far from equivalent, since you can’t permute the edges between two vertices in the multiset picture. Instead a map just becomes a function on vertices which numerically preserves arities everywhere. This kind of graph is sometimes used, although the main near-example I’m aware of is in Petri nets, which are a touch more complicated.

Jonas Forster (Mar 20 2025 at 13:45):

Yep, and this already happens in the original example of $\mathcal{P}$-coalgebras. I would expect a graph homomorphism to preserve edges, but coalgebra homomorphisms preserve and reflect them.

Adittya Chaudhuri (Mar 20 2025 at 14:25):

Thanks. I also felt the presentation is "closer to Petri nets" , but I think for a Petri net $T \rightrightarrows \mathbb{N}[E]$ over the set of entities $E$, we need a function $f \colon T \to U(\mathbb{N}[E]) \times U(\mathbb{N}[E])$ denoting its inputs and outputs. I am not able to guess at the moment how to see $f$ in the form of a colalgebra $X \to \mathbb{B}(X)$ for some endofunctor $\mathbb{B} \colon Set \to Set$, so that coalgebra morphisms become the morphisms of Petri nets.