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: one-hop neighborhood of a category

Bruno Gavranović (Mar 16 2022 at 14:04):

Something I realised I can do with graphs, but not with categories, is to talk about the "one-hop neighbourhood" of a node.

Say I have the graph below. image.png

I can ask "What are the nodes neighbouring $V_1$?". The answer is $(V_0, V_1, V_2, V_3)$ . The node $V_4$ is not a neighbour since it takes two hops to get to $V_4$.

But if I consider this graph as a presentation of a category, then I lose the ability to talk about "one-hop" neighbourhoods. Since $V_0$ is a neighbour of $V_1$ (via $V_1 \xrightarrow{e_0} V_0$) and $V_4$ is a neighbour of $V_0$ (via $V_0 \xrightarrow{e_5} V_4$), then $V_0$ is a "neighbour" of $V_4$ (via the composite $V_1 \xrightarrow{e_0 ; e_5} V_4$. That is, any object is connected to any other object, as long as there is a sequence of morphisms connecting them.

Is it possible to model the idea of one-hop neighborhood with categories? Or do I relinquish this possibility by moving from graphs to categories?

Jules Hedges (Mar 16 2022 at 14:33):

I guess you can recover the graph from its path category: an edge is a morphism that has no non-trivial factorisation

Ralph Sarkis (Mar 16 2022 at 14:46):

I guess this is vaguely related to monoidal width.

Graham Manuell (Mar 16 2022 at 15:33):

Perhaps weighted categories are also relevant here?

Spencer Breiner (Mar 16 2022 at 17:04):

How about this: Write $\N$ for the one object category, and its underlying graph. Any graph $G$ has a canonical homomorphism $G\to\N$ sending every edge to 1. Hitting this with the free/forgetful adjunction, this is the same as a functor $FG\to\N$.

Now if $\mathbf{2}=\{0\to 1\}$ is the "walking arrow", the one-hop paths are represented by the pullback

$$\begin{CD} \bullet @>>> FG\\ @VVV @VVV\\ \mathbf{2} @>>1> \N \end{CD}$$

You can see that this prevents composition of edges by pairing them with the unique arrow in $\mathbf{2}$.

Matteo Capucci (he/him) (Mar 17 2022 at 09:02):

Ralph Sarkis said:

I guess this is vaguely related to monoidal width.

(OT: that paper didn't get the buzz it deserved, it's really cool)

Matteo Capucci (he/him) (Mar 17 2022 at 09:04):

Spencer Breiner said:

How about this: Write $\N$ for the one object category, and its underlying graph. Any graph $G$ has a canonical homomorphism $G\to\N$ sending every edge to 1. Hitting this with the free/forgetful adjunction, this is the same as a functor $FG\to\N$.

Now if $\mathbf{2}=\{0\to 1\}$ is the "walking arrow", the one-hop paths are represented by the pullback

$$\begin{CD} \bullet @>>> FG\\ @VVV @VVV\\ \mathbf{2} @>>1> \N \end{CD}$$

You can see that this prevents composition of edges by pairing them with the unique arrow in $\mathbf{2}$.

This is cool but I guess the interesting thing is to do it when $\mathcal C$ is not free

Matteo Capucci (he/him) (Mar 17 2022 at 09:04):

Which is not far off from this actually...

Matteo Capucci (he/him) (Mar 17 2022 at 09:07):

Since $\mathrm{Cat}$ is monadic over $\mathrm{Graph}$, every small category has a presentation by generators and relations,i.e. for any given small $\mathcal C$ there is a graph $G$ and a quotient map
image.png

Matteo Capucci (he/him) (Mar 17 2022 at 09:14):

Well then I expected something obvious to happen but I don't see it

Fabrizio Genovese (Mar 17 2022 at 12:52):

As some have already said, the problem is "easy" when your category is free. You just take the graph that generates it and talk about neighborhoods there. When C is not free I don't know how to generalize this. Matteo gave a presentation of categories in the universal algebraic sense of "taking a free thing and quotienting it out", but if we start from there I am pretty sure that the graph-theoretic concept of neighborhood won't play nice with the quotienting equations.

Fabrizio Genovese (Mar 17 2022 at 12:54):

For instance, consider the equation $A \xrightarrow{f} B \xrightarrow{g} C = A \xrightarrow{h} C$. Is $C$ a one hop neighbor of $A$ or not? RHS says yes, LHS says no.

Matteo Capucci (he/him) (Mar 17 2022 at 14:10):

indeed

Matteo Capucci (he/him) (Mar 17 2022 at 14:34):

I think it should play somewhat nicely, you'd define the length of a morphism $f$ to be the length of the shortest word of arcs $\vec a = a_1 \ldots a_n$ such that $f =\pi( \vec a)$. This always exists because $\N$ is discrete and bounded below.

Bruno Gavranović (Mar 17 2022 at 21:26):

Thanks for all the answers! Yeah, the general theme seems "yeah, if you have a free category just work with the underlying graph". I suppose that's what my question was: is the right abstraction to talk about one-hop neighbours graphs? I suppose it is, since when we take a free category on a graph we explicitly "complete" the graph by iterating through all the one-hop neighbourhoods. This loses all the distinction of how many hops we did.
Huh, turning things into categories doesn't always help :)

Having learned recently that in the same way one can have a $\mathcal{V}$-category for a suitable $\mathcal V$, one can too have a $\mathcal{V}$-graph.

@bgavran3 @mattecapu "I never realised I can "graph-enrich" and consider not a V-category, but a V-graph." I think I read this in something by Street or Lack or someone. If anyone knows a good reference on V-graphs (sets with an object of the category V for each pair of elements) let me know!

- John Carlos Baez (@johncarlosbaez)

This makes me think that graphs have this extra curious construction that we can do (that we can't do in categories), where for any graph $G$ we can to each node $a:G$ assign a $\mathcal{N}_a$, a set of one-hop neighbours. Perhaps this assembles into a functor $OH : G \to \mathsf{Graph}$ (assuming we can give an appropriate structure to $\mathcal{N}_a$ for each $a:G$?

Bruno Gavranović (Mar 17 2022 at 21:32):

What I mean is, this reminds me of the Yoneda embedding in category theory. We pick a vantage point $A$ and then "look all the places we can go from $A$" by looking at the representable $\mathcal{C}(A, -)$. This feels like a "$n$-hop neighbourhood", for any $n$, since we can reach places from $A$ even if our path is a composite.

In graphs, I'd assume that a Yoneda embedding would look at just 1-hop neighbourhoods, since there's no composition!

Matteo Capucci (he/him) (Mar 17 2022 at 23:01):

mmh this has universal covering vibes to me

Matteo Capucci (he/him) (Mar 17 2022 at 23:02):

like you assemble a graph from all the neighbourhoods, but then you can go on and repeat the same construction, ad infintum... that's how you get the universal cover of a graph

Nathaniel Virgo (Mar 18 2022 at 00:47):

I guess you could define the one-hop neighbourhood of an object following this definition that Jules gave:

Jules Hedges said:

an edge is a morphism that has no non-trivial factorisation

Just define the one-hop neighbourhood of $C$ as the set of objects that can be reached from $C$ by an edge. (Though maybe it makes more sense to define it as the set of edges itself, since there might be more than one edge between the same two objects.)

This works in any category, not just free ones, but it might not always be useful. Consider the reals as a preorder. In that category every non-identity morphism has a non-trivial factorisation, so the one-hop neighbourhood of any object is empty (apart from the object itself, via its identity morphism). But maybe that makes sense.

Matteo Capucci (he/him) (Mar 18 2022 at 00:53):

ha, I bet one can express this kind of irreducibility as initiality (or terminality, i don't remember the direction of arrows) in the [[twisted arrow category]]

Nathaniel Virgo (Mar 18 2022 at 05:59):

It's not really terminality though. It's "an object $E\in \operatorname{Tw}(\mathcal{C})$ such that there is exactly one morphism into $E$". You can only have one terminal object up to iso, but lots of distinct objects can have this property.

Matteo Capucci (he/him) (Mar 18 2022 at 10:38):

oh right, of course