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: Networks in Biology

Adittya Chaudhuri (Jul 06 2025 at 13:57):

Lets talk about Networks in Biology in this thread!!

In our recent paper Graphs with polarities, @John Baez and I studied how monoid labeled directed graphs can model regulatory networks in biology when the monoid is suitably chosen. We discussed the work related to this paper here #theory: applied category theory > Graphs with polarities . Now I am trying to understand the content of this interesting paper Cell Fate Reprogramming by Control of Intracellular Network Dynamics by Jorge G. T. Zañudo and Réka Albert (Suggested by @John Baez ). Let me start by spelling out my very initial understanding of the paper. I apologise priorly if my understanding sounds very naive and immature at the moment. I expect to get better with my understanding in the coming days. In this thread, I am assunming the notations used in our paper Graphs with polarities.

How the framework in the paper Cell Fate Reprogramming by Control of Intracellular Network Dynamics relates to our framework in Graphs with polarities??

For a monoid $M$, let $(G, \ell \colon E \to M)$ be a monoid labeled graph. Although in Graphs with polarities, we modelled regulatory network as a $M$-labeled graph for some suitable choices of monoids $M$, we have not studied the dynamics of $M$-labeled graphs. I feel Biologists are usually interested in three kinds of dynamics:

• Quantitative dynamics (For example, @Evan Patterson et al studied an O.D.E based dynamics of regulatory networks via structured cospan formalism here) .
• Logic based dynamics (Eg: Boolean networks)
• Hybrid dynamics (which is a hybrid of both quantitative dynamics and logic based dynamics ).

For a detailed discussion related to "how the above three classes of dynamics modelling approach differ and how each has its own advantages", please see the paper Quantitative and logic modelling of gene and molecular networks by Nicolas Le Novère.

I feel the paper Cell Fate Reprogramming by Control of Intracellular Network Dynamics discusses certain interesting and as well as useful aspects of logic based dynamics of our $\mathbb{Z}/2$-labeled graphs in Graphs with polarities and is discussed in terms of Boolean networks. In particular, the authors studied how stabilizing the expression or activity of a few select nodes of a regulatory network can drive the cell towards a desired fate or away from an undesired fate. I may be wrong but next, I will try to argue why I think a Boolean network describe a logic based dynamics of our $M$-labeled graphs!!.

Adittya Chaudhuri (Jul 06 2025 at 19:27):

Below, I am trying to write my understanding of a Boolean model of the discrete dynamics of a regulatory network as explained in An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks adopted in the framework of monoid labeled graphs.

Consider a $M$-labeled graph $(G=(E,V,s,t), \ell \colon E \to M)$. Let $V= \lbrace v_1, v_2, \cdots, v_{n} \rbrace$. Now, suppose for each $i =1, 2, \cdots n$, consider a $\lbrace 0,1 \rbrace$-valued function $f_i \colon \mathbb{N} \to \lbrace 0, 1 \rbrace$ the state function of the vertex $v_i$. We define the state of the vertex $v_i$ at time $t$ as $f_{i}(t)$.

If $f_i(t)=0$, we will say the vertex $v_i$ is off.

If $f_i(t)=1$, we will say the vertex $v_i$ is on.

We define the tuple $F(t)=(f_1(t), f_2(t), \cdots, f_{n}(t))$ as the state of $(G, \ell)$ at time $t$.

Now for each $i$, we have to equip an updating function

$f_i(t+1)= \phi_i \bigg( \prod_{t(e_j)=v_i, s(e_j)=v_j} \big( (f_j(t), \ell(e_j) \big) \bigg)$, where

$\phi_i \colon (\lbrace 0,1 \rbrace \times M)^{|{G(-, v_i)}|} \to \lbrace 0,1 \rbrace$, where $G(-, v_i) = \lbrace e \colon t(e)=v_i \rbrace$.

Thus, we can extend the above definition to an updating family of functions

$\phi=(\phi_1, \phi_2, \cdots, \phi_n )$ which updates the state of $(G, \ell)$ from $F(t)$ to $F(t+1)$.

Thus, I am defining a Boolean model of the discrete dynamics of $(G, \ell)$ as the tuple $((G, \ell), \phi)$, with a given initial state $F(0)=(f_1(0), f_2(0), \cdots f_n(0))$ at $t=0$.

Above is an example of synchronous updating scheme, where the state of every vertex is updated simultaneously. However, in many cases, the updating scheme is asynchronous, in which we have to define the updating function accordingly. (I have to think how to talk about it in a formal way).

Adittya Chaudhuri (Jul 06 2025 at 19:45):

Next I want to understand the concept of attractor, a set of states in which the above dynamics eventually settles down. According to the authors in Cell Fate Reprogramming by Control of Intracellular Network Dynamics,

"The attractors of intracellular networks have been found to be identifiable with different cell fates, cell behaviors, and stable patterns of cell activity"

John Baez (Jul 06 2025 at 19:55):

It might be good to start by focusing on the synchronous updating scheme for boolean networks, even though it's oversimplified, and look at various biologically interesting behaviors that can naturally arise from this scheme. The paper you're writing about claims to make progress in this:

As it was pointed out in section II A, the state space of
a Boolean network with N nodes contains $2^N$ states. This
exponential dependence on the number of nodes of the
state space's size makes the problem of finding the attractors
of a Boolean network computationally intractable,
which means a full search of the state space can be performed,
in practice, only for small networks.

To overcome this challenge several types of methods have
been proposed to simplify the search space. The most
prominent of these approaches, the so-called network reduction
methods [35-38], shrink the effective network size
by removing frozen nodes (nodes that reach the same
steady state regardless of initial conditions) [38-40] and
dynamically irrelevant nodes (such as simple mediator
nodes or nodes with no outputs), and by simplifying the
Boolean functions (for example, due to the presence of a
node with a fixed state), thus reducing the effective state
space.

Although the reduction methods developed so far have
been successfully applied to several biological networks
[35-37, 41], they have some limitations [....]

The method that we propose is based on the idea that
certain components of the network can only stabilize in
one or a small number of attractors. This idea is itself
not new and is closely related to R. Thomas' rules
linking feedback loops with the appearance of complex
dynamical behavior in biological networks [19]. For example,
an approach that connects the dynamics of certain
network motifs to construct the attractors of the full
Boolean network was recently proposed by Siebert [28].
The novelty of our method is the efficiency of identifying
every motif that stabilizes in an asynchronous attractor
despite being coupled to the rest of the network...

This makes me want to figure out what their method is. I couldn't succeed in a few minutes of work. I don't even know what it means to say a motif stabilizes in an "asynchronous attractor", given that they're studying the synchronous updating scheme. But it would definitely be worth spending an hour or two trying to figure out their method! If it's too hard, maybe some of the papers they refer to are easier.

By the way, here is a free version of the paper you linked to, on the arXiv:

• An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks.

The version you pointed to doesn't seem to be open-source.

Adittya Chaudhuri (Jul 07 2025 at 05:19):

John Baez said:

It might be good to start by focusing on the synchronous updating scheme for boolean networks, even though it's oversimplified, and look at various biologically interesting behaviors that can naturally arise from this scheme.

Thank you!! Yes, I agree.

Kevin Carlson (Jul 07 2025 at 05:24):

I bounced off the complicated notation for your updating function at first glance. Maybe you can just say what you mean in words too? There's a graph floating around here and yet nobody said anything like "the state depend son the state of all the neighbors"!

Adittya Chaudhuri (Jul 07 2025 at 05:29):

Kevin Carlson said:

I bounced off the complicated notation for your updating function at first glance. Maybe you can just say what you mean in words too? There's a graph floating around here and yet nobody said anything like "the state depend son the state of all the neighbors"!

Yes, I meant to say that the transition from one state $t$ of a vertex $v$ to another $t+1$ depends on two things:

1) State of the neighbours of $v$ at $t$ (state of neighbours also include the state of $v$ itself at $t$).

2) Regulatory nature (stimulation, inhibition, etc.) of the neighbours of $v$ on $v$.

Adittya Chaudhuri (Jul 07 2025 at 05:35):

John Baez said:

This makes me want to figure out what their method is. I couldn't succeed in a few minutes of work. I don't even know what it means to say a motif stabilizes in an "asynchronous attractor", given that they're studying the synchronous updating scheme. But it would definitely be worth spending an hour or two trying to figure out their method! If it's too hard, maybe some of the papers they refer to are easier.

Thanks!! Yes, I completely agree. I am trying to undertstand what they meant by "a motif stabilizes in an "asynchronous attractor", given that they're studying the synchronous updating scheme"

Adittya Chaudhuri (Jul 07 2025 at 05:37):

John Baez said:

By the way, here is a free version of the paper you linked to, on the arXiv:

• An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks.

The version you pointed to doesn't seem to be open-source.

Thanks very much for this version. Somehow, I could not find it yesterday and I downloaded the previous version from my institutional account.

Adittya Chaudhuri (Jul 07 2025 at 05:40):

John Baez said:

The method that we propose is based on the idea that
certain components of the network can only stabilize in
one or a small number of attractors. This idea is itself
not new and is closely related to R. Thomas' rules
linking feedback loops with the appearance of complex
dynamical behavior in biological networks [19].

I am trying to understand "what they meant by the above paragraph".

Adittya Chaudhuri (Jul 07 2025 at 05:46):

John Baez said:

Although the reduction methods developed so far have
been successfully applied to several biological networks
[35-37, 41], they have some limitations [....]

I need to understand "what they meant by their reduction method" and "what are its limitations".

John Baez (Jul 07 2025 at 05:52):

Kevin Carlson said:

I bounced off the complicated notation for your updating function at first glance. Maybe you can just say what you mean in words too? There's a graph floating around here and yet nobody said anything like "the state depend son the state of all the neighbors"!

Adittya mentioned a graph, but I don't see why. Maybe the paper talks about a graph? I prefer to think about a boolean network: a set of vertices and for each vertex $v$ a set $S_v$ of vertices together with a boolean function $\mathbb{B}^{S_v} \to \mathbb{B}$ telling us the state of that vertex as a function of the states of the vertices in $S_v$. If we start by assigning each vertex a boolean at time $t$, we can update the state at time $t+1$ using these functions in the hopefully obvious way.

