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: natural enough transformations of graph homomorphisms

Chad Nester (Mar 30 2021 at 10:12):

I'm currently working with the category $\mathsf{RGraph}$ of reflexive graphs, and I'm wondering if the following phenomenon has a name.

It involves the well-known adjunction $F : \mathsf{RGraph} \dashv \mathsf{Cat} : U$, with $F(G)$ being the category of paths in the graph $G$, and $U(C)$ being the underlying graph of the category $C$.

If I have morphisms $f,g : G \to U(C)$ in $\mathsf{RGraph}$, then I can define a "natural transformation" $\alpha : f \to g$ to consist of a morphism $\alpha_A : f(A) \to g(A)$ in $C$ for each vertex $A$ of $G$, such that for any edge $t : A \to B$ of $G$ we have $\alpha_B\circ f(t) = g(t) \circ \alpha_A$. That is, the definition of natural transformation still works.

Now, applying $F$ to a "natural transformation" like this yields a natural transformation in the usual sense. It feels like this should be a well-known thing that people can tell me lots of facts about, but I don't know what it would be called!

Matteo Capucci (he/him) (Mar 30 2021 at 10:15):

Is this related to the fact that every object in $RGraph$ can be presented as a colimit involving only $\bullet$ and $\bullet \to \bullet$?

Chad Nester (Mar 30 2021 at 10:16):

Very possibly!

Fawzi Hreiki (Mar 30 2021 at 10:47):

It’s worth noting that the forgetful functor from categories to reflexive graphs is monadic, but I’m not sure if that relates to this at all

Fawzi Hreiki (Mar 30 2021 at 10:48):

Are there any other nontrivial examples of categories over which $\text{Cat}$ is monadic?

Amar Hadzihasanovic (Mar 30 2021 at 10:58):

How is that different from a natural transformation between the transpose morphisms $f', g': FG \to C$ in $\mathsf{Cat}$?

Fawzi Hreiki (Mar 30 2021 at 11:01):

It’s not. That’s the idea. You can transport 2-morphism back and forth along an adjunction even if one of the categories is just a 1-category.

Tom Hirschowitz (Mar 30 2021 at 11:30):

It's equivalent, but isn't it different in that the condition on $G \to UC$ is about edges, while the one on $FG \to C$ is about paths? Maybe there is some kind of 2-dimensional adjunction behind this, although reflexive graphs don't seem to form a relevant 2-category. Google doesn't find anything on "sesqui-adjunction"...

Chad Nester (Mar 30 2021 at 13:52):

Indeed, the nice thing is that it's done in terms of the edges of the graph. In particular, my graphs are secretly transition systems, so it's nice to be able to talk about "each transition" instead of "each sequence of transitions".

Mike Shulman (Mar 30 2021 at 14:49):

I don't know of a good general theory of this sort of thing, but it has been noticed before. For instance, in "The geometry of tensor calculus", Joyal and Street proved a universal property for the free monoidal category on a tensor scheme that's similar to this, involving "transformations" between maps from a tensor scheme to the underlying tensor scheme of a monoidal category, even though the category of tensor schemes is itself only a 1-category.

John Baez (Mar 30 2021 at 16:16):

Wow, are you saying $\mathsf{RGraph}$ can be extended from a category to a 2-category, in such a way that the functor between categories $F: \mathsf{RGraph} \to \mathsf{Cat}$ extends to a 2-functor between 2-categories? @Mike Stay would be interested in this.

John Baez (Mar 30 2021 at 16:20):

Is the point that a natural transformation in $\mathsf{Cat}$ between two functors $f, g: \mathsf{C} \to \mathsf{D}$ is the same as a functor $h: \bullet\to\bullet \times \mathsf{C} \to \mathsf{D}$, where $\bullet \to \bullet$ is the "walking arrow" category? So that we can mimic this in $\mathsf{RGraph}$ using the "walking edge" reflexive graph?

John Baez (Mar 30 2021 at 16:21):

(The "walking edge" reflexive graph is the one with two vertices, one edge from the first vertex to the second, and an edge from each vertex to itself.)

Fawzi Hreiki (Mar 30 2021 at 16:31):

Aren’t you just identifying the graphs with the free categories on them? This way the free functor becomes a forgetful functor from free categories to categories.

John Baez (Mar 30 2021 at 18:58):

I was confused; I wasn't paying enough attention to what Chad was doing.

John Baez (Mar 30 2021 at 18:59):

