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: labeled graphs

John Baez (Nov 09 2024 at 21:17):

Here's a question that came up in my research on polarities.

Given a set $L$, let's say an $L$-labeled graph is a graph

$s, t: E \to V$

equipped a map sending edges to elements of $L$:

$\ell: E \to L$

We call $\ell(e)$ the label of the edge $e$.

There's an obvious category $L\mathsf{Gph}$ of $L$-labeled graphs, where the morphisms are graph maps that preserve the labeling of edges. And there's a forgetful functor

$U: L\mathsf{Gph} \to \mathsf{Gph}$

that forgets the labels on edges.

Question. Is this is a fibration, an opfibration, or both?

John Baez (Nov 09 2024 at 21:18):

I think it's both a fibration but not an opfibration.

John Baez (Nov 09 2024 at 21:21):

Maybe a good way to tackle my question is to note that $L\mathsf{Gph}$ is a slice category of $\mathsf{Gph}$: an $L$-labeled graph is a graph over the graph

$s, t : L \to \{\ast\}$

with one vertex and one edge for each element of $L$. Let's call this graph $G_L$, so

$L\mathsf{Gph} \cong \mathsf{Gph}/G_L$

John Baez (Nov 09 2024 at 21:23):

Maybe there are some theorems about when you've got a presheaf topos $\mathsf{C}$ and an object $c \in \mathsf{C}$ then the forgetful functor

$U : \mathsf{C}/c \to \mathsf{C}$

is a fibration, or opfibration, under some conditions. But since I don't know these theorems, I would probably just go in and study whether

$U : \mathsf{Gph}/G_L \to \mathsf{Gph}$

is a fibration, or opfibration, "by hand". There's an obvious candidate for the desired cartesian lifts, and I think cocartesian lifts don't exist.

Damiano Mazza (Nov 09 2024 at 21:38):

Maybe I am missing something, but isn't the forgetful functor $\mathsf C/c\to\mathsf C$ always a discrete fibration, regardless of whether $\mathsf C$ is a topos? It corresponds to the representable presheaf $\mathsf C(-,c)$.

Damiano Mazza (Nov 09 2024 at 21:39):

(But I have no idea whether the functor in question is a bifibration).

Damiano Mazza (Nov 09 2024 at 21:40):

(And I'll go to bed now, so I won't be of any help at all, sorry :-) ).

John Baez (Nov 09 2024 at 21:43):

Thanks! I edited some of my comments to say I think $U : L\mathsf{Gph} \to \mathsf{Gph}$ is not an opfibration. I was confused before.

John Baez (Nov 09 2024 at 21:49):

Okay, I think I understand your argument that the forgetful functor $\mathsf{C}/c \to \mathsf{C}$ is always a discrete fibration. That sounds right! Thanks.

John Baez (Nov 09 2024 at 21:57):

Here's why the forgetful functor from $L$-labeled graphs to graphs can't be an opfibration. I'll show some lift we'd need doesn't exist.

Let our label set $L$ be $\{0,1\}$. Consider this $L$-labeled graph with 3 vertices and 2 edges:

$a \xleftarrow{0} b \xrightarrow{1} c$

Its underlying graph is

$a \leftarrow b \rightarrow c$

There's a unique map from this graph to the terminal graph, which has one vertex $\ast$ and one edge. To lift this map to a map of labeled graphs, we'd need to choose a way to label that one edge. We can label that one edge with either $0$ or $1$, but either way there is no map from

$a \xleftarrow{0} b \xrightarrow{1} c$

to the resulting $L$-labeled graph, since $0 \ne 1$.

Reed Mullanix (Nov 16 2024 at 14:35):

There is an opfibration lurking in the background: $\text{\rm{L-Gph}}$ is a pullback of a much larger 2-sided fibration $\mathrm{LabeledGph}$ living over $\mathrm{Gph} \times \mathrm{Set}$

John Baez (Nov 17 2024 at 00:50):

Thanks! Yes, I get what you mean. In Part 2 I considered graphs with edges labeled by monoids and separately considered 'pulling back along a map of graphs' and 'pushing forward along a map of monoids' (though I didn't say 'pushing forward') there. I should be more explicit about how they're both parts of a 2-sided fibration.

All this can be done equally well using graphs with edges labeled by elements of a set, as in the thread here. The monoid is important for other reasons.

More recently, in Part 5, I discussed both the fibration @Damiano Mazza was discussing and also an opfibration that appears only when we look at finite graphs with edges labeled by a commutative monoid. The latter seems incredibly important in applications to system dynamics (which is what I'm actually studying here).

Kevin Carlson (Nov 17 2024 at 03:14):

I suppose the opfibration will involve summing labels over fibers, right?

John Baez (Nov 17 2024 at 05:33):

Right.

fosco (Nov 17 2024 at 08:09):

Isn't $L{\sf Gph}$ the pullback

$\begin{array}{ccc}L{\sf Gph} &\to&{\sf Set}/L \\\downarrow && \downarrow\\{\sf Gph} &\to&{\sf Set}\end{array}$

where the lower horizontal arrow sends a graph $(E,\_)$ to $E$ and the right vertical is the fibration sending $u : X\to L$ to $X$? Are homomorphisms in $L{\sf Gph}$ different from the ones in the pullback?

John Baez (Nov 17 2024 at 08:19):

I'll answer your two questions with two questions: is an object in the pullback a graph with some edge set $E$ and a map $E \to L$? Is a morphism in the pullback a map of graphs with some map on edges $E \to E'$ and maps $E \to L, E' \to L$ making the resulting triangle commute?

(I think so.)

If so, this indeed my category $L\mathsf{Gph}$.

fosco (Nov 17 2024 at 08:26):

objects, yes, surely.

A morphism in "my" $L{\sf Gph}$ is a graph homomorphism so that the map between sets of edges is a morphism in the slice category as well, so yes.

Then your map is a fibration (it's the pullback of the discrete fibration on the vertical right).

John Baez (Nov 17 2024 at 16:46):

Right! I explained that it's a discrete fibration in Part 5 of my posts on this stuff. But I used a different argument (and I was talking to people who might know only a tiny bit of category theory, so beware).