At least this is my impression of how boolean networks work. Wikipedia puts it this way:

A Boolean network consists of a discrete set of Boolean variables each of which has a Boolean function (possibly different for each variable) assigned to it which takes inputs from a subset of those variables and output that determines the state of the variable it is assigned to. This set of functions in effect determines a topology (connectivity) on the set of variables, which then become nodes in a network. Usually, the dynamics of the system is taken as a discrete time series where the state of the entire network at time t+1 is determined by evaluating each variable's function on the state of the network at time t.

Adittya Chaudhuri (Jul 07 2025 at 06:04):

John Baez said:

Kevin Carlson said:

I bounced off the complicated notation for your updating function at first glance. Maybe you can just say what you mean in words too? There's a graph floating around here and yet nobody said anything like "the state depend son the state of all the neighbors"!

Adittya mentioned a graph, but I don't see why. Maybe the paper talks about a graph? I prefer to think about a boolean network: a set of vertices and for each vertex $v$ a set $S_v$ of vertices together with a boolean function $\mathbb{B}^{S_v} \to \mathbb{B}$ telling us the state of that vertex as a function of the states of the vertices in $S_v$. If we start by assigning each vertex a boolean at time $t$, we can update the state at time $t+1$ using these functions in the hopefully obvious way.

My inspiration for thinking Boolean network as "some extra structure" on a monoid labeled graph $(G, \ell)$ (which gives us a discrete dynamics of $(G, \ell)$) comes from the page 2 of * An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks (please see the attached screenshot for the precise portion on the page).
boolnetwork.png

John Baez (Jul 07 2025 at 06:06):

What's the point of having the graph, if "experience shows us" that this is not enough and we need a boolean network as I defined it above? I would throw out the graph. Anyway, I would not worry about these details much until I figured out the "method" which is supposedly the main point of this paper. These are biologists writing, not mathematicians, so I don't expect them to be very precise, but they may (or may not) have an interesting "method".

Adittya Chaudhuri (Jul 07 2025 at 06:09):

I understand your point but it said "not enough", but may be necessary. That is why I thought of keeping the both graph structure and as well as the "boolean network" structure in my updating function here #theory: applied category theory > Networks in Biology @ 💬 . I may be misunderstanding something!!

Adittya Chaudhuri (Jul 07 2025 at 06:10):

John Baez said:

Anyway, I would not worry about these details much until I figured out the "method" which is supposedly the main point of this paper. These are biologists writing, not mathematicians, so I don't expect them to be very precise, but they may (or may not) have an interesting "method".

Thanks!! Yes, I agree to your point.

Adittya Chaudhuri (Jul 07 2025 at 16:33):

I am trying to write down my current understanding of stable motifs in a Boolean network as discussed in An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks.

Adittya Chaudhuri (Jul 08 2025 at 05:47):

Sorry I realised I was misunderstanding very fundamentally about Boolean networks. In particular, I realised that the graph structure in Boolean network is induced from the Boolean functions on the nodes. Before, I was misunderstanding by thinking that "we are starting with a graph structure and then adding the Boolean functions to it". I now realised what @John Baez explained here #theory: applied category theory > Networks in Biology @ 💬 . So, I decided to delete my yesterday night's post and redfine the notions according to my current realisations.

Boolean network:
A Boolean network $B$ consists of a finite set of nodes $V= \lbrace v_1, v_2, \cdots v_{n} \rbrace$ along with

• a family of subsets $\lbrace S_{v_i} \subseteq V \rbrace_{i=1,2, \cdots, n}$ whose members are the regulators of $v_i$,
• a family of functions $\lbrace f_{i} \colon \mathbb{B}^{S_{v_i}} \to \mathbb{B} \rbrace_{i=1,2, \cdots, n}$ whose members are the Boolean functions associated to $v_i$.

Graph associated to a Boolean network:
Let $B=(v_i, S_{v_i}, f_i)_{i= 1,2, \cdots n}$ be a Boolean network. We define a graph $G_{B}=(E,V, s, t)$ whose

• set of vertices $V$ is the set of nodes in $B$
• the set of edges $E:= \lbrace \big(v, v_i\big) \colon v \in S_{v_{i}}, i \in \lbrace 1,2, \cdots, n \rbrace\rbrace$
• the source $s \colon E \to V, (v,v_i) \mapsto v$,
• the target $t \colon E \to V, (v, v_i) \mapsto v_i$.
  We define the graph $G_{B}$ as the graph associated to Boolean network $B$.

Remark:
Note that $G_{B}$ does not permit multiple edges between vertices.

Discrete dynamics of a Boolean network:
Let $B=(v_i, S_{v_i}, f_i)_{i= 1,2, \cdots n}$ be a Boolean network. Consider a family of functions $\lbrace \phi_i \colon \mathbb{N} \to \mathbb{B}^{S_{v_i}} \rbrace_{i=1, 2, \cdots n}$, whose members are called the updating functions of the node $v_i$. We define the discrete dynamics of $B$ as the the n-tuple $F_{B}= \big( f_1 \circ \phi_1, f_2 \circ \phi_2, \cdots ,f_n \circ \phi_{n} \big)$.

State of the Boolean dynamics:

Let $(B, F_{B})$ be the discrete dynamics of the Boolean network $B=(v_i, S_{v_i}, f_i)_{i= 1,2, \cdots n}$. We define the state of $(B, F_{B})$ at time $t \in \mathbb{N}$ as the n-tuple

$F(t):= \big( f_1 \circ \phi_1(t), f_2 \circ \phi_2(t), \cdots ,f_n \circ \phi_{n}(t) \big) \in \mathbb{B}^{n}$,

and we define the state of the vertex $v_i$ at time $t \in \mathbb{N}$ as the projection of $F(t)$ to its $i_{th}$ coordinate.

Based on the above formalisms, I will define the notion of stable motifs later today.

Nathaniel Virgo (Jul 08 2025 at 09:02):

There is something slightly strange about that definition, because it could be that one of the functions $f_i$ doesn't depend on one of its arguments, say $j\in S_{v_i}$. Then the graph will have an edge from $j$ to $i$ even though there is no influence of $j$ on $i$, if that makes sense. I'm not sure if this will matter for anything or not.

Maybe a better way to express that is: what's the right notion of morphism for Boolean networks? It seems like maybe you'd want such a network to be isomorphic to one where $j\not\in S_{v_i}$.

John Baez (Jul 08 2025 at 09:24):

I have thought about Nathaniel's point when I was defining "stock flow diagrams", which have "links" pointing from "stocks" to "flows" together with a function saying how a flow depends on those stocks that have links pointing to it. The function could be independent of one of its arguments! Then one link would be unnecessary. But instead of trying to forbid this, I decided it was better to allow it.

To disallow it is a bit like trying to say a constant function is not really a function. "What? You're telling me 3 is a function of x? That's absurd!" It feels convincing in a certain gut-level way, but I think it's mathematically very inconvenient.

Adittya Chaudhuri (Jul 08 2025 at 11:09):

Thanks!!

Below, I am trying to write down below what I thought about the issue:

According to the (page 3- 4 (Expanded network) of attached puiblished version of An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks Screenshot of the portion is attached
An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks.pdf
labeledBoolean.png
),

I think Biologists often prefer to work with the following labeled version of graphs associated to Boolean networks:

Labeled Boolean graph:
Let $G_{B}$ be the graph associated to a Boolean network $B=(v_i, S_{v_i}, f_{i})_{i=1,2, \cdots ,n}$. For a monoid $M$, we define a $M$-labeled Boolean graph of $B$ as a $M$-labeled graph (as defined in our paper Graphs with polarities) $(G_{B} \colon \ell \colon E \to M)$.

Remark:
Note that in the diagram attached, authors considered a $\mathbb{Z}/2$-labeled Boolean graph of some Boolean network $B$.

Now, I propose a solution to the issue raised by @Nathaniel Virgo as follows:

Let us work in the $\mathbb{Z}/3$-labeled Boolean graph whose one of the element say $0$ represents "no-influece" [We discussed this in Example 3.4 in our paper Graphs with polarities].

Then, I would like to label the unnecessary edges with the element $0$ ??

John Baez (Jul 08 2025 at 11:46):

By the way, I think this issue is distracting from the more urgent goal of figuring out what "reduction approach" is being explained in An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks.

John Baez (Jul 08 2025 at 11:47):

Our earlier paper was setting up a formalism, and for that it's nice to pay careful attention to details. But if one is trying to understand a biology paper one needs to start by trying to understand the main thing they're trying to say, and later worry about details.

Nathaniel Virgo (Jul 08 2025 at 11:48):

