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

Topic: Graphs with polarities

John Baez (Apr 02 2025 at 16:01):

@Adittya Chaudhuri and I are writing a paper on "Graphs with polarities", and I thought it would be nice to have our conversations about this paper here. I've always liked doing research in public forums, like blogs. It's a good way to make sure we're not missing big ideas or making dumb mistakes, since people can comment. It's a good way to publicize the research. And for others, it's entertaining to watch - and helpful for students who are just starting research and haven't seen how it's done.

John Baez (Apr 02 2025 at 16:03):

Anyone wanting to get the basic idea of what we'll be discussing can check out my blog series

• Polarities

(This links to part 5, but you can easily click back to earlier articles.)

John Baez (Apr 02 2025 at 16:18):

But I'll just dive in and start talking to @Adittya Chaudhuri.

Any graph $G$ freely generates a category $\textrm{Free}(G)$.
In the paper we talk about graphs whose edges are labeled by elements of a monoid $L$. We show that any such $L$-labeled graph $G$ freely generates a category $\textrm{Free}(G)$ over the one-object category $BL$.

I want to make some expository changes but also I have a more substantial idea.

In terms of exposition, we currently define an $L$-labeled graph to be a graph with a functor $\text{Free}(G) \to BL$. This makes the concept seem too complicated. It's just a graph with edges labeled by elements of $L$. We'd defined graphs with edges labeled by elements of a set in Definition 2.1, so we can just apply that here.

It should be a little proposition, not a definition, that when $L$ is a monoid an $L$-labeled graph gives a functor $\text{Free}(G) \to BL$ (and the $L$-labeled graph can be recovered from this).

I'll make this change - I won't list all the expository changes I want to make; it's quicker just to make them - but I want to emphasize my philosophy: definitions should be simple and easy to understand whenever possible. They should not be impressive, especially in applied category theory where non-category-theorists will be trying to understand them.

Adittya Chaudhuri (Apr 02 2025 at 16:22):

Just to clarify, did you refer to Definition 2.1 as in the current overleaf file?

Adittya Chaudhuri (Apr 02 2025 at 16:23):

(As Defn 2.1 is the definition of $L$-labeled graph).

John Baez (Apr 02 2025 at 16:24):

Yes: that's where we define graphs with edges labeled by elements of a set, and labeling edges by elements of a monoid works the exact same way.

But here's the more substantial idea. We're calling elements of $L$ 'polarities' and using them to describe different ways in which one thing affects another. For example if $L = \{+,-\}$ is the group $\mathbb{Z}/2$, an edge labeled by + means one vertex positively affects another, while an edge labeled by - means one vertex negatively affects another.

But we've seen that the absence of an edge is also a kind of polarity, meaning 'no effect'.

This has been confusing me for a long time, but I think I've figured it out.

Adittya Chaudhuri (Apr 02 2025 at 16:25):

Are you saying about multiplicative monoid of $\mathbb{Z}/3$?

John Baez (Apr 02 2025 at 16:27):

Let me take my time and explain things... it will take a while but it'll become clear.

Adittya Chaudhuri (Apr 02 2025 at 16:27):

Sure.

John Baez (Apr 02 2025 at 16:34):

So, we want a formalism where the absence of an edge is on the same footing as a labeled edge. And I realized such a formalism already exists! If $V$ is a monoidal category people talk about categories enriched in $V$, or $V$-categories for short, which have a set of objects and for each pair of objects $x,y$ an object $\text{hom}(x,y) \in V$, and composition and identity-assigning maps obeying the usual properties.

But some people (who? I've seen it somewhere!) also define $V$-graphs, which are like $V$-categories without the composition and identity-assigning maps. A $V$-graph is just a set of vertices and for each pair of vertices $x,y$ an object $\text{hom}(x,y) \in V$. That's all.

People do this because there's something like a monad on the category of $V$-graphs whose algebras are $V$-categories: the 'free enriched category on an enriched graph' monad.

But if we take $V$ to be a mere monoid, thought of as a monoidal category with only identity morphisms, then a $V$-graph is like a graph with polarities!

If we take $V$ to be the boolean monoid $$\{T,F}$$ then a $V$-graph is just a graph, where $T$ means the presence of an edge and $F$ means the absence of an edge.

But if we take $V$ to be the multiplicative monoid of $\mathbb{Z}/3$, then a $V$-graph is the same as a $L$-labeled graph where $L = \{+,-\}$ - just as you said.

John Baez (Apr 02 2025 at 16:35):

I'm now thinking that $V$-graphs are fundamentally more important than $L$-labeled graphs, in part because they connect so nicely to enriched category theory.

John Baez (Apr 02 2025 at 16:36):

Any monoid $L$ gives a monoid $V$ with an extra element $0$ that's 'absorptive': anything times $0$ is $0$ - and this lets us turn $L$-labeled graphs into $V$-graphs.

John Baez (Apr 02 2025 at 16:37):

However, there are also monoids $V$ that don't have an absorptive element, so the theory of $V$-graphs is strictly more general than the theory of $L$-labeled graphs. I have not thought of any examples of how this could be useful in the study of polarities.

John Baez (Apr 02 2025 at 16:38):

Right now, my reason for getting interested in $V$-graphs is not so much the greater generality, but the fact that it wouldn't be good to be studying a special case of enriched category theory without even noticing it!

John Baez (Apr 02 2025 at 16:39):

Okay, now I'm fired up... I will go to the gym and later today I will start working on the exposition of the paper. (The other reason I like doing research in public is that it's more exciting and it makes me work faster!)

Adittya Chaudhuri (Apr 02 2025 at 16:40):

Thanks !! I am thinking on the perspective of $V$-graphs.

John Baez (Apr 02 2025 at 16:42):

Great! Maybe you can find some aspects of our paper that would be clearer from this perspective. Notice that the 0 in the monoid $V$ is naturally the additive identity when we give $V$ a ring structure. I.e., adding a non-edge to a labeled edge goes nothing to the labeled edge.

John Baez (Apr 02 2025 at 16:43):

Do people think about categories enriched in a ring or rig?

Adittya Chaudhuri (Apr 02 2025 at 16:47):

My question is "why do we need the full rig structure in the hom Set?" Is'nt the commutative monoid structure not sufficient?

Adittya Chaudhuri (Apr 02 2025 at 16:49):

I meant categories enriched in commutative monoids?

John Baez (Apr 02 2025 at 16:51):

I think we're getting a bit mixed up here, since $L$ doesn't need to be a commutative monoid, and we should think of its operation as multiplication, and an $L$-labeled graph gives a $V$-graph where $V = L \cup \{0\}$ is a not necessarily commutative monoid.

The rig structure plays no role in any of this.

It comes later, and I probably shouldn't have mentioned it yet.

Adittya Chaudhuri (Apr 02 2025 at 16:52):

Yes, now I understand your point.

Kevin Carlson (Apr 02 2025 at 17:38):

Ignore me if this is distracting, but I thought of you two sometime in the last couple of weeks when I was doing some $V$-enriched calculation and I found I wanted to understand maps $f:v\to C(a,b)$ for varying $v\in V$ and an enriched category $C.$ I found myself drawing such maps as arrows from $a$ to $b$ labeled by a little $v.$ Also, you can compose such a “$v$-arrow” $f$ with a “$w$-arrow” $g: w\to C(b,c)$ to get a $v\otimes w$-arrow $a\to c$! You just compose $w\otimes f$ with $g$ in $V.$

Kevin Carlson (Apr 02 2025 at 17:41):

So, it feels like there’s some nice functor from $V$-categories into categories labeled by the monoid of objects of $V$, up to truth since the objects of $V$ aren’t quite a monoid in general. Just an idle thought!

Nathanael Arkor (Apr 02 2025 at 17:44):

The concept of a $V$-graded category captures this intuition precisely (every $V$-enriched category induces a $V$-graded category where the $v$-graded morphisms from $a$ to $b$ are given by the morphisms $v \to C(a, b)$). Rory Lucyshyn-Wright's recent paper V-graded categories and V-W-bigraded categories: Functor categories and bifunctors over non-symmetric bases is a nice introduction to these ideas.

Kevin Carlson (Apr 02 2025 at 17:49):

Ah, lovely, I'm glad it's a known thing!

Adittya Chaudhuri (Apr 02 2025 at 18:02):

(deleted)

Adittya Chaudhuri (Apr 02 2025 at 18:08):

One problem is our $V$ is in the form of $[V \rightrightarrows V]$, for a monoid $V$. So, only arrows are identity morphisms.