In particular we cannot get a 2-category of reflexive graphs where a 2-morphism between maps of graphs is a map of graphs $h: \bullet \to \bullet \times G \to H$ where $\bullet \to \bullet$ is the "walking edge" reflexive graph.

John Baez (Mar 30 2021 at 19:00):

The problem is we can't compose such 2-morphisms.

John Baez (Mar 30 2021 at 19:01):

I knew that; I somehow momentarily thought Chad had gotten around it. He did it by assuming $H$ was the underlying graph of a category, so we can compose edges in $H$.

John Baez (Mar 30 2021 at 19:01):

I should get back to preparing for my calculus class - first day of class, really busy!!!

Amar Hadzihasanovic (Mar 31 2021 at 00:36):

A relevant thing here seems to be this:

• a natural transformation between functors $FG \to C$ is the same as a functor $I \times FG \to C$ where $I$ is the walking arrow;
• $I$ is the free category on a graph, let's call it $J$ so $I = FJ$;
• there is a monoidal product $-\square -$ on graphs, the box product or (confusingly) the “Cartesian” product, which is taken by $F$ to the “funny” tensor product $-\square -$ of categories, so $F(J \square G) \simeq I \square FG$;
• the cartesian product of two categories is canonically a quotient of their funny tensor product. (In fact $F$ may be oplax monoidal from graphs + box product to categories + cartesian product)

So the natural transformation between two functors $FG \to C$ can be defined as a functor $F(J \square G) \to C$, which is equivalently a morphism of graphs $J \square G \to UC$, satisfying some equations.

Tom Hirschowitz (Mar 31 2021 at 08:32):

This looks nice. Could it be phrased by saying that RGph is enriched over graphs with the box product, and that the adjunction lifts to the enriched world?

John Baez (Mar 31 2021 at 16:04):

Nice work, @Amar Hadzihasanovic!

John Baez (Mar 31 2021 at 16:05):

Your $J$ is what I was calling the "walking edge" reflexive graph.

John Baez (Mar 31 2021 at 16:07):

I really like how you related the box product of graphs to the funny tensor product of categories.

John Baez (Mar 31 2021 at 16:09):

A monoid in Cat with its funny tensor product is called a premonoidal category, and they occur in nature.

Mike Stay (Mar 31 2021 at 16:35):

Tom Hirschowitz said:

This looks nice. Could it be phrased by saying that RGph is enriched over graphs with the box product, and that the adjunction lifts to the enriched world?

There's a topos of (not-necessarily-reflexive) directed multigraphs, the topos of presheaves on the category with two objects and two parallel morphisms between them. The categorical product of two edges $a\to b$ and $c \to d$ is a "diagonal" $(a,c) \to (b, d)$, and the exponential in the topos has nothing to do with graph homomorphisms. However, the category is also symmetric monoidal closed with respect to the box product, an unusual case where a category is symmetric monoidal closed in two different ways. The adjuntion involving the box product gives a notion of exponential graph whose vertices are homomorphisms and whose edges are graph transformations.

When we move to the topos of reflexive directed multigraphs, the categorical product of two edge graphs $a\to b$ and $c \to d$ (which look diagrammatically something like dumbbells because of the canonical self-edges on the vertices) is a box with a diagonal. Each side of the box comes from a use of a canonical self edge. The box makes the exponential graph be the graph of homomorphisms and graph transformations, and the extra diagonal happens to not screw anything up. So here the two symmetric monoidal closed structures coincide.

John Baez (Mar 31 2021 at 16:50):

Mike wrote:

However, the category is also symmetric monoidal closed with respect to the box product, an unusual case where a category is symmetric monoidal closed in two different ways.

I'm not sure how unusual this is. There are some results about this:

• François Foltz, Christian Lair, and G. M. Kelly, Algebraic categories with few monoidal biclosed structures or none, Journal of Pure and Applied Algebra 17 (1980), 171-177.

Here's one of their results: Cat is symmetric monoidal closed in exactly two ways: via the cartesian product, and via the funny tensor product (which is very similar in flavor to the box product).

Amar Hadzihasanovic (Mar 31 2021 at 17:24):

I guess categories of presheaves on a small symmetric monoidal category are always symmetric monoidal closed in two different ways: with the cartesian monoidal structure, and with the Day tensor product. I'm not sure how often these are the only two ways.

John Baez (Mar 31 2021 at 18:14):

Indeed, that's actually a very common situation.

Tom Hirschowitz (Mar 31 2021 at 20:11):

Tom Hirschowitz said:

This looks nice. Could it be phrased by saying that RGph is enriched over graphs with the box product, and that the adjunction lifts to the enriched world?

No.