(sorry, I didn't mean to distract, the detail just popped out at me when I read the post!)

John Baez (Jul 08 2025 at 11:49):

No problem - I'm just trying to act like Adittya's advisor, since he doesn't seem to mind that, and I'm trying to push him into doing actual biology, since he seems to want that.

Adittya Chaudhuri (Jul 08 2025 at 13:35):

John Baez said:

Our earlier paper was setting up a formalism, and for that it's nice to pay careful attention to details. But if one is trying to understand a biology paper one needs to start by trying to understand the main thing they're trying to say, and later worry about details.

Thanks!! Yes,  I got your point and fully agree with it!! I will focus on figuring out the "reduction approach" in that paper.

Adittya Chaudhuri (Jul 08 2025 at 13:35):

John Baez said:

I'm just trying to act like Adittya's advisor, since he doesn't seem to mind that, and I'm trying to push him into doing actual biology, since he seems to want that.

Thanks very much!! I am very glad and grateful for this!!

David Corfield (Jul 08 2025 at 14:06):

It would be interesting to look at commonalities and differences of approach in this field. In a paper along the lines of that Symmetries of Living Systems book I mentioned elsewhere,

• Luis A. Álvarez-García, Wolfram Liebermeister, Ian Leifer, Hernán A. Makse, Complexity reduction by symmetry: uncovering the minimal regulatory network for logical computation in bacteria,

the authors explain the steps of their work to understand something as complex as E. coli

image.png

The use of fibrations should make people here feel very at home.

John Baez (Jul 08 2025 at 15:23):

What's a 'TRN'? I'm assuming a 'GRN' is a gene regulatory network.

John Baez (Jul 08 2025 at 15:32):

Hmm, looking at the paper I don't see them defining 'TRN', but nor do I see them using that term except in the one section header that David gave us a screenshot of! So never mind.

There is a lot of interesting stuff in this paper. I see what seems like the bold claim that most of the gene regulatory network of E. coli (for example) is unnecessary to understand the behavior of this bacterium, or at least the most important aspects.

They start with a gene regulatory network (GRN) with 4692 genes and then trim it down to a 'minimal' GRN with just 42 genes. I don't yet understand the algorithm they use, and I also don't know what properties are supposed to be preserved by this massive simplification. But it sounds remarkable. I guess how remarkable it is depends on how much evolution penalizes inefficiency.

It could be that some seemingly unimportant aspects of the bacteria's GRN become important under some special conditions.

John Baez (Jul 08 2025 at 15:46):

I'm glad to see the key idea of 'fibration' for these GRNs seems to be taken from my friend Eugene Lerman and a collaborator: I remember Eugene working on it and it's nice to see someone has picked up on it!

Here's an interesting passage:

We have shown before [4, 10, 11, 24] that the use of fibrations allows for the breakdown of the network into its fundamental synchronized building blocks, the fiber building blocks. Each fiber belongs to a fiber building block, defined as the induced subgraph formed from the nodes in the fiber, and the nodes that send inputs to the fiber (the regulators).

[....]

We find that these fiber building blocks can be precisely characterized by just two numbers n (or φ) and ℓ, defining the |n, ℓ⟩ classes [10].

John Baez (Jul 08 2025 at 15:48):

Paper [10] is

• Flaviano Morone, Ian Leifer, and Hernán A Makse, Fibration symmetries uncover the building blocks of biological networks, Proceedings of the National Academy of Sciences 117(15) (2020), 8306–8314.

John Baez (Jul 08 2025 at 15:50):

This passage in the paper makes my crackpot alarm ring:

The building blocks are classified into topological classes of input trees characterized by integer branching ratios and fractal golden ratios of Fibonacci sequences representing cycles of information.

Anyone who mentions 'fractal', 'golden ratio' and 'Fibonacci' in the same sentence makes me afraid.

Adittya Chaudhuri (Jul 08 2025 at 16:02):

On a different note (but might be related), for last few days (after @David Corfield shared the paper on symmetries of Living systems), I was trying to understand the Math of Graph fibrations from the paper fibrations of graphs by Boldi and Vigna.

Last to last week, one of my collegue at my current institute (ISI, Kolkata, Stat-Math Dept.) gave a talk on discrete $A$-homotopy of undirected simple graphs, where he was also talking about "local isomorphism" properties imply casrtesian morphisms lifting in graph fibrations. Although his definition of graph is a bit restrictive than ours. Interestingly, I find the notion of local isomorphisms present in the "paper on graph fibrations" (for eg: Please see page 25 of Fibration of graphs) relatable.

Adittya Chaudhuri (Jul 08 2025 at 16:41):

Now again, I am continuing from here #theory: applied category theory > Networks in Biology @ 💬 towards network reduction methods discussed in An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks

Adittya Chaudhuri (Jul 08 2025 at 17:51):

Expanded network of a Boolean network:

Let $B=(v_i, S_{v_i}, f_{v_i})_{i= 1,2, \cdots n}$ be a Boolean network. Then, the expanded network of a Boolean network $B$ is the graph $G_{Exp(B)}$ of a Boolean network $Exp(B)$ obtained from $G_B$ via the following two operations:

• 1) For every node $v_{i}$ we introduce a complementary node $\bar{v_i}$ such that the Boolean function associated to $\bar{v_i}$ is the negation of the Boolean function $f_{i} \colon \mathbb{B}^{S_{v_i}} \to \mathbb{B}$ associated to $v_i$.
• 2) Let $\lbrace v_{i1}, v_{i2}, \ldots, v_{ik} \rbrace$ denote the elements of $S_{v_i} \subseteq V$, and let $f_i$ is expressed in the following form
  synergistic.png
  

where $s_j$'s are either the states of one of the $k$ elements of $S_{v_i}$ or one of these states' negations. In the same way, one can also represent the negation of the update function $\bar{f_i}$ in a similar form. Then, composite nodes $(v_1v_2 \cdots v_{k}), (v_{k+1} v_{k+2} \cdots v_{l}), \ldots$ so on... are added for every set of nodes involved in a conjunctive clause (AND-dependent relationship) and for every constituent node of the composite node an edge is drawn from the constituent node to the composite node. A simpler example of this operation is attached in the screenshot.

examplesyn.png

Stable motifs are certain strongly connected components of $G_{Exp(B)}$, which I am going to define next!!

Adittya Chaudhuri (Jul 08 2025 at 17:55):

Before defining stable motifs, I will say a few things about "what $Exp(B)$ gives us"!!

Adittya Chaudhuri (Jul 08 2025 at 18:13):

According to the authors in that paper, $Exp(B)$ buys us the following:

Consequence of (1):

• (a) It allows us to evaluate the inhibitory effect of a node on the rest of the network.
• (b) By assigning the negation of the original Boolean function to every complementary node, it also explictly considers how the other nodes can promote the inactivation of a given node.

Consequence of (2):

• (1) We identify synergistic interactions (via AND) of the neighbouring vertices of a vertex on the vertex.

David Corfield (Jul 08 2025 at 18:59):

John Baez said:

What's a 'TRN'? I'm assuming a 'GRN' is a gene regulatory network.

"A gene regulatory network (GRN) is often referred to as a transcriptional regulatory network
(TRN), although the former is more general than the latter." (Stewart et al. book, p. 139)

David Corfield (Jul 08 2025 at 19:06):

John Baez said:

Anyone who mentions 'fractal', 'golden ratio' and 'Fibonacci' in the same sentence makes me afraid.

I don't think it's too concerning. From the book with Ian Stewart:

image.png

John Baez (Jul 08 2025 at 19:11):

Yes, I saw this chart in the paper I was reading. Maybe this is a case of people who haven't noticed that crackpots love to drop references to fractals, Fibonacci numbers and the golden ratio much more than ordinary scientists, and thus haven't learned that a sentence like the one they wrote is alarming rather than intriguing to many of us.

You may have heard of the physicists Paul Davies. He got in trouble talking about black holes and the golden ratio.

Adittya Chaudhuri (Jul 08 2025 at 19:11):

I realised I misunderstod here #theory: applied category theory > Networks in Biology @ 💬 while "discussing $\mathbb{Z}/2$-labeled Boolean graph. I feel the following may be the correct interpretation of labeledBoolean.png

The definition of $f_i \colon \mathbb{B}^{S_{v_i}} \to \mathbb{B}$ naturally gives a $\mathbb{Z}/2$-labeled graph, when logical operators like NOT is used in the definition of $f_i$. Previously, I misinterpreted by thinking that "we are incorporating an addtional labeling on the graph associated with the Boolean network".

John Baez (Jul 08 2025 at 19:18):

What graph do you draw for $f_A = B$ OR $C$? Or is that boolean expression not allowed here?

John Baez (Jul 08 2025 at 19:19):

By the way, I have a lot of questions about what you've been explaining - I don't understand it.

Adittya Chaudhuri (Jul 08 2025 at 19:20):

For $f_{A}=B$, I would draw $B \xrightarrow{+} A$

John Baez (Jul 08 2025 at 19:20):

Okay. But that's not what I asked about.

Adittya Chaudhuri (Jul 08 2025 at 19:24):

John Baez said:

Okay. But that's not what I asked about.

I understood the problem. I am not able to distinguish between $f_{A}= B$ AND $C$ and $f_{A}= B$ OR $C$ by drawing a $\mathbb{Z}/2$-labeled graph. However, I am able to distinguish them in the expanded graph by introducing the composite node.
IMG_0377.PNG

Adittya Chaudhuri (Jul 08 2025 at 19:27):

BC is the composite node here.

Adittya Chaudhuri (Jul 08 2025 at 19:28):

John Baez said:

By the way, I have a lot of questions about what you've been explaining - I don't understand it.

I will try my best to answer. Also, Sorry for explaing not well. I am trying to improve my explanation.

Adittya Chaudhuri (Jul 08 2025 at 19:35):

I think $F_A=$ NOT $C$ in $B$ tranforms into $F_A=\bar{C}$ in $Exp(B)$, and hence $C \xrightarrow{-} A$ in $G_B$ becomes $\bar{C} \xrightarrow{+} A$ in $G_Exp(B)$. Here, $B$ denotes the Boolean network and $Exp(B)$ denotes the expanded network of $B$.

John Baez (Jul 08 2025 at 19:38):

I'll probably ask my questions tomorrow, after rereading what you wrote.

Adittya Chaudhuri (Jul 08 2025 at 19:39):

Okay, I am also learning and writing at the same time. So, may be tomorrow, my understanding will get better than what I have today.

Adittya Chaudhuri (Jul 09 2025 at 06:09):

I think the dynamics of a Boolean Network $B$ (i.e a Boolean network along with its updating functions on nodes) naturally gives us a $\mathbb{Z}/2$-labeled graph $G_{B}$, whose signed edges represent the influences of the $t_{th}$ state of a neighbour $w \in S_{v_i}$ of a vertex $v_i$ on the $(t+1)_{th}$ state of the vertex $v_i$. I think the graph structure represents a synergistic (cumulative) influence of $t_{th}$ states of all the neighbours of a vertex $v_i$ on the $(t+1)_{th}$ state of the vertex $v_{i}$ via "logical combinations" (especially AND) of the state of the neigbouring vertices $v \in S_{v_i}$ at time $t$, which determines the state of the vertex $v_i$ at time $t+1$.

In the attached file, I tried to explain it through examples.

Booleannetworkgraphs.PNG

I feel the logical operator "NOT" is the reason for using the $\mathbb{Z}/2$-labeled graph structure on the graph associated to the Boolean network."

Adittya Chaudhuri (Jul 09 2025 at 06:44):

The last post is my current understanding of what I think a Boolean network and its associated graph means. It seems according to this understanding I need to reformulate some the definitions accodingly here #theory: applied category theory > Networks in Biology @ 💬 . However, before formalising fully, as @John Baez suggested before, first, I am trying to figure out the authors' reduction methods discussed in that paper based on the understianding of my "last post". Although I am not fully sure, it seems my last post makes more sense than what I was saying till yesterday night.