Adittya Chaudhuri (Apr 02 2025 at 18:11):

An $L$-labeled graph is $[L \leftarrow E \rightrightarrows V]$, which means for every $x,y \in V$ there can multiple labeled edges between $x$ and $y$.

Adittya Chaudhuri (Apr 02 2025 at 18:15):

How the notion of $V$-graph is capturing "labelled multiple edges" between two vertices $x,y$?

Adittya Chaudhuri (Apr 02 2025 at 18:21):

I feel like for a monoid $L$, there should be a functor from the category of $L$-labeled graphs $Gph/G_{L}$ to the category of $( L \cup \lbrace 0 \rbrace)$-graphs.. ? (where $G_{L}$ is the graph with one vertex and an edge for each $l$ in $L$). Of course, to make such an association, we may need additional algebraic structure on $L$ (like a rig..etc.).

Jorge Soto-Andrade (Apr 02 2025 at 18:22):

John Baez said:

Adittya Chaudhuri and I are writing a paper on "Graphs with polarities", and I thought it would be nice to have our conversations about this paper here. I've always liked doing research in public forums, like blogs. It's a good way to make sure we're not missing big ideas or making dumb mistakes, since people can comment. It's a good way to publicize the research. And for others, it's entertaining to watch - and helpful for students who are just starting research and haven't seen how it's done.

Nice idea! A very naive question: isn't this (labeling edges of a graph by elements in a monoid)motivated - among other things - by path integrals in discrete integral calculus in $n$ dimensions? The label associated to an edge from $a$ to $b$ could be the potential difference $V(b) - V(a)$. When integrating, you add the weights associated to the edges which constitute your path. But you may have contexts where it is sensible to multiply those weights... You also have cases where you deal with (directed) graphs whose edges are labelled by linear operators, which you can compose.

Adittya Chaudhuri (Apr 02 2025 at 18:30):

