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: category theory

Topic: action on presheaves over a graph

Matteo Capucci (he/him) (Oct 18 2022 at 19:43):

Suppose $G=V \overset{s}\rightarrow E \overset{t}\to V$ is a graph, consider $\mathbf{Set}^{G^*}$ where $G^*$ is the free category on $G$.
There is a canonical endomorphism $(-)^1 : \mathbf{Set}^{G^*} \to \mathbf{Set}^{G^*}$ given by 'pushing forward' data along edges.
That is, given $F$, we define on vertices $v \in V$

$$F^1(v) = \sum_{t(e)=v} F(s(e))$$

and on paths $p: v \to w$

$$F^1(p) = \lambda (e, x:F(s(e))) \,.\, (p, F(e)(x))$$

One can show pretty easily this is well-defined on natural transformations too: $\phi^1 (v): F^1(v) \to H^1(v)$ sends $(e,x)$ to $(e, \phi_{s(e)}(x))$.

Now my questions:

1. Does anyone know this construction? It seems pretty natural. (Also, it seems to work for any category $\cal C$, not just graphs).
2. How could I phrase it in purely abstract terms? On the object data, it is given by pull-pushing $\mathrm{el}(F)_0 \to V$ across the span defining $G$. But on arrows?
3. Does it remind you of something known in geometry/topology?

Paolo Capriotti (Oct 18 2022 at 20:26):

Is the sum in the definition of $F^1$ meant to be over paths? If so, I think this is the left Kan extension along $V \to G^*$ of the restriction of $F$ to $V$. In other words, the endofunctor $(-)^1$ is the comonad corresponding to the adjunction between $\mathbf{Set}^V$ and $\mathbf{Set}^{G^*}$ induced by left Kan extension.

Fabrizio Genovese (Oct 18 2022 at 21:01):

It is reminescent of some old papers about doing automata theory with formal power series. I'm sure @fosco will be able to tell you more. In any case yes, it seems like a very natural construction!

Fabrizio Genovese (Oct 18 2022 at 21:01):

And as you say, I'm sure it extends pretty nicely to Petri nets

Fabrizio Genovese (Oct 18 2022 at 21:12):

I'm not sure I can parse correctly the action on paths tho. Are you basically saying that given how you push all the sets forward, you are pushing forward the functions as well?

fosco (Oct 18 2022 at 21:22):

I don't understand the question but I'll get back to this tomorrow, or asap. What paper are you thinking of, @Fabrizio Genovese ?

Fabrizio Genovese (Oct 18 2022 at 21:23):

It was something by Gadducci or Kasangian, I dont' remember

Fabrizio Genovese (Oct 18 2022 at 21:29):

In any case I was thinking that if your functor maps vertexes $v$ to sets of the form $A_v \otimes S_v$ (where $\otimes$ can be either $\times$ or $\sqcup$, for instance), you could apply this construction only on the $S_v$ part. In itself this is not very interesting, but it models the idea that $A$ is 'private information' while $S$ is a 'stack' of messages to send. Operating only on the stack part would give you the dynamics. I was thinking about defining another functor $Set^G \to Set^G$ that, instead, takes $A_v, S_v$ at each vertex and recomputes the stack accordingly, but it seems harder than I expected.

Fabrizio Genovese (Oct 18 2022 at 21:30):

This could be nice as the evolution of a computational system could be described as alternating applications of the dynamic and the computation functor

Fabrizio Genovese (Oct 18 2022 at 21:31):

You could actually try to do this with ordered sets as well, and now your evolution functor would keep track of the order in which the messages are delivered. This gets considerably messier tho, as for instance instead of graphs you need a way to order inbound and outbound edges :confused:

Matteo Capucci (he/him) (Oct 19 2022 at 04:28):

Paolo Capriotti said:

Is the sum in the definition of $F^1$ meant to be over paths? If so, I think this is the left Kan extension along $V \to G^*$ of the restriction of $F$ to $V$. In other words, the endofunctor $(-)^1$ is the comonad corresponding to the adjunction between $\mathbf{Set}^V$ and $\mathbf{Set}^{G^*}$ induced by left Kan extension.

Ha! Beautiful! Spot on, thanks :D

Matteo Capucci (he/him) (Oct 19 2022 at 04:29):

Yes the sum happens over all paths landing at a given node

Matteo Capucci (he/him) (Oct 19 2022 at 04:30):

So given $v$, $F^1(v)$ is the sum of all $F$-data coming from the source of any edge pointing at $v$

Matteo Capucci (he/him) (Oct 19 2022 at 04:31):

Fabrizio Genovese said:

I'm not sure I can parse correctly the action on paths tho. Are you basically saying that given how you push all the sets forward, you are pushing forward the functions as well?

I think that's a good way to put it

Matteo Capucci (he/him) (Oct 19 2022 at 04:32):

Fabrizio Genovese said:

This could be nice as the evolution of a computational system could be described as alternating applications of the dynamic and the computation functor

This is exactly what I'd like to do

Matteo Capucci (he/him) (Oct 19 2022 at 04:33):

Although I don't understand yet if $(-)^1$ also induces a map $F \to F^1$ that pushes sections forward

Fabrizio Genovese (Oct 19 2022 at 12:37):

Matteo Capucci (he/him) said:

Fabrizio Genovese said:

This could be nice as the evolution of a computational system could be described as alternating applications of the dynamic and the computation functor

This is exactly what I'd like to do

The thing that I find hard to justify in this perspective is the need for a presheaf. Tecnically all you need is to map vertexes to sets of states/messages. You don't need necessarily to map the edges to anywhere. Probably this is related to your comment about pushing the sections forward, I'm not sure

Fabrizio Genovese (Oct 19 2022 at 12:39):

Anyway: "You have a stack of incoming messages, you process them sequentially and eventually fill a stack of outgoing messages" is a pretty basic model of network+computation that imho has a lot of gas in the tank. So whatever effort goes in this direction, I'll advocate for that!