David Corfield (Jul 09 2025 at 10:35):

I guess if you were allowed two time steps, you could represent something acting as $A$ OR $B$, by negative edges from $A$ and from $B$ to a third node and a negative edge from that to a fourth node.

John Baez (Jul 09 2025 at 12:23):

Hmm. This seems messy, and I don't feel confident that the authors are doing things optimally, so instead of trying to understand this I'll ask some questions about the "big picture" - basically, why are they doing all this stuff.

Let me state my understanding so far. I'm going to completely avoid using math symbols or formulas, because those are often distracting when you're trying to understand basic ideas.

They start with a boolean network, which is a simple and clear concept, at least in my definition back here.

Then they try to build a graph from that boolean network - I guess a graph with edges labeled by signs. As far as I can tell, this graph is suppose to say whether one node affects another node "positively" or "negatively" (or not at all, if there's no edge). But I don't see how to determine this for an arbitrary boolean network: e.g. I can say

If it's Monday I'll eat a sandwich when I see it's 2 pm; if it's Tuesday I won't eat a sandwich when I see it's 2 pm

Does it being 2 pm affect my sandwich eating positively or negatively? This question has no answer; it's not a good question.

So, I'm already confused about what they're trying to do.

Then they try build another graph, starting from the first one, called the "expanded network" of the Boolean network. Adittya says it's obtained from the first graph using two operations.

1) First, for each node we introduce a "complementary node" which is a kind of negation of the original one. E.g. if we had a node that means "I'm eating a sandwich", we'd put in a new node meaning "I'm not eating a sandwich". This is simple enough.

2) Then, we introduce a bunch of nodes called "composite nodes", using a [procedure](Hmm. This seems messy, and I don't feel confident that the authors are doing things optimally, so instead of trying to understand this I'll ask some questions about the "big picture" - basically, why are they doing all this stuff.

Let me state my understanding so far. I'm going to try to avoid using any math symbols or formulas, because those are often distracting when you're trying to understand basic ideas.

They start with a boolean network, which is a simple and clear concept, at least in my definition back here.

Then they try to build a graph from that boolean network - I guess a graph with edges labeled by signs. As far as I can tell, this graph is suppose to say whether one node affects another node "positively" or "negatively" (or not at all, if there's no edge). But I don't see how to determine this for an arbitrary boolean network: e.g. I can say

If it's Monday I'll eat a sandwich when I see it's 2 pm; if it's Tuesday I won't eat a sandwich when I see it's 2 pm

Does it being 2 pm affect my sandwich eating positively or negatively? This question has no answer; it's not a good question.

So, I'm already confused about what they're trying to do.

Then they try build another graph, starting from the first one, called the "expanded network" of the Boolean network. Adittya says it's obtained from the first graph using two operations.

1) First, for each node we introduce a "complementary node" which is a kind of negation of the original one. E.g. if we had a node that means "I'm eating a sandwich", we'd put in a new node meaning "I'm not eating a sandwich". This is simple enough.

2) Then, we introduce a bunch of nodes called "composite nodes", using a procedure that's too complicated for me to understand - since I don't know the goal of this procedure.

Adittya did kindly try to explain the goal of doing 1) and 2):

Consequence of (1):

• (a) It allows us to evaluate the inhibitory effect of a node on the rest of the network.

• (b) By assigning the negation of the original Boolean function to every complementary node, it also explictly considers how the other nodes can promote the inactivation of a given node.
  Consequence of (2):

• (1) We identify synergistic interactions (via AND) of the neighbouring vertices of a vertex on the vertex.

I still feel very confused. It almost seems that the authors don't like boolean networks, so they are trying to build a graph that expresses most of the information in the original boolean network. But they don't seem to be claiming their expanded graph captures all the information in the original boolean network, do they?

Is there any way to say what information they're trying to capture, and what information they're throwing out? Presumably the information they're trying to capture is supposed to be "more important" in some way.

David Corfield (Jul 09 2025 at 15:14):

John Baez said:

I'm glad to see the key idea of 'fibration' for these GRNs seems to be taken from my friend Eugene Lerman and a collaborator: I remember Eugene working on it and it's nice to see someone has picked up on it!

Looking around for other applications of fibrations, I see there's the FibLang work of @Fabrizio Romano Genovese,  @fosco and @Caterina Puca (here and here). These look to understand natural language and its acquisition via fibrations. They rely on the result that any functor factors through a fibration. There's also work on locating obstructions to a functor being a fibration by Fabrizio and others.

On the other hand, I see that those using graph fibrations in biology are also interested in slight departures, which get called "13.5.1 Pseudosymmetries 246, 13.5.2 Quasifibrations 249, 13.5.3 Pseudo-balanced colorings".

I wonder if there's some useful cross-over. Grammatical language would resemble the latter's reduced gene networks, the logic of cognition and of the cell.

John Baez (Jul 09 2025 at 16:53):

David Corfield said:

It would be interesting to look at commonalities and differences of approach in this field. In a paper along the lines of that Symmetries of Living Systems book I mentioned elsewhere,

• Luis A. Álvarez-García, Wolfram Liebermeister, Ian Leifer, Hernán A. Makse, Complexity reduction by symmetry: uncovering the minimal regulatory network for logical computation in bacteria,

I'm enjoying this paper, not because it uses fibrations, but because it makes sense to me both biologically and mathematically.

David Corfield (Jul 09 2025 at 18:35):

Yes, it's nicely organised. The book has Makse also as one of its authors and covers similar ground, but at much greater length especially on the pure mathematics, as well as several further topics.

Adittya Chaudhuri (Jul 09 2025 at 19:28):

John Baez said:

Then they try to build a graph from that boolean network - I guess a graph with edges labeled by signs. As far as I can tell, this graph is suppose to say whether one node affects another node "positively" or "negatively" (or not at all, if there's no edge). But I don't see how to determine this for an arbitrary boolean network: e.g. I can say

Sorry, I was a bit distracted from the afternoon till night. I was attending a post marriage ceremony of one of my closest friend (who is coincidentally also a Mathematician, and works in Algebraic geometry). I just returned from the ceremony venue.

For me, given a Boolean network $\mathsf{B}$, the signed edges of the graph $G_{\mathsf{B}}$ may not say whether one node affects another node "positively" or "negatively". I may be misunderstanding something fundamentally, but my interpreation for them are the following:

• Say we get an edge $A \xrightarrow{+} B$. For me, it means the $(t+1)_{th}$-state of $B$ is similar to the $t_{th}$ state of $A$.
• Say we get an edge $C \xrightarrow{-} D$. For me, it means the $(t+1)_{th}$-state of $D$ is not similar to the $t_{th}$ state of $C$.
• Now, if there are no other edges $e$ in the graph $G_{\mathsf{B}}$ such that the target of $e$ is $B$, then $(t+1)_{th}$-state of $B$ is same as the $t_{th}$ state of $A$. In Boolean network form it says: $f_{B}:=A$.
• Now, if there are no other edges $e'$ in the graph $G_{\mathsf{B}}$ such that the target of $e'$ is $D$, then $(t+1)_{th}$-state of $D$ is opposite to the $t_{th}$ state of $C$. In Boolean network form, it says $f_{D}:=$ NOT $C$.
• Let $G(-, B)$ denotes the set of all edges in $G_{\mathsf{B}}$ whose target is $B$. Say, $G(-, B)$ is not singleton. For example, say $G(-, B)$ consists of four elements $A \xrightarrow{+ } B, A_1 \xrightarrow{+ } B, A_2 \xrightarrow{- } B, A_3 \xrightarrow{+ } B$. Then,

$f_{B}:= (A) \,\,\text{AND} \,\, (A_1) \text{AND}\,\, (\text{NOT} \,\, A_2)\,\, \text{AND}\,\, (A_3)$. In otherwords, the cumulative effects of the $t_{th}$ states of the elements of $G(-, B)$ (via logical operarations) determines the $(t+1)_{th}$ state of $B$.

In a way, logical operations on $t_{th}$ state of the source vertices determines the $(t+1)_{th}$ state of the target vertex.

Adittya Chaudhuri (Jul 09 2025 at 19:33):

John Baez said:

Hmm. This seems messy, and I don't feel confident that the authors are doing things optimally,

I am also feeling the same!!

Adittya Chaudhuri (Jul 09 2025 at 20:16):

John Baez said:

I still feel very confused. It almost seems that the authors don't like boolean networks, so they are trying to build a graph that expresses most of the information in the original boolean network.

I feel following are some features of the expanded network:

• (1) Due to the introduction of complementary nodes in the framework, they turn the signed graph $G_{B}$ into just a directed graph.
• (2) They defined the notion of stable motifs for expanded networks, and identify them in the stable motifs for executing their network reduction method.

I am still trying to understand "how they are using their definition of stable motifs in their network reduction methods". In their network reduction method, they are starting their method by keeping states of the nodes of the stable motifs fixed. Although, I am not able to see "why they suddenly define the notion of stable motifs in their expanded network" and "then fix their states" and thus probably justifying the name "stable" .

It is also not clear to me

• "why they need the expanded network" ? Why they need to define stable motifs in expanded network and assume that "the states of the nodes of stable motifs are fixed" ? I am not fully understanding how these constructions are crucial (as they claimed) in their method of network reduction.

I feel they think their definition of a stable motif is good enough to assume that the states of the nodes of the stable motif will be constant eventually. However, at the moment, I am not able to see this from their definition of stable motif .

I am thinking about these things!!

Adittya Chaudhuri (Jul 09 2025 at 20:32):

John Baez said:

But they don't seem to be claiming their expanded graph captures all the information in the original boolean network, do they?

Is there any way to say what information they're trying to capture, and what information they're throwing out? Presumably the information they're trying to capture is supposed to be "more important" in some way.

I feel they are trying to define the notion of stable motifs in their expanded network which by definition is not possible to define in the original Boolean network. (However, I doubt whether we really need conceptually to define stable motifs in their way in expanded network, or, it may suffice to define certain usual motifs in the signed graph associated to Boolean network.) According to authors: their definition of a stable motif is good enough to assume that the states of the nodes of the stable motif will be constant eventually. However, at the moment, I am not able to see this from their definition of stable motif. Then, they use this fact to fix the states of the stable motifs as the starting point of their network reduction method.

Adittya Chaudhuri (Jul 10 2025 at 09:30):

Hi!! I think I found a formal way to express the definition of Boolean network and its associated signed graph, which expresses the information that I informally discussed here #theory: applied category theory > Networks in Biology @ 💬 .

Below, I am wrting down what I thought about it:

Boolean network:
A Boolean network $\mathsf{B}$ consists of the following:

• A finite set $V:= \lbrace v_1, v_2, \cdots v_{n} \rbrace$ called nodes of $\mathsf{B}$.
• A family of subsets $\lbrace S_{v_{i}} \rbrace_{i= 1, 2, \cdots, n} \subseteq V$ whose $i_{th}$ member is called the neighbouring nodes of $v_{i}$.
• A family of functions $\lbrace \phi_{i} \colon \mathbb{B}^{S_{v_i}} \to \mathbb{B} \rbrace_{i=1,2, \cdots, n}$.
• A family of functions $\lbrace \psi_{i} \colon \mathbb{Z} \to \mathbb{B}^{S_{v_i}} \rbrace_{i=1,2, \cdots, n}$

Let $T_{1} \colon \mathbb{N} \to \mathbb{Z}, n \mapsto (n-1)$.

We define the update function of the vertex $v_i$ as the function $f_{i}= \phi_i \circ \psi_{i} \circ T_1 \colon \mathbb{N} \to \mathbb{B}$.

Thus, by definition, we have $f_{i}(t+1)= \phi_i \circ \psi_i \circ T_1(t)$.

I intereprete the above as the following:

The logical operations on $t_{th}$ state of neighbouring nodes of $v_i$ determines the $(t+1)_{th}$ state of the node $v_i$. Here, I would expect that the definition of the function $\phi_{i} \colon \mathbb{B}^{S_{v_i}} \to \mathbb{B}$ will involve logical operations "NOT and AND". The composition of function $\psi_{i} \circ T_1$ gives us the $t_{th}$ states of the neighbouring nodes of $v_i$.

Next, I will construct a $\mathbb{Z}/2$-labeled graph $G_{\mathsf{B}}$ from $\mathsf{B}$ as follows:

• Vertices of $G_{B}$ are the nodes of $V$.
• From the family of subsets $\lbrace S_{v_{i}} \rbrace_{i= 1, 2, \cdots, n} \subseteq V$, we get all the directed edges of $G_{B}$.
• Now, whenever, in the definition of $\phi_{i}$ there is a NOT operator involve, we label the associated edge with $-$, otherwise we label the edges by $+$. This gives us the proposed directed $\mathbb{Z}/2$-labeled graph $G_{B}$ associated to the Boolean network $\mathsf{B}$.

Thus, I feel the $\mathbb{Z}/2$-labeled $G_{B}$ behaves like a graphical model of the dynamics of the Boolean network $B$ (i.e how the Boolean network $\mathsf{B}$ changes from the $t_{th}$ state to the $(t+1)_{th}$-state.)

John Baez (Jul 10 2025 at 10:09):

I'm struggling to understand what you wrote. What's the role of the functions $\psi_i$? Say it in words without symbols, please. Why does a boolean network need to involve functions, one for each vertex, from the integers to boolean functions on the set of vertices that affect that vertex? What do the integers represent here?

My definition of 'boolean network' didn't involve integers at all.
I just have enough information to update the boolean at each vertex, as a function of the booleans at the vertices that affect it. I don't understand why your definition is so much more complicated, and the introduction of integers is the most mysterious part.

Adittya Chaudhuri (Jul 10 2025 at 12:04):

John Baez said:

What's the role of the functions $\psi_i$? Say it in words without symbols, please.

The functions $\psi_{i}$ tells the states of the neighbouring vertices of $v_{i}$ at a given time.

Adittya Chaudhuri (Jul 10 2025 at 12:18):

John Baez said:

Why does a boolean network need to involve functions, one for each vertex, from the integers to boolean functions on the set of vertices that affect that vertex? What do the integers represent here?

I wanted to express the fact that the function $f_i$ tells that the $(t+1)_{th}$ state of the vertex $v_i$ is determined by the $t_{th}$ states of the vertices of the neighbours of $v_i$. For this, I needed a function that takes in the time $t$ and gives out the time $t-1$. Since, in $\mathbb{N}$ I can not subtract, I took $\mathbb{Z}$. I formalized this by taking the composition $f_i:= \mathbb{N} \xrightarrow{T_1} \mathbb{Z} \xrightarrow{\psi_i} \mathbb{B}^{S_{v_{i}}} \xrightarrow{\phi_i} \mathbb{B}$, where the function $T_1 \colon \mathbb{N} \to \mathbb{Z}, n \mapsto (n-1)$.

Adittya Chaudhuri (Jul 10 2025 at 12:29):

John Baez said:

My definition of 'boolean network' didn't involve integers at all.
I just have enough information to update the boolean at each vertex, as a function of the booleans at the vertices that affect it. I don't understand why your definition is so much more complicated, and the introduction of integers is the most mysterious part.

I am Sorry!! May be there are many redundant information in my definition that I am yet to see. I am trying to make my definition more simpler.

I feel my $\phi_{i}$ is your Boolean function at the vertex $v_i$.

To incorporate the "updating information formallly in the setting" as I explained in my previous post, I wrote the other functions, which I guess is making my definition complicated. However, I agree that $\phi_i$ is the most important information for updating the Boolean at each vertex.

John Baez (Jul 10 2025 at 13:44):

Adittya Chaudhuri said:

John Baez said:

Why does a boolean network need to involve functions, one for each vertex, from the integers to boolean functions on the set of vertices that affect that vertex? What do the integers represent here?

I wanted to express the fact that the function $f_i$ tells that the $(t+1)_{th}$ state of the vertex $v_i$ is determined by the $t_{th}$ states of the vertices of the neighbours of $v_i$. For this, I needed a function that takes in the time $t$ and gives out the time $t-1$. Since, in $\mathbb{N}$ I can not subtract, I took $\mathbb{Z}$. I formalized this by taking the composition $f_i:= \mathbb{N} \xrightarrow{T_1} \mathbb{Z} \xrightarrow{\psi_i} \mathbb{B}^{S_{v_{i}}} \xrightarrow{\phi_i} \mathbb{B}$, where the function $T_1 \colon \mathbb{N} \to \mathbb{Z}, n \mapsto (n-1)$.

Okay, so $\mathbb{Z}$ is time. But I don't think "time" should be part of the definition of a boolean network. Time, and in particular integer-valued-time, is part of one possible semantics for boolean networks.

John Baez (Jul 10 2025 at 13:46):

I wanted to express the fact that the function $f_i$ tells that the $(t+1)_{th}$ state of the vertex $v_i$ is determined by the $t_{th}$ states of the vertices of the neighbours of $v_i$. For this, I needed a function that takes in the time $t$ and gives out the time $t-1$. Since, in $\mathbb{N}$ I can not subtract, I took $\mathbb{Z}$.

If you're trying to compute the next state as a function of the current state, you just need to describe a function that maps states to states. You don't need to mention time at all. (And you definitely don't need to subtract 1, since subtracting one takes us one time step into the past, not the future!)

John Baez (Jul 10 2025 at 13:52):

As I've said before, I think a boolean network is

1) a finite set $V$ of nodes,
2) a set $S_v$ of nodes for each node $v$, and
3) a function $\phi_v : \mathbb{B}^{S_v} \to \mathbb{B}$ for each node $v$.

That's all.

A state of a boolean network is a function

$s: V \to \mathbb{B}$

From a boolean network it's easy to define a time evolution function

$F: \mathbb{B}^V \to \mathbb{B}^V$

that maps states to states. (I'll leave this as an exercise: here we use the functions $\phi_v$.)

Thus, if we have a state $s$, we get a sequence of states $F(s), F(F(s)), \dots$ which describe how the state evolves in time, and we can define the state at time $n \in \mathbb{N}$ to be $F^n(s)$.

John Baez (Jul 10 2025 at 13:55):

This seems much simpler than bringing in the mysterious functions and $\psi_i$, and all this stuff about integers, including the function $T_1 : \mathbb{N} \to \mathbb{Z}$.

Also - this is a smaller stylistic point - there's no need to index the vertices by numbers $i = 1, \dots, n$. Indexing by numbers is often a mistake. You can use the vertices to name themselves! For example when you write "the vertex $v_i$" you can just write "the vertex $v$", and when you write $S_{v_i}$ you can just write $S_v$, and when you write $\phi_i$ you can write $\phi_v$. That simplifies some expressions, and it avoids bringing in these irrelevant numbers $i = 1, \dots, n$, which just distract us from the actual ideas.

Adittya Chaudhuri (Jul 10 2025 at 20:19):

John Baez said:

As I've said before, I think a boolean network is

1) a finite set $V$ of nodes,
2) a set $S_v$ of nodes for each node $v$, and
3) a function $\phi_v : \mathbb{B}^{S_v} \to \mathbb{B}$ for each node $v$.

That's all.

A state of a boolean network is a function

$s: V \to \mathbb{B}$

From a boolean network it's easy to define a time evolution function

$F: \mathbb{B}^V \to \mathbb{B}^V$