For me, a motivation for multiplication of weight can be from regulatory networks in biological systems (for eg: the paper https://arxiv.org/pdf/2301.01445, where the case $L$= $\mathbb{Z}/2$ is considered), and they are called signed graphs (signed categories): "Say $a$ stimulates $b$ and $b$ is inhibiting $c$, then composing, $a$ is inhibiting $c$.

Adittya Chaudhuri (Apr 02 2025 at 18:33):

However, I think if we consider the multiplicative monoid of the tropical semiring https://ncatlab.org/nlab/show/tropical+semiring, then a product is actually an addition.

Adittya Chaudhuri (Apr 02 2025 at 18:53):

According to the definition of $V$-graph as @John Baez defined above, it seems it is like a monoid valued matrix $M \colon X \times X \to V$ , where $X$ is the set of vertices of the graph, which may be like the "adjacency matrices of such $V$-graphs.. ? I feel like the concept of $R$-matrices in @Jade Master 's thesis https://arxiv.org/pdf/2105.12905 is the quantale analog of $V$-graphs that you defined.

Adittya Chaudhuri (Apr 02 2025 at 18:55):

But, is this notion capturing "multiple labeled edges" like our definition of $L$-labeled graphs i.e objects of the slice category $Gph/G_{L}$?

Adittya Chaudhuri (Apr 02 2025 at 19:24):

However, I completely agree that the absence of edges is nicely captured by $V$-graphs unlike $L$-labeled graphs.

John Baez (Apr 02 2025 at 19:27):

Kevin Carlson said:

So, it feels like there’s some nice functor from $V$-categories into categories labeled by the monoid of objects of $V$, up to truth since the objects of $V$ aren’t quite a monoid in general. Just an idle thought!

Nice! And of course every monoidal category is equivalent to a strict one so you can have a monoid of objects if you want... at the cost of making it obscenely large. (This is probably not a good idea, but you can do it.)

So far in our work on 'polarities' @Adittya Chaudhuri and I are only thinking about the case where $V$ actually is a monoid, i.e. a discrete monoidal category. We haven't thought about 'morphisms between polarities'. But it might be a natural thing to do - we could dip our toe in this water by letting $V$ be a monoidal poset.

John Baez (Apr 02 2025 at 19:37):

Jorge Soto-Andrade said:

A very naive question: isn't this (labeling edges of a graph by elements in a monoid) motivated - among other things - by path integrals in discrete integral calculus in $n$ dimensions? The label associated to an edge from $a$ to $b$ could be the potential difference $V(b) - V(a)$. When integrating, you add the weights associated to the edges which constitute your path. But you may have contexts where it is sensible to multiply those weights... You also have cases where you deal with (directed) graphs whose edges are labelled by linear operators, which you can compose.

We are motivated by work that people are already doing on 'regulatory networks' in biology (as @Adittya Chaudhuri explained) and also 'causal loop diagrams' in the modeling discipline known as System Dynamics. I explained the latter here:

• Polarities (Part 1)

and here is an example:

Causal loop diagram for factory productivity

In all that work, one only considers a monoid of labels. But if your monoid is a rig, you can try to sum labels over all paths from one vertex to another, where the labels for paths are obtained by multiplying labels of edges making up the path... and the summation is where we use a rig. So then we get a discrete path integral, similar to what you're describing.

There are difficulties with this idea as soon as our graph has directed cycles, because then the sum can become infinite. And the graphs usually do have directed cycles, as in the picture above. That's why they're called 'causal loop diagrams': people are interested in studying the 'feedback loops'.

There are ways around these difficulties... but anyway I should be working on the paper!

James Fairbanks (Apr 02 2025 at 23:51):

This sounds cool and I’m interested to see if there’s a connection to the matrix exponential. When the edge weights are real or complex, you can look at the matrix exponential to summarize all paths between a pair of nodes, discounting by length.

John Baez (Apr 03 2025 at 00:07):

There is definitely a connection to the matrix exponential, and yes, the 'discounting by length' implicit in the formula for the exponential is exactly what solves the divergence issue that occurs in a naive 'sum over paths'. I've written a bit about this in a note to myself, and I should figure out a good place to put that writing. I'm not sure this paper is the place! We'll see. Anyway, thanks, you've revived a certain interesting line of thought.

John Baez (Apr 04 2025 at 16:28):

@Adittya Chaudhuri - I'm trying to prove and polish up Proposition 2.3. So people can understand what I'm talking about: we're studying the category of graphs with edges labeled by elements of some set $L$, and we call this category $\mathsf{Gph}/G_L$ because it's equivalent to the category of graphs over $G_L$: the graph with one vertex and one edge for each element of $L$.

I've removed the part of this proposition that's useful for structured cospans, and moved it to the section on structured cospans, where people will understand why we care about this.

So what's left is this:

Proposition. For any set $L$, we have the following:

(a) The category $\mathsf{Gph}/G_L$ is a presheaf topos.

(b) The forgetful functor $U\colon \mathsf{Gph}/G_L \to \mathsf{Gph}$ is a discrete fibration.

(c) The presheaf $P \colon \mathsf{Gph}^{\text{op}} \to \mathsf{Set}$ associated to $U$ is representable by $G_L$.

(d) The category $\mathsf{Gph}/G_L$ is equivalent to the category of elements $\int P$.

John Baez (Apr 04 2025 at 16:34):

All of this should be a special case of completely general facts that show up whenever you have a presheaf category $\widehat{C}$ (here $\mathsf{Gph}$) and an object $x$ in that category (here $G_L$). So I think our proof should say this, and briefly explain the completely general facts, with references to proofs, in a way that people who don't already know them have a chance of understanding.

Here are the general facts, if I understand correctly:

General facts. For any object $x$ in a presheaf category $\widehat{C}$:

(a) The category $\widehat{C}/x$ is a presheaf topos.

(b) The forgetful functor $U\colon \widehat{C}/x \to \widehat{C}$ is a discrete fibration.

(c) The presheaf $P \colon \widehat{\mathsf{C}}^{\text{op}} \to \mathsf{Set}$ associated to $U$ is representable by $x$.

(d) The category $\widehat{\mathsf{C}}/x$ is equivalent to the category of elements $\int_{\widehat{\mathsf{C}}^{\text{op}}} P$.

So, one question is: where are these general facts proved - preferably in a textbook that will help readers understand them?

John Baez (Apr 04 2025 at 16:47):

I also think for (a) it's good to note that

$\widehat{\mathsf{C}}/x \simeq \widehat{\int_{\mathsf{C}} x}$

where $x : \mathsf{C}^{\text{op}} \to \mathsf{Set}$ is our presheaf on $\mathsf{C}$. I think this the usual proof that a slice category of a presheaf category is again a presheaf category. I'm confused about how this is related to fact (d).

Adittya Chaudhuri (Apr 04 2025 at 18:29):

I think (d) should follow from the fact that $P$ is the presheaf associated to $U$(via Grothendieck correspondence). Hence, $\int P$ should be equivalent to $\widehat{C}/x$ by the fact that the category of Presheaves over $\widehat{C}$ is equivalent to the category of discrete fibrations over $\widehat{C}$.

Adittya Chaudhuri (Apr 04 2025 at 18:30):

Or , am I misunderstanding something here?

Adittya Chaudhuri (Apr 04 2025 at 19:00):

(deleted)

John Baez (Apr 04 2025 at 21:03):

I don't follow the logic here:

Hence, $\int P$ should be equivalent to $\widehat{C}/x$ by the fact that the category of presheaves on $\widehat{C}$ is equivalent to the category of discrete fibrations over $\widehat{C}$.

You're probably just skipping some steps, but the part " $\int P$ should be equivalent to $\widehat{C}/x$" mentions $\int P$ and $\widehat{C}/x$, but the reason "by the fact that the category of presheaves on $\widehat{C}$ is equivalent to the category of discrete fibrations over $\widehat{C}$" doesn't mention either of those things.

John Baez (Apr 04 2025 at 21:05):

Another question: where do you plan to use these facts:

(c) The presheaf $P \colon \mathsf{Gph}^{\text{op}} \to \mathsf{Set}$ associated to $U$ is representable by $G_L$.

(d) The category $\mathsf{Gph}/G_L$ is equivalent to the category of elements $\int P$.

?

Adittya Chaudhuri (Apr 04 2025 at 21:49):

John Baez said:

I don't follow the logic here:

Hence, $\int P$ should be equivalent to $\widehat{C}/x$ by the fact that the category of presheaves on $\widehat{C}$ is equivalent to the category of discrete fibrations over $\widehat{C}$.

You're probably just skipping some steps, but the part " $\int P$ should be equivalent to $\widehat{C}/x$" mentions $\int P$ and $\widehat{C}/x$, but the reason "by the fact that the category of presheaves on $\widehat{C}$ is equivalent to the category of discrete fibrations over $\widehat{C}$" doesn't mention either of those things.

Let $Pre(\widehat{C})$ denote the category of presheaves over $\widehat{C}$ and $discfib(\widehat{C})$ denote the category of discrete fibrations over $\widehat{C}$. Since $Pre(\widehat{C})$ is equivalent to $discfib(\widehat{C})$, there is a pair of functors $F \colon discfib(\widehat{C}) \to Pre(\widehat{C})$ and $G \colon Pre(\widehat{C}) \to discfib(\widehat{C})$ such that $F \circ G \cong \rm{id}$ and $G \circ F \cong {\rm{id}}$. However, these $F$ and $G$ arise from the Grothendieck correspondence i.e in our context $F(U)=P$ and $G(P)= \int P \to \widehat{C}$. Hence, $G \circ F(U) \cong U$ translates to $(\int P \to \widehat{C}) \cong U$ as fibrations. Now, from the definition of isomorphism of fibrations, we have $\int P \cong \widehat{C}/x$.

Adittya Chaudhuri (Apr 04 2025 at 22:09):

John Baez said:

Another question: where do you plan to use these facts:

(c) The presheaf $P \colon \mathsf{Gph}^{\text{op}} \to \mathsf{Set}$ associated to $U$ is representable by $G_L$.

(d) The category $\mathsf{Gph}/G_L$ is equivalent to the category of elements $\int P$.

?

The free-forgetful adjunction between $\mathsf{Gph}$ and $\mathsf{Set}$ allows us to define a natural isomorphism between the presheaves $\hom(Free(-),BL)\colon \mathsf{Gph}^{{\rm{op}}} \to \mathsf{Set}$ and $\hom(-,G_L) \colon \mathsf{Gph}^{{\rm{op}}} \to \mathsf{Set}$. Hence, by Grothendieck correspondence, $\int \hom(Free(-),BL) \cong \int \hom(-,G_L)$. However, $\hom(-,G_L)$ is same as $P$, and thus $\int \hom(-,G_L) \cong \int P \cong \mathsf{Gph}/G_{L}$. On the other hand $\int \hom(Free(-),BL)$ is the category of graphs with $L$-valued polarities" as defined in Definition 3.10. Thus the category of graphs with $L$- valued polarities is same as the category of $L$-labeled graphs. I used it in the proof of Theorem 3.12.

John Baez (Apr 05 2025 at 01:20):

Thanks.

Adittya Chaudhuri (Apr 05 2025 at 08:32):

@John Baez and I were discussing about the "stratification" as in the Section 5 of https://arxiv.org/pdf/2211.01290 and its possible way of incorporating it in the framework of graphs with polarities. I was thinking in the following way:

Say we assume "Students influence University in "$i_1,i_2, \ldots i_{n}$ ways". We see it as a graph with two vertices (Students and University) and $n$-number of directed labelled edges from Students to University. Out of these $n$ influences, some are positive and some are negative. We call this graph $G_{aggregate}$. Now consider another graph with two vertex $a,b$ but only two directed edges from $a$ to $b$ labeled by $+1$ and $-1$. We call this graph $G_{Type}$. Now, let us divide the Students into "PhD and Undergrads" and divide the University into "Public and Private". Then, if we construct the corresponding graph, we would obtain (by incorporating the appropriate edges coming from $G_{aggregate}$) a graph which we call $G_{Strata}$. Now, there are two functions $t_{aggregate} \colon G_{aggregate} \to G_{Type}$ and $t_{strata} \colon G_{strata} \to G_{Type}$, which maps Students, PhD, Undergrads to $a$ and University, public, private to $b$, and the positive edges to $+1$ and negative edges to $-1$. Now, we construct the pullback $G_{Strata} \times_{t_{strata}, G_{Type}, t_{aggregate}} G_{aggregate}$ in the category $\mathsf{Gph}/G_{\mathbb{R}}$. We will call the pullback graph $G_{Stratified}$.

However, @John Baez said that "the notion of multiple stratifications" i.e Students into PhD's and Undergads and Universitites into Public and Private may lead to some unwanted errors. He said the standard technique is to do in a "non-multiple" way like "classifying people based on the "age difference" or "sex difference" (Separately) as in the Figure 14 of https://arxiv.org/pdf/2211.01290.

But, I am thinking about this :

Is there a way to incorporate "multiple stratification" in the framework of labeled graphs which can bypass the "errors about which @John Baez mentioned"? I think like this because, for example, $a$ influence $b$ positively and say, $b$ influence $c$ negatively. Now, say based on certain characteristics, $a,b$ and $c$ can be classified into $a_1,a_2$, $b_1,b_2, b_3$, $c_1,c_2$ respectively. Then, shouldn't the concept of multiple stratifications may naturally arise ? Am I missing something?

From the Mathematical point, we are trying to understand how the property "products distribute over colimits in a presheaf topos" translate into the language of "gluing and stratifying labeled graphs/causal loop diagrams".

John Baez (Apr 05 2025 at 21:03):

In the paper A categorical framework for modeling with stock and flow models we explain how to do stratification of models using pullbacks.

If I wanted to do multiple stratifications, like taking a model with students and universities and 1) subdividing students into undergraduates and PhD students and 2) subdividing universities into public and private, I would do one at a time, not both at once. This means doing first one pullback of stock and flow models that involves students, and then another that involves universities.

Of course, taking one pullback and then another is still an example of a limit. So we are still just taking a limit of stock and flow models. But it's less confusing to do it in stages.

Adittya Chaudhuri (Apr 05 2025 at 21:28):

Thanks. I got your point.

Adittya Chaudhuri (Apr 07 2025 at 13:10):

@John Baez I was thinking about an alternative (a bit relaxed) formalism of stratification for labeled graphs, which I am describing below:

For a set $L$, consider a $L$-labeled graph $p \colon G \to G_{L}$. I am defining a stratification of $p \colon G \to G_{L}$ as a functor $Strat_{G} \colon Free(G) \to \mathsf{Rel}$ from the free category on $G$ to the category of relations https://ncatlab.org/nlab/show/Rel.

For every vertex $v$ of $G$, lets call the elements of the set $Strat_{G}(v)$ as the stratification of $v$. Now, I construct a $L$-labeled graph $G_{Strata}$ defined by the following data:

$V(G_{Strata}):= \sqcup_{v \in V} Strat_{G}(v)$

$E(G_{Strata}):=\sqcup_{e \in E} Strat_{G}(e)$

$s_{G_{Strata}} \colon E(G_{Strata}) \to V(G_{Strata}), \big(((x,v), (y,w)), Strat_{G}(e:v \to w) \big) \mapsto (x,v)$, where $x \in Strat_{G}(v)$.

$t_{G_{Strata}} \colon E(G_{Strata}) \to V(G_{Strata}), \big(((x,v), (y,w)), Strat_{G}(e:v \to w) \big) \mapsto (y,w)$, where $y \in Strat_{G}(w)$.

$l_{G_{Strata}} \colon E(G_{Strata}) \to L$, defined as $\big(((x,v), (y,w)), Strat_{G}(e:v \to w) \big) \mapsto l(e)$.

Although to match our intuition (with the kind of stratification discussed in https://arxiv.org/pdf/2211.01290), we may add an extra condition i.e we may define a stratification of $p \colon G \to G_{L}$ as a functor $Strat_{G} \colon Free(G) \to \mathsf{Rel}$ from the free category on $G$ to the category of relations such that for each morphism $\gamma \neq {\rm{id}}$ in $Mor(Free(G))$, we have $Strat_{G}(\gamma)= Strat_{G}(v) \times Strat_{G}(w)$. However, I am illustrating the general case by an example below:

Let us consider a graph with two vertices $x$ and $y$, and an edge $e \colon x \to y$ labeled by the phrase $`help \,\ in \,\, curing'$ by considering it as a graph whose edges are labeled by free monoid on the set of English words. Say, $x$ represents medicines used in treating headache and $y$ represents people with headache. Now, define $Strat_{G} \colon Free(G) \to \mathsf{Rel}$ as follows:
"$x$ maps to the set of all medicines used in curing headaches, and $y$ maps to the set of collection of people with different kinds of allergies. In this case $Strat_{G}(e)= \lbrace \big((x_i, Strat_{G}(x) ), (y_{j}, Strat_{G}(y) ) \big) \colon x_i$ does not cause any allergic effects among people in $y_i \rbrace$. Finally each edge of $Strat_{G}$ is labeled by the phrase '$help\,\, in \,\, curing$'.

Maybe the whole discussion can be simplified/or maybe I am misunderstanding some perspectives.

John Baez (Apr 07 2025 at 16:06):

Can you use this construction to obtain a new labeled graph? The idea of stratification has traditionally been that you start with a model $X$ of some sort (e.g. a labeled graph), and then build a new more complicated model $X'$ that has an epimorphism $X' \to X$.

John Baez (Apr 07 2025 at 17:07):

I'm in touch with an ecologist who has been using causal loop diagrams. These are simply directed graphs with edges labeled by signs) to study ecosystems. They're called 'causal loop diagrams' because people who use them are especially interested in finding feedback loops. This is a standard technique in the field called 'systems ecology'. She wrote this paper about it:

• Using Relational Biology with Loop Analysis to Study the North Atlantic Biological Carbon Pump in a ‘Hybrid’ Non-Algorithmic Manner .

In this paper she introduced what she called "Type II loop analysis":

Loop Analysis for aquatic ecosystems has been used in two ways: (1) construction of hypothetical–intuitive models buttressed by the general knowledge of the investigator and reports of species coexistence and interactions in the literature (Type I). This is not unlike how Systems Ecologists first conceptualize their quantitative models. To date, most applications of LA have been Type I, with 10–12 or fewer nodes, which ignores a great deal of biological realism. Often, a model or set of models is drawn by hand in a ‘back of the envelope’ manner, and the LA calculation is completed to obtain predictions of changes in each node once a parameter input or driving force is assumed to perturb the network at one or more locations. In Type II LA, time series data of species field densities and nutrient concentrations are used to identify nodes and links, and node number is not limited, making larger, more biologically reasonable models possible.

She writes:

Hi Dr. Baez,

I considered your preference in doing Category Theory with decorated cospans a serious challenge.  I came up with a way to decorate the links in my Type II Loop Analysis models for marine plankton ecosystems.  Usually, I translate the quantitative field-lab data into qualitative signs as directed changes (in abundances from one sampling period to the next) in graph nodes that are sets of functional species in an ecological network.   This leaves the networks completely qualitative, and quantitative values are never used again.   However, calculations in the LA methodology allow one to predict how the nodes will change qualitatively when the network is perturbed from the outside (parameter input=PI).  I construct the models and automatically test for all positive and negative PIs to all nodes, then select the simplest model and input node with the best agreement with the data in the 90-100% range.  In the new work, I took the best agreement PI for the 640 individual models (20 years of about 17.5 networks/year for 2 stations)  and listed the paths and complements.  A complement is a set of disjunct loops of nodes not on the path.   Then, I counted how many times each link appeared in the paths, complements, and total (P + C) calculations, so I have individual 640 quantified sets of links x 3 with associated graphs.  A total of 1.36 links were counted for the Halifax station.  I view these values as frequencies of causality in the networks.  I believe this causal structure is more important than just flows of carbon or Kcal of energy, which are the common ways of quantifying ecosystem links.  No two networks repeat over hundreds of networks, but they are about 75% similar.  All networks are ranged around a central lattice containing several hundred species individually arranged in the nodes.  The link frequency values are quite disparate, with the lattice links generally the most common, which was expected.  As an example, I have attached a summary table of the counts and percentages of link frequencies for the summary graph for about 374 individual models for the Halifax station.   (On the attached graph, the asterisks mean the links were present in loop calculations but <1% of all involved links).  

I want to determine if there is a deeper underlying, even emergent, causal structure with Category Theory than summarized by the current set of largely collective network properties usually calculated for signed digraphs.  In addition, is there any way to illustrate the networks are CLEF (closed to efficient causality a la’ Aristotle and a main characteristic of self-organizing living systems).  Robert Rosen demonstrated ‘CLEFness’ with his M-R systems for cells using Category Theory models, and Jan-Hendrik Hofmeyr of Stellenbosch University is currently expanding Rosen’s work.  I think Bob was the first person to use Category Theory in biology in the 1950s in his PH.D. thesis at the University of Chicago and subsequent publications.  He knew the two Category Founders (Professors Eilenberg and MacLane).   I have identified these lattice structures at different locations over 1000 km of ocean.  It appears the upper ocean is a teaming 3D lattice of interactions. The loop models are a main part of my work on ecosystem chimeras-nodes that trade functions mutualistically in networks that individual nodes cannot provide for themselves throughout evolution.  I do not think anything like this (using Category Theory for loop links) has been attempted before at the ecosystem level. 

Thus, my questions are:

1. Are the cospans decorated sufficiently for Category Theory?  Is there something better I could do?
2. Is this a project you would be interested in?  I would be very interested to work with you on it. 

I have also attached two papers I wrote for Mathematics in December, one on Rosen’s approach to algorithms for living systems (he didn’t think they could capture life itself), and one on how I do Type II loop analysis for plankton communities,  which is the most detailed description of the methodology to date.  There is a YouTube video (https://www.youtube.com/watch?v=QFQNTv8lGFw) for a seminar about ecosystem chimeras I did for Michael Levin’s lab at Tufts last week using Loop Analysis.  They make laboratory chimeras at the organism level.

John Baez (Apr 07 2025 at 17:09):

She's a great example of someone who may benefit from wisely done research on graphs with polarities.

Adittya Chaudhuri (Apr 07 2025 at 19:43):

John Baez said:

Can you use this construction to obtain a new labeled graph? The idea of stratification has traditionally been that you start with a model $X$ of some sort (e.g. a labeled graph), and then build a new more complicated model $X'$ that has an epimorphism $X' \to X$.

I think yes. The correspondence about which you asked is
$G \mapsto G_{Strata}$
and the epimorphism that you asked is $\phi \colon G_{strata} \to G$ defined as
$(x,v) \mapsto v$ and
$\big(((x,v), (y,w)), Strat_{G}(e:v \to w) \big) \mapsto e$.

Now, the fact $\phi$ is a morphism of $L$-labeled graphs follows from the construction of the labelling map $l_{G_{Strata}} \colon E(G_{Strata}) \to L$, defined as $\big(((x,v), (y,w)), Strat_{G}(e:v \to w) \big) \mapsto l(e)$.

Here $G_{Strata}$ is more complicated than $G$.

Adittya Chaudhuri (Apr 07 2025 at 19:45):

John Baez said:

She's a great example of someone who may benefit from wisely done research on graphs with polarities.

Definitely!! I agree completely.

Adittya Chaudhuri (Apr 07 2025 at 20:03):

I am going through the Patricia A. Lane's paper that you shared. I had always been super interested in Rosen's approach (especially, anticipatory systems https://link.springer.com/book/10.1007/978-1-4614-1269-4)

James Fairbanks (Apr 08 2025 at 23:12):

Section 3b of this paper also talks about Stratified Models with pullbacks

https://royalsocietypublishing.org/doi/10.1098/rsta.2021.0309

It’s presented there in an elementary way because the audience was modelers, not category theorists. So it might be a helpful presentation for communicating with collaborators.

James Fairbanks (Apr 08 2025 at 23:17):

In some code I wrote for the Regulatory Networks project I computed some pullbacks of signed graphs with Catlab and it did what I expected. You could make stratified models that way too. They would be stratified at the presentation level rather than at the free signed category level.

John Baez (Apr 08 2025 at 23:51):

Yes, that paper seems to be the original "stratification using pullbacks" paper. I should have mentioned it!

John Baez (Apr 09 2025 at 00:11):

@Adittya Chaudhuri - can you try writing something for the proof of Prop. 2.3? The statements are:

If we write $\widehat{C}$ for the category of presheaves on a category $C$, and choose a presheaf $F \in \widehat{C}$, then:

(a) The category $\widehat{C}/F$ is a presheaf topos.
(b) The forgetful functor $U \colon \widehat{C}/F \to \widehat{C}$ is a discrete fibration.
(c) The functor $P \colon \widehat{C}^{\text{op}} \to Set$ associated to $U$ is representable by $F$.
(d) The category $\widehat{C}/F$ is equivalent to the category of elements $\int P$.

We don't really want to prove them: we want to crisply explain them and give references to proofs. If you write something I can try to make it nicer.

John Baez (Apr 09 2025 at 02:43):

Also: I want to make the math section of the paper more focused on topics that will actually help people who study causal loop diagrams. Here's one example:

When $L$ is a monoid, we already discuss the free $L$-labeled category on an $L$-labeled graph $G$. One reason is obvious: this lets us assign labels not just to edges of $G$ but to edge paths (which are the morphisms in the free category on $G$), thus describing 'indirect effects'.

But here's another reason: if we can show $L$-labeled categories are monadic over $L$-labeled graphs, we can define a Kleisli category. This has $L$-labeled graphs as objects, but maps that send an edge in one $L$-labeled graph to a composite of edges in another.

This is a useful notion of morphism. For example we can use one of these morphisms to map

$\text{health} \xrightarrow{+} \text{wealth}$

to

$\text{health} \xrightarrow{+} \text{income} \xrightarrow{+} \text{wealth}$

John Baez (Apr 09 2025 at 02:44):

I think quite often we may want to make a model of a system more complicated in this way: by adding new vertices, and 'factoring' $L$-labeled edges into edge paths!

John Baez (Apr 09 2025 at 02:46):

So I have a question:

Question. It's widely known that reflexive graphs are monadic over sets, and categories are monadic over reflexive graphs. Are categories monadic over graphs? I.e. is $\mathsf{Cat}$ monadic over $\mathsf{Gph}$ where $\mathsf{Gph}$ is the category of presheaves on the category

$\bullet \stackrel{\to}{\to} \bullet$?

John Baez (Apr 09 2025 at 02:47):

I think it is....

John Baez (Apr 09 2025 at 03:55):

If true, I feel it must be true that $L$-labeled categories are monadic over $L$-labeled graphs when $L$ is a monoid. Then we can set up the Kleisli category I mentioned, and know it really is a Kleisli category.

I believe you can define a Kleisli-like category starting with any adjunction $L : C \to D$, $R: D \to C$. The objects are objects $c \in C$, the morphisms from $c$ to $c'$ are morphisms $c \to R L c'$, and we compose $f: c \to RL c'$ and $g: c' \to RL c''$ by taking $RL g \circ f: c \to RLRLc'$ and following it with $R \epsilon L : RLRLc' \to RLc'$ where $\epsilon$ is the counit.

Question. What good features does this category have when the adjunction is monadic, which it lacks otherwise?

Nathanael Arkor (Apr 09 2025 at 05:45):

John Baez said:

I think it is....

It is (it's easy to check directly).

Nathanael Arkor (Apr 09 2025 at 05:47):

John Baez said:

I believe you can define a Kleisli-like category starting with any adjunction $L : C \to D$, $R: D \to C$. The objects are objects $c \in C$, the morphisms from $c$ to $c'$ are morphisms $c \to R L c'$, and we compose $f: c \to RL c'$ and $g: c' \to RL c''$ by taking $RL g \circ f: c \to RLRLc'$ and following it with $R \epsilon L : RLRLc' \to RLc'$ where $\epsilon$ is the counit.

Question. What good features does this category have when the adjunction is monadic, which it lacks otherwise?

$RL$ is the monad induced by the adjunction, so this is exactly the Kleisli category of the monad. Monadicity is irrelevant.

Adittya Chaudhuri (Apr 09 2025 at 05:57):

John Baez said:

Adittya Chaudhuri - can you try writing something for the proof of Prop. 2.3? The statements are:

If we write $\widehat{C}$ for the category of presheaves on a category $C$, and choose a presheaf $F \in \widehat{C}$, then:

(a) The category $\widehat{C}/F$ is a presheaf topos.
(b) The forgetful functor $U \colon \widehat{C}/F \to \widehat{C}$ is a discrete fibration.
(c) The functor $P \colon \widehat{C}^{\text{op}} \to Set$ associated to $U$ is representable by $F$.
(d) The category $\widehat{C}/F$ is equivalent to the category of elements $\int P$.

We don't really want to prove them: we want to crisply explain them and give references to proofs. If you write something I can try to make it nicer.

Thanks. I will add .

Adittya Chaudhuri (Apr 09 2025 at 06:40):

(deleted)

Kevin Carlson (Apr 09 2025 at 07:40):

This is an aside, but in case you guys haven’t caught this vibe yet, the kind of Kleisli category you’re working on is a big inspiration for double Lawvere theories in the double categorical setting. The natural morphisms of models of double Lawvere theories are, in effect, Kleisli in this way.

Adittya Chaudhuri (Apr 09 2025 at 09:15):

John Baez said:

But here's another reason: if we can show $L$-labeled categories are monadic over $L$-labeled graphs, we can define a Kleisli category. This has $L$-labeled graphs as objects, but maps that send an edge in one $L$-labeled graph to a composite of edges in another.

This is a useful notion of morphism. For example we can use one of these morphisms to map

$\text{health} \xrightarrow{+} \text{wealth}$

to

$\text{health} \xrightarrow{+} \text{income} \xrightarrow{+} \text{wealth}$

I am thinking of it as a zooming-in (refining) details operation on a $L$-labeled graph by adding new vertices to it and factoring its $L$-labeled edges into $L$-labeled edge-paths using the Kleisli morphisms of the Kleisli category associated to the monad arising from the free-forgetful adjunction between the category of $L$-labeled graphs and the category of $L$-labeled categories as you explained. I am trying to demonstrate, why I am thinking from the point of zooming-in (refining) details operation below:

Considering your example $G:= \text{health} \xrightarrow{+} \text{wealth}$

Now, if we ask how? Then, an answer may be given by a morphism $Z_1 \colon G \to T(H_1)$ ($health \mapsto health, weatlth \mapsto wealth$, and the unique edge maps to the unique edge path in $H_1$) in the associated Kleisli category (w.r.t to the Free-forgetful monad $T$), where $H_1$ is as described by you $\text{health} \xrightarrow{+} \text{income} \xrightarrow{+} \text{wealth}$.

However, one may ask how again!!

Then, one may define another morphism: $Z_2 \colon H_1 \to T(H_2)$ (I think the definition is evident from the construction of $H_2$ below), where $H_2$ is as follows:

$\text{health} \xrightarrow{+} \text{income} \xrightarrow{+}savings \xrightarrow{+} \text{wealth}$.

Question:

By construction, $Z_2$ and $Z_1$ are composable morphisms in the Kleisli category we are talking about. Now, can we think $Z_2 \circ Z_1$ as the double-zooming in operation on $G$ , which takes $(G=\text{health} \xrightarrow{+} \text{wealth})$ to $( H_2=\text{health} \xrightarrow{+} \text{income} \xrightarrow{+}savings \xrightarrow{+} \text{wealth} )$?

If the above statement makes sense, then we can of course extend it to a "$n$-level zooming in operations on $G$", by composing $n$ number of morphisms $Z_{n} \circ Z_{n-1} \cdots \circ Z_1 \colon G \to T(H_{n})$ in the Kleisli category.

Adittya Chaudhuri (Apr 09 2025 at 09:26):

Another side of the story could be the following (Using Kleisli category)

I think the same idea has been used to describe the occurrence of motifs (which I like to think as some important simple shaped labeled graphs") like feedback loops, feedforward loops in a regulatory networks. I think the same idea had been used in the section 2.2 of https://arxiv.org/pdf/2301.01445 to find the occurrence of motifs in particular case of $L=\mathbb{Z}/2$ for regulatory networks.

I wonder the following: When we work with the monoid $\mathbb{Z}/2$, then the corresponding important shaped graphs are mostly various feedback loops and feedforward loops etc..(for example, the ones mentioned in the Uri Alon's paper https://www.nature.com/articles/nrg2102).

Question:

What are some other monoids (monoids other than $\mathbb{Z}/2$) which accommodate the notion of "interesting simple shaped graphs", and why they would be considered as interesting from the point of both applications/mathematics?

@John Baez In the overleaf file (Remark 3.2), I called a morphism $f \colon X \to T(G)$ in the Kleisli category as an occurrence of an $X$-shaped graph in $G$. (Although, my nomenclature may not be appropriate).

Adittya Chaudhuri (Apr 09 2025 at 15:15):

James Fairbanks said:

In some code I wrote for the Regulatory Networks project I computed some pullbacks of signed graphs with Catlab and it did what I expected. You could make stratified models that way too. They would be stratified at the presentation level rather than at the free signed category level.

Thank you. Does it allow multiple stratifications i.e different vertices can be stratified in different ways? i.e for example if one vertex represent students, then it may be stratified into UG and PhD's, and if another vertex denotes University, then it can be stratified into public and private?

John Baez (Apr 09 2025 at 15:39):

Nathanael Arkor said:

John Baez said:

Question. What good features does this category have when the adjunction is monadic, which it lacks otherwise?

$RL$ is the monad induced by the adjunction, so this is exactly the Kleisli category of the monad. Monadicity is irrelevant.

Oh, duh! Thanks!

John Baez (Apr 09 2025 at 15:42):

Adittya Chaudhuri said:

Another side of the story could be the following (Using Kleisli category)

I think the same idea has been used to describe the occurrence of motifs (which I like to think as some important simple shaped labeled graphs") like feedback loops, feedforward loops in a regulatory networks. I think the same idea had been used in the section 2.2 of https://arxiv.org/pdf/2301.01445 to find the occurrence of motifs in particular case of $L=\mathbb{Z}/2$ for regulatory networks.

Oh, very good point! Yes, a 'motif' is an example of a Kleisli morphism. I was talking to @Evan Patterson about this Kleisli idea recently, and he probably pointed that out.

Somehow looking for motifs in a complicated monoid-labeled graph feels a bit different than taking a simple model of a system, given by a monoid-labled graph, and 'zooming in', or 'adding detail', using a Kleisli morphism. But they're mathematically very similar.

John Baez (Apr 09 2025 at 15:49):

Adittya Chaudhuri said:

Question: What are some other monoids (monoids other than $\mathbb{Z}/2$) which accommodate the notion of "interesting simple shaped graphs", and why they would be considered as interesting from the point of both applications/mathematics?

I listed a few in my blog articles and I plan to talk about these examples in our paper - otherwise it's useless to generalize from $\mathbb{Z}/2$ to an arbitrary monoid!

The simplest example is the multiplicative monoid of $\mathbb{Z}/3$, where 1 and -1 mean 'positive effect' and 'negative effect', and 0 means 'no effect'. Notice that the additive group $\mathbb{Z}/2$ is a submonoid. There's a general construction of 'adding an absorptive element' or 0 to a monoid, and that's what we're doing to get the the multiplicative monoid of $\mathbb{Z}/3$ from the additive abelian group $\mathbb{Z}/2$.

John Baez (Apr 09 2025 at 15:50):

I also mentioned an example where we have a monoid with an element that means 'undetermined effect' - an effect that could be positive or negative.

John Baez (Apr 09 2025 at 15:50):

It's also perfectly fine to use $(\mathbb{R}, +)$ or $(\mathbb{R}, \cdot)$ as our monoid - these should be very useful in applications. These monoids have homomorphisms onto some of the small monoids I just mentioned.

John Baez (Apr 09 2025 at 16:02):

Adittya Chaudhuri said:

John Baez said:

If we write $\widehat{C}$ for the category of presheaves on a category $C$, and choose a presheaf $F \in \widehat{C}$, then:

(a) The category $\widehat{C}/F$ is a presheaf topos.
(b) The forgetful functor $U \colon \widehat{C}/F \to \widehat{C}$ is a discrete fibration.
(c) The functor $P \colon \widehat{C}^{\text{op}} \to Set$ associated to $U$ is representable by $F$.
(d) The category $\widehat{C}/F$ is equivalent to the category of elements $\int P$.

Thanks. I added the material in the overleaf file in the way you suggested. For (a), I added a reference. For (b), (c) and (d), I sketched the proofs.

Great! We should find references for all this stuff - I can't believe any of it is new. But proof sketches are also good, mainly for educational reasons. I already added a reference to Loregian-Riehl that's an introduction to the relation between functors $F : \mathsf{C}^{\text{op}} \to \mathsf{Set}$ and discrete fibrations $\int F \to \mathsf{C}$. I'll add it to this proof too.

James Fairbanks (Apr 09 2025 at 16:59):

Adittya Chaudhuri said:

Thank you. Does it allow multiple stratifications i.e different vertices can be stratified in different ways? i.e for example if one vertex represent students, then it may be stratified into UG and PhD's, and if another vertex denotes University, then it can be stratified into public and private?

You can repeatedly do pullbacks, but it gets complicated fast. The result of a pullback is actually not an object in the category, but a commutative diagram with an object that has the universal property and the span of projection maps. So in order to take a pullback of a pullback, you have to drop that extra structure. Then when you want to index into the resulting object from your nested pullbacks, you really wish you had those morphisms. In a nested pullback, it is hard to find the stuff you want algorithmically.

I found it easier to figure out what multiple stratification I wanted and set up the right limit in one shot. Then you have all the projections into the factors at one level of abstraction. You can build up that limit diagram one arrow at a time, computing limits and visualizing the results until you get all the factors in. But it is more convenient to build up the limit diagram iteratively and compute one big limit, rather than compute limits of limits.

John Baez (Apr 09 2025 at 17:12):

That's interesting. I was telling Additya it's easier (for me) to think about multiple stratifications one step at a time. But thinking is different than coding.

John Baez (Apr 09 2025 at 23:21):

Hey @Adittya Chaudhuri - thanks for putting a proof for Prop. 2.3. I've polished it up a bit - check it out.

John Baez (Apr 10 2025 at 02:04):

Could you supply a similar proof for Prop. 2.6? I've gotten up to that point now. Here's a question for the world:

• What kind of 'nice category' is the 1-category $\mathsf{Cat}$, such that any slice category $\mathsf{Cat}/C$ is also nice in this way?

(Yes, we're being evil in treating $\mathsf{Cat}$ as a 1-category, but that's mainly because in our application we think we want to use the strict slice category, where morphisms are triangles that commute on the nose.)

I know $\mathsf{Cat}$ and $\mathsf{Cat}/C$ are complete, cocomplete and cartesian closed. So one answer to my question would be "complete, cocomplete and cartesian closed". But maybe there's more.

David Egolf (Apr 10 2025 at 02:25):

This question reminds me of the fundamental theorem of topos theory. I read on the nLab that $\mathsf{Cat}$ is a "2-topos". So I wonder if there is a "fundamental theorem of 2-topos theory", and if that could be relevant here.

John Baez (Apr 10 2025 at 02:26):

Right. The sad thing is that we seem to want the strict slice 2-category, where morphisms are triangles that commute on the nose. Anyone proving a "fundamental theorem of 2-topos theory" would not use that.

John Baez (Apr 10 2025 at 02:28):

But if someone has proved a "fundamental theorem of 2-topos theory" I'd still like to know about it!

John Baez (Apr 10 2025 at 04:50):

In our paper we use the easier "fundamental theorem of presheaf topos theory", which says the slice category of a presheaf topos is a presheaf topos... and there's probably a higher version of that too.

Adittya Chaudhuri (Apr 10 2025 at 06:53):

John Baez said:

Adittya Chaudhuri said:

Question: What are some other monoids (monoids other than $\mathbb{Z}/2$) which accommodate the notion of "interesting simple shaped graphs", and why they would be considered as interesting from the point of both applications/mathematics?

I listed a few in my blog articles and I plan to talk about these examples in our paper - otherwise it's useless to generalize from $\mathbb{Z}/2$ to an arbitrary monoid!

The simplest example is the multiplicative monoid of $\mathbb{Z}/3$, where 1 and -1 mean 'positive effect' and 'negative effect', and 0 means 'no effect'. Notice that the additive group $\mathbb{Z}/2$ is a submonoid. There's a general construction of 'adding an absorptive element' or 0 to a monoid, and that's what we're doing to get the the multiplicative monoid of $\mathbb{Z}/3$ from the additive abelian group $\mathbb{Z}/2$.

Thank you, yes. But,

Question:
What could be some interesting patterns of subgraphs (motifs) in graphs labeled by elements of $\mathbb{Z}/3$ or $\mathbb{R}$ . By interesting, I meant to say an appropriate analogue of feedback and feedforward loops in the context of $\mathbb{Z}/3$ and $\mathbb{R}$?

Adittya Chaudhuri (Apr 10 2025 at 07:02):

John Baez said:

Hey Adittya Chaudhuri - thanks for putting a proof for Prop. 2.3. I've polished it up a bit - check it out.

Thank you so much for polishing the proof. The proof now looks much, much better than what I did. I am slowly understanding what you meant by "to add the right amount of details" and in "a crispy way".

Adittya Chaudhuri (Apr 10 2025 at 07:04):

John Baez said:

Could you supply a similar proof for Prop. 2.6?

Thanks. Yes, I added a basic proof in the overleaf file. By basic , I mean like the way you upgraded the version of graphs (Proposition 2.3) to presheaf topos, there should be a similar upgradation for $\mathsf{Cat}$ in Proposition 2.6. I think you are already hinting about this in #theory: applied category theory > Graphs with polarities @ 💬 In other words, can we characterise $\mathsf{Cat}$ like categories?

Adittya Chaudhuri (Apr 10 2025 at 07:15):

James Fairbanks said:

Adittya Chaudhuri said:

Thank you. Does it allow multiple stratifications i.e different vertices can be stratified in different ways? i.e for example if one vertex represent students, then it may be stratified into UG and PhD's, and if another vertex denotes University, then it can be stratified into public and private?

You can repeatedly do pullbacks, but it gets complicated fast. The result of a pullback is actually not an object in the category, but a commutative diagram with an object that has the universal property and the span of projection maps. So in order to take a pullback of a pullback, you have to drop that extra structure. Then when you want to index into the resulting object from your nested pullbacks, you really wish you had those morphisms. In a nested pullback, it is hard to find the stuff you want algorithmically.

I found it easier to figure out what multiple stratification I wanted and set up the right limit in one shot. Then you have all the projections into the factors at one level of abstraction. You can build up that limit diagram one arrow at a time, computing limits and visualizing the results until you get all the factors in. But it is more convenient to build up the limit diagram iteratively and compute one big limit, rather than compute limits of limits.

Thank you. I understand your point.

Adittya Chaudhuri (Apr 10 2025 at 07:16):

John Baez said:

That's interesting. I was telling Additya it's easier (for me) to think about multiple stratifications one step at a time. But thinking is different than coding.

Thank you. Yes, now I understand why you were suggesting about multiple stratifications one step at a time.

Graham Manuell (Apr 10 2025 at 07:42):

John Baez said:

I know $\mathsf{Cat}$ and $\mathsf{Cat}/C$ are complete, cocomplete and cartesian closed. So one answer to my question would be "complete, cocomplete and cartesian closed". But maybe there's more.

It's not true that $\mathsf{Cat}/C$ is cartesian closed in general.

Adittya Chaudhuri (Apr 10 2025 at 10:00):

Graham Manuell said:

John Baez said:

I know $\mathsf{Cat}$ and $\mathsf{Cat}/C$ are complete, cocomplete and cartesian closed. So one answer to my question would be "complete, cocomplete and cartesian closed". But maybe there's more.

It's not true that $\mathsf{Cat}/C$ is cartesian closed in general.

I think Example 1.7 in https://sinhp.github.io/files/CT/notes_on_lcccs.pdf demonstrates it.

Adittya Chaudhuri (Apr 10 2025 at 15:35):

Regarding #theory: applied category theory > Graphs with polarities @ 💬 , For the monoid $(\mathbb{N}, \times, 1)$, let us consider the $\mathbb{N}$-graphs. Let $G:= v \xrightarrow{20}v$. Then, a Kleisli morphism $Z \colon G \to T(H)$, where $H:= v \xrightarrow{2}w \xrightarrow{2}x\xrightarrow{5}v$ gives a factorisation of $20$.

I think more generally, for any $n \in \mathbb{N}$, if we consider $G:= v \xrightarrow{n}v$, then every prime factorisation $n=p^{\alpha_1}_1 p^{\alpha_2}_2 \cdots p^{\alpha_k}_{k}$ of $n$ can be described as a (monic)Kleisli morphism $Z \colon G \to T(H)$ from $G$ to some graph $H$, where $T$ is the monad associated to free-forgetful adjunction between $\mathbb{N}$-graphs and $\mathbb{N}$-categories?

Of course, it may not be anything interesting.

Kevin Carlson (Apr 10 2025 at 17:45):

John Baez said:

• What kind of 'nice category' is the 1-category $\mathsf{Cat}$, such that any slice category $\mathsf{Cat}/C$ is also nice in this way?

Locally finitely presentable (which implies complete and cocomplete and monadic over presheaf category) and extensive is about all I've got.

John Baez (Apr 10 2025 at 18:09):

Adittya Chaudhuri said:

Thank you so much for polishing the proof.

Sure!

The proof now looks much, much better than what I did.

It's based on what you did, but I want to explain things to readers who may not know all the concepts well enough. When writing it's always important to imagine who the audience is. I'm imagining an audience of people who want to apply category theory, but may not know very much category theory. So just saying some functor is a discrete fibration may not mean much to them, so I wanted to explain what it means.

Also I think it may someday be useful for people to have an explicit description of the category of $L$-labelled graphs as a presheaf category, so I added that. Probably I should move it out of the proof and make it a separate paragraph.

I am slowly understanding what you meant by "to add the right amount of details" and in "a crispy way".

Great! By the way, I said "crisp", not "crispy". English is a weird language, almost impossible to learn: potato chips (which the British call "crisps") are crispy; fresh lettuce is not crispy - but it's crisp. "Crisp" also means something else:

A crisp way of speaking, writing, or behaving is quick, confident, and effective. For example:

• a crisp reply

• a crisp, efficient manner

John Baez (Apr 10 2025 at 18:11):

Kevin Carlson said:

John Baez said:

• What kind of 'nice category' is the 1-category $\mathsf{Cat}$, such that any slice category $\mathsf{Cat}/C$ is also nice in this way?

Locally finitely presentable (which implies complete and cocomplete and monadic over presheaf category) and extensive is about all I've got.

Thanks, that's super-helpful! If I'd thought I might have guessed they were locally finitely presentable, but I would never have thought about 'extensive' since I tend to think of that as applying to categories of 'spaces'.

Adittya Chaudhuri (Apr 10 2025 at 18:14):

John Baez said:

Adittya Chaudhuri said:

Thank you so much for polishing the proof.

Sure!

The proof now looks much, much better than what I did.

It's based on what you did, but it explains things to readers who may not know all the concepts well enough. Also I think it may someday be useful to explicitly describe the category of $L$-labelled graphs as a presheaf category, so I added that.

I am slowly understanding what you meant by "to add the right amount of details" and in "a crispy way".

Great! By the way, I said "crisp", not "crispy". English is a weird language: potato chips are crispy, fresh lettuce is not crispy but it's crisp, but "crisp" also means something else:

A crisp way of speaking, writing, or behaving is quick, confident, and effective. For example:

• a crisp reply

• a crisp, efficient manner
  

Thank you. Yes, I meant `crisp', but somehow, I typed crispy.

Kevin Carlson (Apr 10 2025 at 18:40):

John Baez said:

Thanks, that's super-helpful! If I'd thought I might have guessed they were locally finitely presentable, but I would never have thought about 'extensive' since I tend to think of that as applying to categories of 'spaces'.

Well, I think Grothendieck at least thought that categories are a kind of space!

John Baez (Apr 10 2025 at 20:37):

If you think of categories as simplicial sets with an extra property you can think of them as a kind of space, but it takes a lot of nerve.

John Baez (Apr 10 2025 at 20:50):

Yes, I meant 'crisp', but somehow, I typed crispy.

Okay. I started getting interested in the difference between crisp and crispy and got into an argument with my wife about it. I argued that good potato chips are clearly "crispy", while she says they are "crisp".

I don't know if I can continue to live with someone who has such fundamental disagreements with me.

John Baez (Apr 11 2025 at 00:46):

On a more serious note:

$L$-labeled graphs with $L = \{+,-\}$ are often called 'causal loop diagrams' because people use them to identify 'feedback loops'. I think it would be good to say a bit about this. Here's an idea:

We can define the first homology of a graph $G$ with coefficients in $L$, $H_1(G)$, in two equivalent ways. We can either geometrically realize the graph as a space and take its first homology with $\mathbb{Z}$ coefficients, or - better - define an abelian group of 'cycles' in $G$, called $Z_1(G)$, and an abelian group of 'boundaries', called $B_1(G)$ and form $H_1(G)$ as a quotient:

$H_1(G) = Z_1(G)/B_1(G)$

At least when we have a finite graph, $H^1(G)$ is a free abelian group. But beware: there's no canonical choice for the generators of this free group.

John Baez (Apr 11 2025 at 00:52):

However:

1) $G$ is a directed graph, and for our applications the only possible feedback loops are directed loops: that is, paths of edges of the form