that maps states to states. (I'll leave this as an exercise: here we use the functions $\phi_v$.)

Thus, if we have a state $s$, we get a sequence of states $F(s), F(F(s)), \dots$ which describe how the state evolves in time, and we can define the state at time $n \in \mathbb{N}$ to be $F^n(s)$.

Thanks very much!! I find your ideas very interesting and much much more elegant and natural than my approach of incorporating the dynamics of a Boolean network by creating an "unnecessarily complicated definition of a Boolean network".

In particular, I find your idea of genarating the time evolution function $F \colon \mathbb{B}^{V} \to \mathbb{B}^{V}$ of a Boolean network from the underlying structure of your Boolean network very beautiful. In otherwords, (as you mentioned as part of the exercise you proposed) every state $s \colon V \to \mathbb{B}$ induces by restiriction a family of maps $\lbrace s_{v} \colon S_{v} \to \mathbb{B} \rbrace_{v \in V}$, which gives us a map $\bar{s} \colon V \to \mathbb{B}$ that takes $v$ to $\phi_{v}(s_{v}) \in \mathbb{B}$.

Thus, $F(s):=\bar{s}$. I also liked very much the idea of using "n-times self composition of $F$" as the evolution of the Boolean network at time $t=n$ much much more elegant than my approach of using the map $\mathbb{N} \to \mathbb{Z} \to \mathbb{B}^{S_{v}}$ to talk about time evolution.

Adittya Chaudhuri (Jul 10 2025 at 20:21):

John Baez said:

This seems much simpler than bringing in the mysterious functions and $\psi_i$, and all this stuff about integers, including the function $T_1 : \mathbb{N} \to \mathbb{Z}$.

I fully agree. Thanks very much!!

Adittya Chaudhuri (Jul 10 2025 at 20:25):

John Baez said:

Also - this is a smaller stylistic point - there's no need to index the vertices by numbers $i = 1, \dots, n$. Indexing by numbers is often a mistake. You can use the vertices to name themselves! For example when you write "the vertex $v_i$" you can just write "the vertex $v$", and when you write $S_{v_i}$ you can just write $S_v$, and when you write $\phi_i$ you can write $\phi_v$. That simplifies some expressions, and it avoids bringing in these irrelevant numbers $i = 1, \dots, n$, which just distract us from the actual ideas.

Thanks!! Yes, I agree to your point. I will use these notational conventions from now on.

Adittya Chaudhuri (Jul 10 2025 at 20:30):

John Baez said:

As I've said before, I think a boolean network is

1) a finite set $V$ of nodes,
2) a set $S_v$ of nodes for each node $v$, and
3) a function $\phi_v : \mathbb{B}^{S_v} \to \mathbb{B}$ for each node $v$.

That's all.

Thanks!! Now, the above definition makes full sense to me!!

Adittya Chaudhuri (Jul 10 2025 at 20:43):

I think then associated to any Boolean network $B$ (i.e your definition), we can still construct a $\mathbb{Z}/2$-labeled graph $G_{B}$ as

• Vertices of $G_{B}$ are the nodes of $V$.
• From the family of subsets $\lbrace S_{v} \rbrace_{v \in V}$, we get all the directed edges of $G_{B}$.
• Now, whenever, in the definition of $\phi_{v}$ there is a NOT operator involved, we label the associated edge with $-$, otherwise we label the edges by $+$. This gives us a directed $\mathbb{Z}/2$-labeled graph $G_{B}$ associated to the Boolean network $B$.

Adittya Chaudhuri (Jul 10 2025 at 20:51):

Although I directly do not feel the need of "constructing this $\mathbb{Z}/2$-labeled graph at all". Except, yes, since this is a graph in a "graph theoretic sense" we may understand the Boolean network from the point of graph theory or homology theory of monoids, or by identifying the motifs in this $\mathbb{Z}/2$-labeled graphs via Kleisli morphisms.

Also, may be another interesting aspect of representing a Boolean network as a $\mathbb{Z}/2$-labeled graph is the availability of "ACT compositional theorems based on structured cospans" for creating a compositional framework for your definition of Boolean networks.

Adittya Chaudhuri (Jul 10 2025 at 20:55):

However, I think it could be interesting if we define a double category of Boolean networks and then define a double functor from this double category to the double category of $\mathbb{Z}/2$-labeled graphs (as we defined in our paper) as a functorial semantic of Boolean network (your definition) ?

Adittya Chaudhuri (Jul 10 2025 at 21:03):

So, first I want to check the following:

Does the assoiciation $\mathsf{B} \mapsto G_{\mathsf{B}}$ gives a functor from the appropriate category of Boolean networks to the category $\mathsf{Gph}/G_{\mathbb{Z}/2}$?

John Baez (Jul 10 2025 at 21:08):

I'm glad my ideas seem useful.

Adittya Chaudhuri said:

I think then associated to any Boolean network $B$ (i.e your definition), we can still construct a $\mathbb{Z}/2$-labeled graph $G_{B}$ as

• Vertices of $G_{B}$ are the nodes of $V$.
• From the family of subsets $\lbrace S_{v} \rbrace_{v \in V}$, we get all the directed edges of $G_{B}$.
• Now, whenever, in the definition of $\phi_{v}$ there is a NOT operator involved, we label the associated edge with $-$, otherwise we label the edges by $+$. This gives us a directed $\mathbb{Z}/2$-labeled graph $G_{B}$ associated to the Boolean network $B$.

I'm not sure this rule for associating edges with $+$ or $-$ is well-defined. Suppose $\phi_v$ is a function of two boolean variables which I will call $A$ and $B$ given by

$\phi_v$ (A,B) = (A and B) or (not(A) and not(B))

Do you label the edges with $+$ or $-$ in this case?

Adittya Chaudhuri (Jul 10 2025 at 21:10):

I want to use only "AND and NOT" operators. For the time being I am excluding the OR operators. I know I may sound "very unnatural", but I agree I am confused how to create the signed graph structure induced from the OR operator.

John Baez (Jul 10 2025 at 21:19):

If the paper we're discussing develops an interesting "network reduction approach", it makes sense to study these questions. If it doesn't, these questions may not be worth studying.

John Baez (Jul 10 2025 at 21:20):

I still do not understand their "network reduction approach". Do you?

Adittya Chaudhuri (Jul 10 2025 at 21:21):

John Baez said:

I still do not understand their "network reduction approach". Do you?

Not yet clear. I am trying to improve my understanding of their method in a considerable way by tomorrow. At least, now we have a "definition of what I can think a Boolean network is".

Adittya Chaudhuri (Jul 10 2025 at 21:22):

John Baez said:

If the paper we're discussing develops an interesting "network reduction approach", it makes sense to study these questions. If it doesn't, these questions may not be worth studying.

I agree.

Adittya Chaudhuri (Jul 10 2025 at 21:24):

They define certain "minimal strongly connected components" of their Expanded networks as Stable motifs. Then, they assumed that the states of the vertices in this component will be fixed eventually. This is the starting point of their network reduction method.

Adittya Chaudhuri (Jul 10 2025 at 21:38):

On a different note, I just found this paper Decomposition of Boolean networks: An approach to modularity of biological systems by Claus Kadelka, Reinhard Laubenbacher, David Murrugarra, Alan Veliz-Cuba, and Matthew Wheeler, which studies "a decomposition theory of Boolean networks in "a non-category theoretic way". I will read what they have done.

John Baez (Jul 10 2025 at 22:08):

They define certain "minimal strongly connected components" of their Expanded networks as Stable motifs. Then, they assumed that the states of the vertices in this component will be fixed eventually.

Do they assume it or do they prove it? Is it true or not? You can't make something true just by assuming it.

I'm getting more and more suspicious of this paper.