$v_0 \xrightarrow{e_1} v_1 \xrightarrow{e_2} \cdots \xrightarrow{e_n} v_n = v_0$

So, we're not really interested in the usual 1st homology, but only a kind of directed first homology. This should be easy to define, but maybe someone in directed algebraic topology has already defined the directed first homology of a directed graph - so we should find out.

2) In some of our applications $L$ is not an abelian group but merely a commutative monoid. So, the usual textbook theory of homology doesn't apply. However, the directed first homology of a graph with coefficients in a commutative monoid should still make sense.

John Baez (Apr 11 2025 at 01:37):

When we understand this stuff, I hope there will be

• a commutative monoid $\vec{Z}_1(G)$ of 'directed cycles' in $G$

and

• a congruence relation saying when two directed cycles are 'homologous'

so we can define the commutative monoid $\vec{H}_1(G)$ as $\vec{Z}_1(G)$ modulo the congruence relation of being homologous.

(Note that with commutative monoids, we should mod out by [[congruence relations]], not submonoids! For abelian groups you can turn congruence relations into (normal) subgroups, which lets you talk about modding out by a subgroup. But that uses subtraction!)

I conjecture that, at least for a finite graph, $\vec{H}_1(G)$ will be a free commutative monoid on some set of generators. (If you draw me a directed graph, I believe I can find such generators.)