If you decide this paper is junk, maybe you should switch to reading some better ones, like the paper you just mentioned (if it's better), or this one that David pointed out:

• Luis A. Álvarez-García, Wolfram Liebermeister, Ian Leifer and Hernán A. Makse, Complexity reduction by symmetry: uncovering the minimal regulatory network for logical computation in bacteria.

which seems pretty good. In fact I think this paper, and related papers by these authors, and the book

• Hernan A. Makse, Paolo Boldi, Francesco Sorrentino and Ian Stewart, Symmetries of Living Systems: Symmetry Fibrations and Synchronization in Biological Networks.

provide an easy way to start doing interesting mathematics connected to gene regulatory networks, I thank @David Corfield for pointing us toward these papers!

Adittya Chaudhuri (Jul 11 2025 at 05:52):

John Baez said:

They define certain "minimal strongly connected components" of their Expanded networks as Stable motifs. Then, they assumed that the states of the vertices in this component will be fixed eventually.

Do they assume it or do they prove it? Is it true or not? You can't make something true just by assuming it.

I am not able to see the proof in the main body of the paper. In the main body I think they assumed it. Previously, I was mostly focussed on the "main body of the paper itself" and somehow did not look at the Appendix part. Now, when I looked at the Appendix portion, it seems they might have given the proof. I think I need to read and understand their proofs (Page 15 onwards in An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks) before I can conclude whether they have assumed or proved that "states of the vertices in this component will be fixed eventually".

Adittya Chaudhuri (Jul 11 2025 at 06:10):

John Baez said:

If you decide this paper is junk, maybe you should switch to reading some better ones, like the paper you just mentioned (if it's better), or this one that David pointed out:

• Luis A. Álvarez-García, Wolfram Liebermeister, Ian Leifer and Hernán A. Makse, Complexity reduction by symmetry: uncovering the minimal regulatory network for logical computation in bacteria.

which seems pretty good. In fact I think this paper, and related papers by these authors, and the book

• Hernan A. Makse, Paolo Boldi, Francesco Sorrentino and Ian Stewart, Symmetries of Living Systems: Symmetry Fibrations and Synchronization in Biological Networks.

provide an easy way to start doing interesting mathematics connected to gene regulatory networks, I thank David Corfield for pointing us toward these papers!

Yes, I also thank very much to @David Corfield for pointing us to these papers. I went through the abstract of the paper Complexity reduction by symmetry: uncovering the minimal regulatory network for logical computation in bacteria. It looks very interesting to me too. Since I was already reading about the math of Graph fibrations from the paper fibrations of graphs by Boldi and Vigna, I find it would be interesting (both from the point of usefuleness in Biology and as well as from the point of developing interesting Mathematics inspired from Biology) to understand how these concepts can be used in the doing useful things for studying networks in Biology/GRN in particular.

I also read the abstract of the "paper on decomposition of Boolean networks" that I shared before. At the moment I am finding the David's suggested paper and the book more interesting. So, I would prefer to read these David's suggested paper and the book before I start reading the "decomposition paper".

Also, along with this, I would like to understand the proofs present in the Appendix of the paper An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks to verify whether this paper's claim and methodology are compatible with each other.

David Corfield (Jul 11 2025 at 08:53):

I'd be very interested in thinking about this graph fibration approach. Here's a question:

We know that a graph homomorphism is a fibration if and only if the functor induced between the respective free categories is a discrete fibration. We also know that any functor between categories can be factorized through a fibration. What then if we find a graph homomorphism that is close to being graph fibration (as in 13.5 of the book)? We might measure this by inducing a functor on the respective free categories, and then using techniques for measuring departure from being a discrete fibration, as here. Would the factorization of this functor through a fibration correspond to factoring the graph homomorphism through a graph fibration?

Perhaps this is an area to investigate later, but there's bound to be a great range of ideas from CT to bring over to the biology.

Adittya Chaudhuri (Jul 11 2025 at 11:42):

David Corfield said:

I'd be very interested in thinking about this graph fibration approach.

Thanks!! I am very glad to know that.

Adittya Chaudhuri (Jul 11 2025 at 12:00):

David Corfield said:

We also know that any functor between categories can be factorized through a fibration.

By "fibration" do you mean a [[Grothendieck fibration]] or fibrations in [[canonical model structure on Cat]] or, in some other Model structure on $\mathsf{Cat}$? However, from the reference you suggested (which measures departure from being a discrete fibration), I think you meant Grothendieck fibrations ?

If I assume Grothendieck fibration, then I am not able to see how this statement is true when we are not working in the category of groupoids (which is certainly the case for ours because we are working in the framework of directed graphs, and hence the we would get free category of graphs rather than free groupoid of graphs). More precisely, fibrations of [[canonical model structure on groupoids]] are precisely the [[isofibration]], which are same as Grothendieck fibrations (Example 4.2 in [[isofibration]]). However, I think this statement is not true when we are working in $\mathsf{Cat}$ (For eg: please see here).

Adittya Chaudhuri (Jul 11 2025 at 12:05):

David Corfield said:

there's bound to be a great range of ideas from CT to bring over to the biology.

I agree !!

Adittya Chaudhuri (Jul 11 2025 at 12:11):

David Corfield said:

We might measure this by inducing a functor on the respective free categories, and then using techniques for measuring departure from being a discrete fibration, as here.

Thanks very much!! I find this idea quite interesting!! I will read the paper your shared.

David Corfield (Jul 11 2025 at 12:51):

Adittya Chaudhuri said:

By "fibration" do you mean...

It's a reference to the result recorded at [[comprehensive factorization system]], factorizing a functor into a final functor and a discrete fibration.

Adittya Chaudhuri (Jul 11 2025 at 13:31):

Thanks for clarifying!! Now, I understand your question:

"Would the factorization of this functor through a fibration correspond to factoring the graph homomorphism through a graph fibration?

Interesting!! I am thinking on this question.

Adittya Chaudhuri (Jul 11 2025 at 14:36):

At the moment, I am not able to see any "answer to your question". I will work with some small examples first.

Adittya Chaudhuri (Jul 11 2025 at 14:58):

David Corfield said:

It's a reference to the result recorded at [[comprehensive factorization system]], factorizing a functor into a final functor and a discrete fibration.

I was not aware of this particular factorisation till today. So, thanks very much again for mentioning about this factorisation. I would be curious to know what would be a suitable analog of a final functor "for graphs".

David Corfield (Jul 11 2025 at 15:38):

We might see for $\phi: G \to H$, a homomorphism of graphs, whether the induced functor between free categories, $F(\phi): F(G) \to F(H)$, factorizes in such a way that the intermediate category is free on some graph.

Kevin Carlson (Jul 11 2025 at 18:51):

I’m pretty sure that any discrete fibration $\pi: C\to D$ over a free category has free domain. A morphism $f$ in $C$ lies over a composite of indecomposables in $D$, which gives a unique factorization of $f$ into morphisms lying over indecomposables, repeatedly applying the discrete fibration property; and a morphism over an indecomposable is actually indecomposable because $\pi$ reflects identities.

Adittya Chaudhuri (Jul 11 2025 at 20:48):

Thanks @Kevin Carlson for the explanation !!

@David Corfield , then, it seems for every homomorphism of graphs $\phi \colon G \to H$, the induced functor between free categories $F(\phi) \colon F(G) \to F(H)$ factorises (via comprehensive factorization system) such that intermidiate category is free on some graph.

In a way, I think it also means that the comprehensive factorization system of $\mathsf{Cat}$ induces a comprehensive factorization system of the Kleisli category of the monad associated to the Free-forgetful adjunction between $\mathsf{Gph}$ and $\mathsf{Cat}$ .

Adittya Chaudhuri (Jul 11 2025 at 22:34):

@John Baez here #theory: applied category theory > Graphs with polarities @ 💬 you mentioned that a Boolean network is a "sort of labeled hypergraph". Inspired from your description, I was trying to think how the underlying graph structure of a Boolean network influences the states of a particular vertex in the Boolean network . In particular, I was trying to see whether the Boolean "rig" can be used to capture indirect and cumulative influences.

To undestand this, I produced a mental image of "such a graph". I am attaching a simple example of such a mental image.
compositeindirectBoolean.PNG

It is also possible that I am misunderstanding something while creating the mental image.

David Corfield (Jul 12 2025 at 06:35):

You might be interested in Makse et al.'s ways of representing hypergraphs in the chapter where they extend fibrations to hypergraphs:

image.png

David Corfield (Jul 12 2025 at 06:58):

Given the "noise" of biological systems perturbing perfect fibrational symmetry, leading to the search for what Makse et al. call "quasifibrations", there might be a useful framing where given a graph $G$ one looks to find a graph $H$ and homomorphism $\phi: G \to H$, which in some sense minimizes the size of $H$ while maximizing the degree to which $\phi$ is a fibration.

John Baez (Jul 12 2025 at 09:58):

By the way, I'm not sold on calling fibrations 'symmetry' I see that those authors want to push for a generalized concept of symmetry more suited to biology than physics: they make a big case for it at the beginning of their book. I agree that it's very interesting to study systems that admit a kind of 'projection', e.g. a fibration, down to some simpler system! But I don't yet want to call this 'symmetry'.

Earlier Stewart and Golubitsky had made a case for groupoid symmetries in biology:

• Martin Golubitsky and Ian Stewart, Nonlinear dynamics of networks: the groupoid formalism, Bull. Amer. Math. Soc. 43 (2006), 305-364.

I'm completely sold on calling groupoid actions 'symmetries': there's enough similarity in the technical machinery between groups and groupoids that we can generalize lots of methods from the former to the latter.

If every fibration $p: X \to Y$ gives rise to a groupoid, such that $p$ can be seen as 'modding out by the groupoid action', then I'll be very happy and I'll see how to understand fibrations as 'symmetry'. But I don't know any result like this.

Mind you, discussing semantic boundaries, like precisely counts as 'symmetry', is not very interesting to me. Far more interesting is: what can you do with fibrations of graphs in biology? I could say a bit about this sometime.

David wrote:

We know that a graph homomorphism is a fibration if and only if the functor induced between the respective free categories is a discrete fibration.

I believe it, but why do "we know" it? Is this some sort of well-known result?

David Corfield (Jul 12 2025 at 11:37):

Just a snatched moment.

That's one way of defining graph fibration as inducing a fibration on free categories.

John Baez (Jul 12 2025 at 11:46):

Okay, but who does that? The big book gives a more nuts-and-bolts definition of graph fibration (Definition 6.7) as a graph homomorphism such that blah-di-blah-di-blah. Do they give the more high-level definition somewhere?

Adittya Chaudhuri (Jul 12 2025 at 11:54):

John Baez said:

If every fibration $p: X \to Y$ gives rise to a groupoid, such that $p$ can be seen as 'modding out by the groupoid action', then I'll be very happy and I'll see how to understand fibrations as 'symmetry'. But I don't know any result like this.

The only partial result that I can think of:

Let $\pi \colon [E_1 \rightrightarrows E_0 ] \to [X_1 \rightrightarrows X_0 ]$ be a fibration of categories equipped with a splitting [[cleavage]] $C \colon E_0 \times_{\pi_0, X_0, t} X_1 \to Cart ({E_1})$, where $Cart ( {E_1})$ is the set of cartesian arrows in $E$ with respect to the functor $\pi$. Now, consider the category $\mathsf{Fib}(\pi)$,

• whose objects are fibres of $\pi_{0}$,
• morphisms are functions
• composition law is derived from the usual composition law of functions

Then, the map $C$ defines an action of the category $[X_1 \rightrightarrows X_0]$ on the set $E_0$ in the following sense:

• For every $\gamma \in X_1$, there is a function $\gamma^{*} \colon \pi_{0}^{-1}(t(\gamma)) \to \pi_{0}^{-1}(s(\gamma))$, which takes an object $p$ to the object $s \big( C(\gamma, p)\big)$.
• For every unit morphism $1_{p} \in X_1$, the function $1^{*}_{p}$ is identity
• For every composable pair of morphisms $\gamma_2, \gamma_1 \in X_1$, we have $\gamma_1^{*} \circ \gamma_2^{*}= (\gamma_2 \circ \gamma_1)*$

The last two conditions (above) should follow from the fact that $C$ is a splitting cleavage.

In otherwords, its a rewording of the fact that "contravariant functors correspond to the splitting fibrations". So, the above description defines a contravariant functor

$C^{*} \colon [X_1 \rightrightarrows X_0] \to \mathsf{Fib}(\pi)$

John Baez (Jul 12 2025 at 12:12):

The big book seems to be arguing that a fibration resembles a map $p: X \to X/G$ where $G$ is a group acting on a set, in that the quotient $X/G$ is a kind of 'simplified version' of $X$ where any two points related by a symmetry are identified. So it might interesting to see if anything along those lines can be turned into a theorem.

But I don't really care too much about whether graph fibrations are 'like symmetries'. I think the biological applications are more interesting.

Adittya Chaudhuri (Jul 12 2025 at 12:19):

I think given an action of a group $G$ on a set $X$, we can define an action groupoid $[X \times G \rightrightarrows X]$. Then, I think the natural projection map $\pi \colon [X \times G \rightrightarrows X] \to [G \rightrightarrows *]$ is a fibration of groupoids .

Adittya Chaudhuri (Jul 12 2025 at 12:22):

John Baez said:

The big book seems to be arguing that a fibration resembles a map $p: X \to X/G$ where $G$ is a group acting on a set, in that the quotient $X/G$ is a kind of 'simplified version' of $X$ where any two points related by a symmetry are identified. So it might interesting to see if anything along those lines can be turned into a theorem.

I see. I got your point!!

Adittya Chaudhuri (Jul 12 2025 at 12:22):

John Baez said:

But I don't really care too much about whether graph fibrations are 'like symmetries'. I think the biological applications are more interesting.

I agree.

Adittya Chaudhuri (Jul 12 2025 at 12:31):

Now, lets see what what happens if we assume David's definition of fibration of graphs , and apply the discussion in #theory: applied category theory > Networks in Biology @ 💬 :

I am assuming the following definition:

A homomorphism of graphs $\phi \colon G \to H$ is a called a graph fibration if $\mathsf{Free}(\phi) \colon \mathsf{Free}(G) \to \mathsf{Free}(H)$ is a discrete fibration.

Since, we are in the framework of discrete fibrations, we do not need to worry about cleavage, as the choice of cartesian lift is uniquely determined by the definition of discrete fibration. Also, note that discrete fibrations are splitting fibrations by deafault. Thus we can legitimately apply the above discussion to get a functor $\tau \colon \mathsf{Free}(H) \to \mathsf{Fib}(\mathsf{Free}(\phi))$.

John Baez (Jul 12 2025 at 12:33):

Adittya Chaudhuri said:

I think given an action of a group $G$ on a set $X$, we can define an action groupoid $[X \times G \rightrightarrows X]$. Then, I think the natural projection map $\pi \colon [X \times G \rightrightarrows X] \to [G \rightrightarrows *]$ is a fibration of groupoids .

Right, good point! But notice that this projection is doing something completely different from what the authors of that book are discussing: simplifying $X$ by identifying points in the same orbit. This is simplifying the action groupoid down to the group itself!

Adittya Chaudhuri (Jul 12 2025 at 12:35):

Thanks. I see. I got your point. I think I need to read the definition of fibration in that book in more detail.

John Baez (Jul 12 2025 at 12:37):

I think it's just a map of graphs s.t. the resulting map of free categories is a discrete fibration - but they say it a lot more slowly, since they're not using category theory.

Adittya Chaudhuri (Jul 12 2025 at 12:38):

Thanks. I see. But in that case, we may think of the following #theory: applied category theory > Networks in Biology @ 💬

Adittya Chaudhuri (Jul 12 2025 at 12:39):

However, I agree, at the moment my description is not "expressing" what you said here #theory: applied category theory > Networks in Biology @ 💬

John Baez (Jul 12 2025 at 12:40):

What I really want to think about is not this abstract nonsense but the five-step method of simplifying graphs explained in this paper:

Luis A. Álvarez-García, Wolfram Liebermeister, Ian Leifer and Hernán A. Makse, Complexity reduction by symmetry: uncovering the minimal regulatory network for logical computation in bacteria.

They seem to be using graphs (not even signed graphs???) as a way of describing a certain class of discrete possibilistic dynamical systems, but they don't spell this out clearly enough for me.

Adittya Chaudhuri (Jul 12 2025 at 12:42):

I got your point. I will read and try to understand their "5-step graph simplification method".

John Baez (Jul 12 2025 at 12:42):

By a discrete possibilistic dynamical system I mean a set $S$ together with a map $T$ from $S$ to its power set $P(S)$, which describes how each state (= element of $S$) can evolve to any state in the subset $T(\{s\})$.

Of course 'discrete possibilistic dynamical system' is just a silly name for a relation from a set to itself. But there's a nice analogy between probability theory and possibility theory, which this term is supposed to evoke. In probability theory we assign a number between 0 and 1 to each event, which tells us how probable that event is. In possibility theory we just assign either 0 or 1 to each event, which tells us whether that event is possible.

John Baez (Jul 12 2025 at 12:44):

If we replace the power set monad by the Giry monad, we get a discrete probabilistic dynamical system, where each state evolves to a probability distribution on states.

John Baez (Jul 12 2025 at 12:45):

I guess people usually say 'stochastic' instead of 'probabilistic' here, and similarly they say 'nondeterministic' instead of 'possibilistic'.

Adittya Chaudhuri (Jul 12 2025 at 12:47):

Thanks!! I see. I was not aware of these things. I will read on them. But I got the overall idea of them from the definitions that you wrote here.

John Baez (Jul 12 2025 at 12:51):

Anyway, the idea is simple: if we have (directed) graph, we say it's possible to go from node v to node w if there's an edge from v to w.

Adittya Chaudhuri (Jul 12 2025 at 12:52):

You said something called "possibility theory". Is it a separate branch of Math like Probability theory?

Adittya Chaudhuri (Jul 12 2025 at 12:54):

Or did you mean just "directed graphs" ?

John Baez (Jul 12 2025 at 12:54):

When I said directed graphs, I meant directed graphs. When I said possibility theory, I was referring to possibility theory:

... there's a nice analogy between probability theory and possibility theory, which this term is supposed to evoke. In probability theory we assign a number between 0 and 1 to each event, which tells us how probable that event is. In possibility theory we just assign either 0 or 1 to each event, which tells us whether that event is possible.

Adittya Chaudhuri (Jul 12 2025 at 12:55):

Sorry, I somehow missed that portion!! Thanks, I got the point now.

Adittya Chaudhuri (Jul 12 2025 at 12:58):

John Baez said:

Anyway, the idea is simple: if we have (directed) graph, we say it's possible to go from node v to node w if there's an edge from v to w.

Thanks. Now, I realised what you meant here.

Adittya Chaudhuri (Jul 12 2025 at 13:03):

John Baez said:

Anyway, the idea is simple: if we have (directed) graph, we say it's possible to go from node v to node w if there's an edge from v to w.

Why are we not considering "directed path" instead of a "directed edge" for this reachability condition?

Adittya Chaudhuri (Jul 12 2025 at 13:06):

David Corfield said:

You might be interested in Makse et al.'s ways of representing hypergraphs in the chapter where they extend fibrations to hypergraphs:

image.png

Yes. Thanks very much!!

John Baez (Jul 12 2025 at 13:08):

Adittya Chaudhuri said:

John Baez said:

Anyway, the idea is simple: if we have (directed) graph, we say it's possible to go from node v to node w if there's an edge from v to w.

Why are we not considering "directed path" instead of a "directed edge" for this reachability condition?

I was talking about a discrete possibilistic dynamical system: we can go from $v$ at time $t$ to $w$ at time $t+1$ if there's an edge from $v$ to $w$. This seems to be what that book is talking about. Their 5 methods of simplifying graphs are supposed to be motivated by simplifying their dynamical systems.

Adittya Chaudhuri (Jul 12 2025 at 13:09):

I see. Thanks.

David Corfield (Jul 12 2025 at 16:41):

John Baez said:

Okay, but who does that?

The big book has on p. 200:

image.png

John Baez (Jul 12 2025 at 16:47):

Okay, thanks! I'm glad they ultimately come clean and use category theory to define graph fibrations. Their presumably 'easier' approach earlier in the book is quite a slog for those of us blessed with knowledge of Grothendieck fibrations.

John Baez (Jul 12 2025 at 16:55):

It's interesting that they only consider graph morphisms $\phi : G \to H$, not the more general Kleisli morphisms that Adittya and I studied (which simply arbitrary functors $F : G^\ast \to H^\ast$ between the free categories on these graphs). A Kleisli morphism can send an edge of $G$ to a formal composite of edges of $H$. Kleisli morphisms are no good if one is considering each edge as taking one time step to traverse, as they sometimes seem to be thinking (e.g. when they're thinking of gene regulatory networks as synchronized processes.) But they're fine if one is not worried about time steps. Then you could say a Kleisli morphism between graphs is a fibration iff $F : G^\ast \to H^\ast$ is a fibration - i.e., it's a fibration iff its a fibration.

David Corfield (Jul 12 2025 at 17:02):

Regarding the issue of symmetry, I recall making considerable use of that Alan Weinstein paper Groupoids: unifying internal and external symmetry for my paper on groupoids, later Ch. 9 of my 2003 book. He considered there "local symmetries" of a tiled floor, so that there are several different kinds of point: outside corners, outside edge points, inside edge points, internal intersections, etc.

I think things are similar here in that one looks for local symmetries between nodes, though perhaps one further step is taken in that we're looking to relate nodes only in terms of isomorphic input trees. The activity of a node only depends on messages sent to it, not on what it sends.

Hence they define a network groupoid as follows:

image.png

This enables them to speak in a third way about the situation already described twice via fibrations and via balanced colorings. More on the translation is in

• Stewart, I. 2024. Groupoids, fibrations, and balanced colorings of networks. Internat. J.
  Bif. Chaos, 34, 2430014.

John Baez (Jul 12 2025 at 17:07):

Oh, thanks yet again! Do you know if they prove a theorem relating graph fibrations to these 'network groupoids' of graphs? In what I've read so far, they seem to be hinting at a relation, but I haven't seen them come out and say anything.

David Corfield (Jul 12 2025 at 17:12):

No doubt all is revealed in that Stewart 2024 article I just mentioned. Unfortunately for me it's behind a paywall.

John Baez (Jul 12 2025 at 17:13):

Okay, I'll bring my powers to bear on it.

Adittya Chaudhuri (Jul 12 2025 at 20:18):

Hi!! Below I am trying to clean up the relation (according to my understanding) between what they consider as fibrations and what I think as fibration and why they are relevant in their context. (By "them", I meant the authors of that "Big book").

Proposition:
The following are equivalent:

• (1) $\phi \colon G \to H$ is a homomorphism of graphs such that for each vertex $v$ in $G$, we have $\phi\big(G(-,v) \big) \cong H(-, \phi(v))$, where $G(-,v)$ is the set of edges in $G$ whose target is $v$ and $H(-, \phi(v))$ is the set of edges in $H$ whose target is $\phi(v)$. (It is their definition of fibrations (attached))
  fibrationofgraphs.png

  

• (2) $\phi \colon G \to H$ is a homomorphism of graphs such that for each edge $e$ in $H$ and a vertex $p \in \phi^{-1}(t(e))$, there is a unique edge $\bar{e}$ in $G$ such that $\phi(\bar{e})=e$ and $t(\bar{e})=p$ (Definition 1 in fibration of graphs)

• (3) $\phi \colon G \to H$ is a homomorphism of graphs such that $\mathsf{Free}(\phi) \colon \mathsf{Free}(G) \to \mathsf{Free}(H)$ is a discrete fibration of categories (in the sense of Grothendieck fibrations , as @David Corfield suggested)