John Baez (Apr 11 2025 at 01:42):

Then I hope we can do this:

Suppose $L$ is a commutative monoid and $G$ is an $L$-labeled graph, i.e. a graph with a map $\ell$ sending edges to elements of $L$.

Clearly for any directed loop in $G$

$v_0 \xrightarrow{e_1} v_1 \xrightarrow{e_2} \cdots \xrightarrow{e_n} v_n = v_0$

we get an element of $L$, namely

$\ell(e_1) + \cdots + \ell(e_n)$

This describes the feedback around this directed loop. (It's analogous to a holonomy.)

But I also conjecture that we get a map of commutative monoids

$\tilde{\ell} \colon \vec{Z}_1(G) \to L$

sending cycles to elements of $L$. I haven't defined cycles, but a cycle should an $\mathbb{N}$-linear combination of edges of $G$ with some property saying its boundary is zero. Then, to define $\tilde{\ell}$$ on a cycle, we sum up the labels over all the edges that appear in this cycle. (The same edge may show up several times in a cycle - so then we sum its label several times.)

This tells us the total feedback around any cycle!

John Baez (Apr 11 2025 at 01:43):

I conjecture that if $c \sim c'$ are homologous cycles, then we get the same element of $\ell$ this way:

$\tilde{\ell}(c) = \tilde{\ell}(c')$

John Baez (Apr 11 2025 at 01:47):

If so, $\tilde{\ell}$ descends to a map of commutative monoids

$\vec{H}_1(G) \to L$

Maybe I'll call this by the same name, $\tilde{\ell}$.

I conjecture that this map contains all the information about how much feedback there is around any directed loop.

John Baez (Apr 11 2025 at 01:56):

One nice thing about this little project is that @Adittya Chaudhuri has already studied holonomies of connections, and this is very much like that: made simpler because we are working on a graph, but more complicated because we are working with a (commutative) monoid instead of a group!

John Baez (Apr 11 2025 at 01:57):

It's possible we should develop this for a not-necessarily-commutative monoid.

James Deikun (Apr 11 2025 at 05:24):

In the conventional first homology of a graph, there are no bounding cycles, so $H_1(G) \cong Z_1(G)$. And when you only look at directed cycles, two cycles can't add up to a cycle that doesn't self-intersect, so you actually get canonical generators.

I was also going to suggest matroid theory besides homology, but it actually doesn't look very promising for this.

Adittya Chaudhuri (Apr 11 2025 at 12:21):

John Baez said:

One nice thing about this little project is that Adittya Chaudhuri has already studied holonomies of connections, and this is very much like that: made simpler because we are working on a graph, but more complicated because we are working with a (commutative) monoid instead of a group!

Thanks. Are you hinting towards the following?

Given a connection 1-form $\omega$ on a smooth principal $G$-bundle $\pi \colon E \to M$ and a point $x \in M$,

1) we can construct a holonomy map $\mathcal{H} \colon \Omega (M,x) \to G$, where $\Omega (M,x)$ is the set of smooth loops on $M$ based at $x$ . On the other hand, one can recover the whole bundle with the connection data from the holonomy map.

2) when two smooth loops $\gamma_1$ and $\gamma_2$ are thin homotopic then the map $\mathcal{H}$ descends to a map on the quotient $\bar{\mathcal{H}} \colon \Omega (M,x)/ \sim \to G$. Here, $\sim$ is the equivalence relation on $\Omega (M,x)$ defined by thin homotopy.

I think (1) is analogous to $\tilde{l} \colon \vec{Z}_1(G) \to L$.

I think (2) is analogous to the map $\tilde{l} \colon \vec{H}_1(G) \to L$.

Now, if we replace the set $\Omega (M,x)$ by $\Omega (M,x)_{lazy}$ containing lazy paths (as defined in https://arxiv.org/pdf/1003.4485), then we can turn $\Omega (M,x)_{lazy}/ \sim$ into a group under concatenation as a binary operation. We can then extend the set map $\bar{\mathcal{H}}$ to a group homomorphism $\bar{\mathcal{H}} \colon \Omega (M,x)_{lazy}/ \sim \to G$.

Then like the way the group homomorphism $\bar{\mathcal{H}} \colon \Omega (M,x)_{lazy}/ \sim \to G$ contain information of the bundle $\pi \colon E \to M$ with connection $\omega$, the homomorphism of commutative monoids $\tilde{l} \colon \vec{H}_1(G) \to L$ contain the information of how much feedback in any directed loop in the $L$-labeled graph $G$.

Or, am I misunderstanding ?

Adittya Chaudhuri (Apr 11 2025 at 14:34):

@John Baez The relation (that you described) between the directed first homology of a graph with coefficients in a (commutative) monoid $L$ and the feedback loops in $L$-labeled graphs seems super interesting!! Now, I am trying to understand all these things (what you wrote) properly.

Adittya Chaudhuri (Apr 11 2025 at 14:48):

By directed Algebraic topology, are you saying about https://ncatlab.org/nlab/show/Directed+Algebraic+Topology?

John Baez (Apr 11 2025 at 16:51):

James Deikun said:

In the conventional first homology of a graph, there are no bounding cycles, so $H_1(G) \cong Z_1(G)$.

In Sunada's approach to undirected graphs (summarized in my paper Topological crystals, section 2) one counts an edge path like

$v_0 \xrightarrow{e_1} v_1 \xrightarrow{e_2} v_2 \xrightarrow{e_2^{-1}} v_1 \xrightarrow{e_1^{-1}} v_0$