Network Theory (Part 17)

joint with Jacob Biamonte

We’ve seen how Petri nets can be used to describe chemical reactions. Indeed our very first example came from chemistry:

However, chemists rarely use the formalism of Petri nets. They use a different but entirely equivalent formalism, called ‘reaction networks’. So now we’d like to tell you about those.

You may wonder: why bother with another formalism, if it’s equivalent to the one we’ve already seen? Well, one goal of this network theory program is to get people from different subjects to talk to each other—or at least be able to. This requires setting up some dictionaries to translate between formalisms. Furthermore, lots of deep results on stochastic Petri nets are being proved by chemists—but phrased in terms of reaction networks. So you need to learn this other formalism to read their papers. Finally, this other formalism is actually better in some ways!

Reaction networks

Here’s a reaction network:

This network involves 5 species: that is, different kinds of things. They could be atoms, molecules, ions or whatever: chemists call all of these species, and there’s no need to limit the applications to chemistry: in population biology, they could even be biological species! We’re calling them A, B, C, D, and E, but in applications, we’d call them by specific names like CO2 and HCO3–, or ‘rabbit’ and ‘wolf’, or whatever.

This network also involves 5 reactions, which are shown as arrows. Each reaction turns one bunch of species into another. So, written out more longwindedly, we’ve got these reactions:

A \to B

B \to A

A + C \to D

B + E \to A + C

B + E \to D

If you remember how Petri nets work, you can see how to translate any reaction network into a Petri net, or vice versa. For example, the reaction network we’ve just seen gives this Petri net:

Each species corresponds to a state of this Petri net, drawn as a yellow circle. And each reaction corresponds to transition of this Petri net, drawn as a blue square. The arrows say how many things of each species appear as input or output to each transition. There’s less explicit emphasis on complexes in the Petri net notation, but you can read them off if you want them.

In chemistry, a bunch of species is called a ‘complex’. But what do I mean by ‘bunch’, exactly? Well, I mean that in a given complex, each species can show up 0,1,2,3… or any natural number of times. So, we can formalize things like this:

Definition. Given a set S of species, a complex of those species is a function C: S \to \mathbb{N}.

Roughly speaking, a reaction network is a graph whose vertices are labelled by complexes. Unfortunately, the word ‘graph’ means different things in mathematics—appallingly many things! Everyone agrees that a graph has vertices and edges, but there are lots of choices about the details. Most notably:

• We can either put arrows on the edges, or not.

• We can either allow more than one edge between vertices, or not.

• We can either allow edges from a vertex to itself, or not.

If we say ‘no’ in every case we get the concept of ‘simple graph’, which we discussed last time. At the other extreme, if we say ‘yes’ in every case we get the concept of ‘directed multigraph’, which is what we want now. A bit more formally:

Definition. A directed multigraph consists of a set V of vertices, a set E of edges, and functions s,t: E \to V saying the source and target of each edge.

Given this, we can say:

Definition. A reaction network is a set of species together with a directed multigraph whose vertices are labelled by complexes of those species.

You can now prove that reaction networks are equivalent to Petri nets:

Puzzle 1. Show that any reaction network gives a Petri net, and vice versa.

In a stochastic Petri net each transition is labelled by a rate constant: that is, a numbers in [0,\infty). This lets us write down some differential equations saying how species turn into each other. So, let’s make this definition (which is not standard, but will clarify things for us):

Definition. A stochastic reaction network is a reaction network where each reaction is labelled by a rate constant.

Now you can do this:

Puzzle 2. Show that any stochastic reaction network gives a stochastic Petri net, and vice versa.

For extra credit, show that in each of these puzzles we actually get an equivalence of categories! For this you need to define morphisms between Petri nets, morphisms between reaction networks, and similarly for stochastic Petric nets and stochastic reaction networks. If you get stuck, ask Eugene Lerman for advice. There are different ways to define morphisms, but he knows a cool one.

We’ve been downplaying category theory so far, but it’s been lurking beneath everything we do, and someday it may rise to the surface.

The deficiency zero theorem

You may have already noticed one advantage of reaction networks over Petri nets: they’re quicker to draw. This is true even for tiny examples. For example, this reaction network:

2 X_1 + X_2 \leftrightarrow 2 X_3

corresponds to this Petri net:

But there’s also a deeper advantage. As we saw in Part 8, any stochastic Petri net gives two equations:

• The master equation, which says how the probability that we have a given number of things of each species changes with time.

• The rate equation, which says how the expected number of things in each state changes with time.

The simplest solutions of these equations are the equilibrium solutions, where nothing depends on time. Back in Part 9, we explained when an equilibrium solution of the rate equation gives an equilibrium solution of the master equation. But when is there an equilibrium solution of the rate equation in the first place?

Feinberg’s ‘deficiency zero theorem’ gives a handy sufficient condition. And this condition is best stated using reaction networks! But to understand it, we need to understand the ‘deficiency’ of a reaction network. So let’s define that, and they say what all the words in the definition mean:

Definition. The deficiency of a reaction network is:

• the number of vertices

minus

• the number of connected components

minus

• the dimension of the stoichiometric subspace.

The first two concepts here are easy. A reaction network is a graph (okay, a directed multigraph). So, it has some number of vertices, and also some number of connected components. Two vertices lie in the same connected component iff you can get from one to the other by a path where you don’t care which way the arrows point. For example, this reaction network:

has 5 vertices and 2 connected components.

So, what’s the ‘stoichiometric subspace’? ‘Stoichiometry’ is a scary-sounding word. According to the Wikipedia article:

‘Stoichiometry’ is derived from the Greek words στοιχεῖον (stoicheion, meaning element) and μέτρον (metron, meaning measure.) In patristic Greek, the word Stoichiometria was used by Nicephorus to refer to the number of line counts of the canonical New Testament and some of the Apocrypha.

But for us, stoichiometry is just the art of counting species. To do this, we can form a vector space \mathbb{R}^S where S is the set of species. A vector in \mathbb{R}^S is a function from species to real numbers, saying how much of each species is present. Any complex gives a vector in \mathbb{R}^S, because it’s actually a function from species to natural numbers.

Definition. The stoichiometric subspace of a reaction network is the subspace \mathrm{Stoch} \subseteq \mathbb{R}^S spanned by vectors of the form x - y where x and y are complexes connected by a reaction.

‘Complexes connected by a reaction’ makes sense because vertices in the reaction network are complexes, and edges are reactions. Let’s see how it works in our example:

Each complex here can be seen as a vector in \mathbb{R}^S, which is a vector space whose basis we can call A, B, C, D, E. Each reaction gives a difference of two vectors coming from complexes:

• The reaction A \to B gives the vector B - A.

• The reaction B \to A gives the vector A - B.

• The reaction A + C \to D gives the vector D - A - C.

• The reaction B + E \to A + C gives the vector A + C - B - E.

• The reaction B + E \to D gives the vector D - B - E.

The pattern is obvious, I hope.

These 5 vectors span the stoichiometric subspace. But this subspace isn’t 5-dimensional, because these vectors are linearly dependent! The first vector is the negative of the second one. The last is the sum of the previous two. And those are all the linear dependencies, so the stoichiometric subspace is 3 dimensional. For example, it’s spanned by these 3 linearly independent vectors: A - B, D - A - C, and D - B - E.

I hope you see the moral of this example: the stoichiometric subspace is the space of ways to move in \mathbb{R}^S that are allowed by the reactions in our reaction network! And this is important because the rate equation describes how the amount of each species changes as time passes. So, it describes a point moving around in \mathbb{R}^S.

Thus, if \mathrm{Stoch} \subseteq \mathbb{R}^S is the stoichiometric subspace, and x(t) \in \mathbb{R}^S is a solution of the rate equation, then x(t) always stays within the set

x(0) + \mathrm{Stoch} = \{ x(0) + y \colon \; y \in \mathrm{Stoch} \}

Mathematicians would call this set the coset of x(0), but chemists call it the stoichiometric compatibility class of x(0).

Anyway: what’s the deficiency of the reaction complex in our example? It’s

5 - 2 - 3 = 0

since there are 5 complexes, 2 connected components and the dimension of the stoichiometric subspace is 3.

But what’s the deficiency zero theorem? You’re almost ready for it. You just need to know one more piece of jargon! A reaction network is weakly reversible if whenever there’s a reaction going from a complex x to a complex y, there’s a path of reactions going back from y to x. Here the paths need to follow the arrows.

So, this reaction network is not weakly reversible:

since we can get from A + C to D but not back from D to A + C, and from B+E to D but not back, and so on. However, the network becomes weakly reversible if we add a reaction going back from D to B + E:

If a reaction network isn’t weakly reversible, one complex can turn into another, but not vice versa. In this situation, what typically happens is that as time goes on we have less and less of one species. We could have an equilibrium where there’s none of this species. But we have little right to expect an equilibrium solution of the rate equation that’s positive, meaning that it sits at a point x \in (0,\infty)^S, where there’s a nonzero amount of every species.

My argument here is not watertight: you’ll note that I fudged the difference between species and complexes. But it can be made so when our reaction network has deficiency zero:

Deficiency Zero Theorem (Feinberg). Suppose we are given a reaction network with a finite set of species S, and suppose its deficiency is zero. Then:

(i) If the network is not weakly reversible and the rate constants are positive, the rate equation does not have a positive equilibrium solution.

(ii) If the network is not weakly reversible and the rate constants are positive, the rate equation does not have a positive periodic solution, that is, a periodic solution lying in (0,\infty)^S.

(iii) If the network is weakly reversible and the rate constants are positive, the rate equation has exactly one equilibrium solution in each positive stoichiometric compatibility class.
Any sufficiently nearby solution that starts in the same stoichiometric compatibility class will approach this equilibrium as t \to +\infty. Furthermore, there are no other positive periodic solutions.

This is quite an impressive result. We’ll look at an easy example next time.

References and remarks

The deficiency zero theorem was published here:

• Martin Feinberg, Chemical reaction network structure and the stability of complex isothermal reactors: I. The deficiency zero and deficiency one theorems, Chemical Engineering Science 42 (1987), 2229–2268.

These other explanations are also very helpful:

• Martin Feinberg, Lectures on reaction networks, 1979.

• Jeremy Gunawardena, Chemical reaction network theory for in-silico biologists, 2003.

At first glance the deficiency zero theorem might seem to settle all the basic questions about the dynamics of reaction networks, or stochastic Petri nets… but actually, it just means that deficiency zero reaction networks don’t display very interesting dynamics in the limit as t \to +\infty. So, to get more interesting behavior, we need to look at reaction networks that don’t have deficiency zero.

For example, in biology it’s interesting to think about ‘bistable’ chemical reactions: reactions that have two stable equilibria. An electrical switch of the usual sort is a bistable system: it has stable ‘on’ and ‘off’ positions. A bistable chemical reaction can serve as a kind of biological switch:

• Gheorghe Craciun, Yangzhong Tang and Martin Feinberg, Understanding bistability in complex enzyme-driven reaction networks, PNAS 103 (2006), 8697-8702.

It’s also interesting to think about chemical reactions with stable periodic solutions. Such a reaction can serve as a biological clock:

• Daniel B. Forger, Signal processing in cellular clocks, PNAS 108 (2011), 4281-4285.

This entry was posted on Saturday, November 12th, 2011 at 6:30 am and is filed under biology, mathematics, networks. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

31 Responses to Network Theory (Part 17)

  1. Blake Stacey says:
    12 November, 2011 at 2:22 pm

    Quick observation: a couple instances of “infty” should be “\infty”.

    But we have little right to expect an equilibrium solution of the rate equation that’s positive, meaning that it sits at a point x \in (0,\infty)^S, where there’s a nonzero amount of every species.

    And

    (ii) If the network is not weakly reversible and the rate constants are positive, the rate equation does not have a positive periodic solution, that is, a periodic solution lying in (0,\infty)^S.

    Will read more closely now.

    Reply
  2. Matt McIrvin says:
    12 November, 2011 at 3:58 pm

    I think I don’t understand the Petri net for the ABCDE example at all. Where is C? Does the transition on the left have no outputs?

    Reply
  3. David Corfield says:
    12 November, 2011 at 4:51 pm

    Is there a whiff of Euler characteristic/homology going on with that definition of the deficiency of a reaction complex?

    Reply
    • John Baez says:
      13 November, 2011 at 2:44 am

      Yes there is! I was wondering if you’d ask. I’m still a bit confused, but here’s where am I now.

      Suppose first that all the reactions x \to y give linearly independent elements x - y \in \mathbb{R}^S. Then the dimension of the stoichiometric subspace is the number of edges of the reaction complex. Then the deficiency of the reaction network is

      • (number of components) + (number of vertices) – (number of edges)

      This should remind you a lot of the Euler characteristic of a simplicial complex:

      (number of vertices) – (number of edges) + (number of triangles) – …

      namely the alternating sum of the numbers of simplices of various dimensions.

      But what about the components? Well, if you remember the relation between the category of simplices, \Delta, and the category of totally ordered finite sets, you’ll remember it’s a bit funny: the n-dimensional simplex corresponds to the set with n+1 elements. So, the empty set corresponds to a (-1)-dimensional simplex! Mathematicians often ignore these (-1)-dimensional simplices, but not always… and if we start with any simplicial complex, we can introduce (-1)-dimensional simplices by defining them to be connected components.

      If we do this, we get a modified concept of Euler characteristic for a simplicial complex, given by:

      • (number of components) + (number of vertices) – (number of edges) + (number of triangles) – …

      Does anyone think about this? Maybe it’s the Euler characteristic in ‘reduced homology’???

      Anyway, the deficiency of a reaction complex is this concept, specialized to graphs, but then generalized to a context where we can talk about ‘linearly dependent’ edges of a graph: instead of just counting the edges, we count the dimension of the space they span! This is this stoichiometric subspace.

      I’m not sure what this means yet.

      Reply
      • David Corfield says:
        13 November, 2011 at 4:06 pm

        Interesting! Of course, one place where ‘deficiency’ turns up is as a synonym of defect, as in angular defect. Could there be a link to Descartes’ theorem and whether a space is hyperbolic, elliptic, etc.?

        Reply
      • David Corfield says:
        15 November, 2011 at 9:55 am

        In the context of the Euler characteristic, your talk of cosets put me in mind of thinking of this situation in terms of a flow on a state space, with the whole apparatus of initial conditions, orbits, equilibria, vector field, indices, etc.

        Hmm, what was the joke back here:

        I’d feel duty-bound to commit hara-kiri if I weren’t describing a functor from the groupoid of stochastic Petri nets to the groupoid of ‘vector spaces equipped with vector field’.

        Reply
        • Eugene Lerman says:
          15 November, 2011 at 7:50 pm

          David,

          There is a functor from a category of stochastic Petri nets to the category of polynomial dynamical systems (polynomial vector fields on finite dimensional vector spaces).

          I can send you a rough draft of the construction, if you are interested.

        • John Baez says:
          16 November, 2011 at 4:13 am

          David wrote:

          Your talk of cosets put me in mind of thinking of this situation in terms of a flow on a state space, with the whole apparatus of initial conditions, orbits, equilibria, vector field, indices, etc.

          Right, the ‘rate equation’ of a stochastic Petri net is a dynamical system, so we get to use all these concepts.

          I get the feeling you’re trying to tell me to set up a relationship between these two results:

          • the theorem saying any vector field on a compact manifold of nonzero Euler characteristic must vanish somewhere, so the dynamical system it determines must have an equilibrium solution.

          • the theorem saying any weakly reversible reaction network of deficiency zero gives a rate equation with an equilibrium solution.

          I’d like to relate these! As I mentioned, “deficiency” is related to “Euler characteristic”, so that’s good. But there are a couple of problems I don’t see how to overcome.

          The obvious one is that the first result talks about nonzero Euler characteristic, while the second talks about zero deficiency. So things seem exactly backward!

          The less obvious one is that the rate equation of a reaction network gives a dynamical system on [0,\infty)^n, which is noncompact and always has Euler characteristic zero. I don’t see how to relate the deficiency of the reaction network to the Euler characteristic of some compact manifold!

          I think the first step would be for me to understand the proof of Feinberg’s deficiency zero theorem, which is a good thing to do even if the above thoughts are completely misguided.

        • John Baez says:
          16 November, 2011 at 4:27 am

          Eugene wrote:

          There is a functor from a category of stochastic Petri nets to the category of polynomial dynamical systems (polynomial vector fields on finite dimensional vector spaces).

          This of course is part of what I was advertising when I said:

          For this you need to define morphisms between Petri nets, morphisms between reaction networks, and similarly for stochastic Petric nets and stochastic reaction networks. If you get stuck, ask Eugene Lerman for advice. There are different ways to define morphisms, but he knows a cool one.

          If you get the draft to the point where you don’t mind showing it to the world, I’d love to blog about it here!

          By the way, we should work out a time for you to visit and work on this stuff. Sometime in May or June or July or August next year would be good… I won’t return to California until late August or September. However, Tom Leinster is running a program on the mathematics of biodiversity at CRM in Barcelona from June 18 to July 20, and I want to attend some of that. Unfortunately working out the precise dates involves negotiations with my wife, which is the kind of thing we tend to put off. And she just got invited to spend a bunch of time in Paris next summer, which adds an extra layer of complexity to this process.

        • David Corfield says:
          16 November, 2011 at 8:54 am

          Eugene,
          Sure I’d like to see that draft.

          John,
          Yes, a few hurdles to jump before a connection is made. There seems to be the added difference that there’s an equilibrium point for every coset, so there could be a subspace of equilibria.

          How about the very simple Petri net with two species, where A transforms to B at rate r, and B transforms to A at rate s. So cosets are diagonal lines of gradient -1. For each coset there’s an equilibrium point on the line through the origin with gradient s/r.

          Hmm, I wonder if the conditions in the theorem are forcing the cosets to remain bounded.

  4. Manoj Gopalkrishnan says:
    12 November, 2011 at 6:08 pm

    Glad to see this post, John! A very trivial comment that I’m almost ashamed for making: there’s an extra “i” in “stoichiometric.” I’m eagerly looking forward to future posts on this topic from you.

    Reply
    • John Baez says:
      13 November, 2011 at 2:11 am

      Whoops! Don’t be ashamed, I’m a spelling perfectionist (my dad was an editor), so if I misspell something, I want to hear about it.

      Maybe it’ll help if I look up the etymology:

      ‘Stoichiometry’ is derived from the Greek words στοιχεῖον (stoicheion, meaning element]) and μέτρον (metron, meaning measure.) In patristic Greek, the word Stoichiometria was used by Nicephorus to refer to the number of line counts of the canonical New Testament and some of the Apocrypha.

      Reply
  5. Jacob Biamonte says:
    13 November, 2011 at 1:57 pm

    Just to remind everyone, as John often has, the full network series is available here:

    http://math.ucr.edu/home/baez/networks/networks.html

    Reply
    • Eugene Lerman says:
      15 November, 2011 at 6:45 pm

      except for part 17 as of the time of this comment

      Reply
      • John Baez says:
        16 November, 2011 at 4:01 am

        Yes, I’m often one behind. The WordPress blog uses a different style of LaTeX than the jsmath used on my website, so I have to work to turn one into the other, which is the sort of task I save for a rainy day.

        Luckily in Singapore it rains almost every day.

        Reply
  6. Eugene Lerman says:
    16 November, 2011 at 8:23 pm

    One general comment about Puzzles 1 and 2 (let’s see if I can successfully put a foot in my mouth again).

    It seems to me that both Petri nets and reaction networks both encode directed hypergraphs. Any hypergraph can be coded by a Petri net – put a transition for every hyperedge, a place for every element of the hyperedge, an arrow from a place to the transition if the place is an element of the tail (source) of hyperedge and an arrow from the transition to a place if the place is an element of the head (target) of the hyperedge.

    Conversely given a Petri net, for every transition form a hyperedge whose tail is the set of places with arrows to the transition and whose target is the set of places with arrows out of the transition.

    It is also easy to write a dictionary between between reaction networks and hypergraphs: a hyperedge is a reaction from the complex formed by the tail of the hyperedge to the complex formed by the head of the hyperedge.

    Reply
    • John Baez says:
      17 November, 2011 at 12:43 am

      All that sounds good. We can also remember this from Part 3:

      By the way: if you’re a category theorist, when I said “turn around all the arrows” you probably thought “opposite category”. And you’d be right! A Petri net is just a way of presenting a strict symmetric monoidal category that’s freely generated by some objects (the states) and some morphisms (the transitions). For more details, try:

      • Vladimiro Sassone, On the category of Petri net computations, 6th International Conference on Theory and Practice of Software Development, Proceedings of TAPSOFT ’95, Lecture Notes in Computer Science 915, Springer, Berlin, pp. 334-348.

      So, to specify a Petri net we first give a set of objects called states:

      S = \{A_1, \dots, A_n\}

      and then a set of generating morphisms called transitions:

      T = \{ f_1, \dots, f_m\}

      where each f_i goes from some tensor product of states to some other tensor product of states. This data determines a strict monoidal category, say C.

      To specify a reaction network we do the exact same thing! Now, however, the states are called species and the morphisms are called reactions.

      Note that every object of C is isomorphic to exactly one of the form

      A_1^{\otimes k_1} \otimes \cdots \otimes A_n^{\otimes k_n}

      so C is equivalent to a ‘skeleton’ where these are the only objects. The set of objects of this skeleton is just \mathbb{N}^S. In the literature on reaction networks, \mathbb{N}^S is called the set of complexes.

      By the way, I’ve been acting as if S and T are finite, and people often assume that, since we need it to prove certain theorems—but we don’t really need it in anything I just said. There are also important examples where S and T are infinite. For example, in ‘stochastic Petri net field theories’ we might take S = \mathbb{Z}^k to be a lattice. Mathematical biologists can use this to describe animals moving around in space. Blake Stacey may tell us more about these sometime; he’s already shown us lots of references.

      To get a stochastic Petri net, we let X be the symmmetric monoidal category with one object and [0,\infty) as morphisms, where composition and tensoring of morphisms are both given by multiplication. Then a stochastic Petri net is a strict symmetric monoidal functor

      r : C \to X

      Since C is freely generated by some objects and morphisms, all \tau does is assign an arbitrary number 0 \le r(f) < \infty to each transition f \in T. This number is called the rate of that transition.

      The same is true for stochastic reaction networks; there’s no real difference!

      I don’t know much about hypergraphs. But if I understand what you said, we can think of a directed hypergraph as a presentation of a free strict symmetric monoidal category, just as we can think of a directed graph, as a presentation of a free category.

      When people use a directed graph to present a free category C, they call the directed graph a ‘quiver’. A representation of this quiver is then a functor \tau : C \to \mathrm{Vect}. Since C is free these functors are easy to describe. We’re doing something similar now except we’re working with symmetric monoidal categories, which are a bit more complicated, but replacing \mathrm{Vect} by X, which is simpler.

      Reply
      • Eugene Lerman says:
        17 November, 2011 at 9:38 pm

        Thanks! I need to think about what you said. I am not very comfortable with hypergraphs either, and different sources seem to use slightly different definitions. In particular some authors order the vertices of the source and target of a hyperedge and others don’t, which confuses me. Are places in Petri nets orderd? It seems that they should be… Hmm.

        Reply
      • John Baez says:
        18 November, 2011 at 2:11 am

        Eugene wrote:

        Are places in Petri nets orderd? It seems that they should be… Hmm.

        I’ve been calling them ‘states’ or ‘species’ and calling the set of them S.

        You’ve got an interesting point there! S is not ordered according to any definition I’ve seen or used: my definition, one of the standard ones, is this:

        Definition. A Petri net consists of a set S of states and a set T of transitions, together with a function
        i : S \times T \to \mathbb{N}
        saying how many copies of each state shows up as input for each transition, and a function
        o: S \times T \to \mathbb{N}
        saying how many times it shows up as output.

        But if you’re using states and transitions as objects and morphisms of a symmetric monoidal categories you might want an order on the states that appear as inputs or outputs to a transition. Why? In a symmetric monoidal category A \otimes B \ne B \otimes A; all we’ve got is a chosen isomorphism A \otimes B \cong B \otimes A, the ‘braiding’. So, turning a transition into a morphism

        f: A \otimes B \otimes C \otimes \cdots \to X \otimes Y \otimes Z \otimes \cdots

        requires that we choose an ordering for the states (objects) showing up in this expression.

        However, right now I actually think the way people are doing things is acceptable, if perhaps suboptimal in some ways. If we’re using the states and transitions to generate a free strict symmetric monoidal category, we need to choose a bunch of orderings to turn the transitions into well-defined morphisms and get a symmetric monoidal category. However, a different choice of orderings gives an isomorphic symmetric monoidal category, and this isomorphism is canonical.

        There’s also a concept of ‘commutative’ monoidal category where the braiding is the identity and thus A \otimes B = B \otimes A. Normally these are evil, but sometimes they’re okay! They’re important in algebraic geometry, for example.

        In my post I talked a lot about the set of complexes, \mathbb{N}^S. This is the free commutative monoid on the set S, at least when S is finite. And this free commutative monoid is the set of objects in the free commutative monoidal category on our states and transitions!

        So, I was almost tempted to use commutatve monoidal categories. I’d feel okay about this if the free commutative monoidal category on some states (objects) and transitions (morphisms) were equivalent to the free strict symmetric monoidal category on that data. But just while writing this I think I’ve seen they’re not.

        And while we’re talking about ‘evil’, of course strict symmetric monoidal categories are also a bit evil. However, my hunch is that the free strict symmetric monoidal category on some objects and morphisms is equivalent to the free weak symmetric monoidal category on that data. If so, we can use strict ones without being punished by the math gods.

        Reply
  7. Eugene Lerman says:
    18 November, 2011 at 4:31 pm

    I think the categorical gadget which is most natural in this context is a “path category” of a directed hypergraph. I am not convinced yet that this “path category” will end up being a symmetric monoidal category of some sort. It may be equivalent to some flavor of such category, but let’s not rush things.

    But what’s a directed hypergraph? The wikipedia seems only to define undirected hypergraphs. The definition in Directed hypergraphs and applications does not seem suitable. David Spivak gives two definitions in Higher-dimensional models of networks. One orders the vertices. The other doesn’t order them but does not allow repetitions of vertices ether. Neither of Spivak’s definition (which have the advantage of being presheaves) quite fit our needs.

    Here is a proposal of a definition of a hypergraph H associated with the sets S of species and T of transitions: H is a pair of maps source, target from the set of transitions T to the set of complexes \mathbb{N}^S. Hmm, I guess I just defined a reaction network.

    I am not sure how to define paths of such a hypergraph. You could just look at paths in the reaction network graph. But it doesn’t feel optimal (maybe it would if I had more sleep). What looks right is made up of paths of length 4 starting (and ending) at species in the corresponding Petri net. I have trouble being articulate.

    Reply
    • John Baez says:
      19 November, 2011 at 3:04 am

      Eugene wrote:

      … let’s not rush things.

      It’s not rushing things for me to say: a reaction network, or Petri net, is a presentation of a symmetric monoidal category. The morphisms in this category are the ‘Feynman diagrams’ I’ve been drawing, like this:

      If this isn’t true, then I’ll tweak the definition of Petri net until it is! The whole point of my research here is to show how various kinds of ‘networks’ in applied math are related to various kinds of symmetric monoidal categories. I started with Petri nets because they play a basic role: they let us describe a symmetric monoidal category generated by some objects (things) and morphisms (processes).

      Concepts like ‘hypergraph’ may be a bit fidgety and ad hoc: I listed 8 different concepts of ‘graph’ and there could be more for ‘hypergraph’. But the concept of symmetric monoidal category is inevitable as soon as you ponder a bunch of things that can interact and also trade places (without getting tangled up). So that’s solid bedrock, as far as I’m concerned. And the connection to Petri nets is discussed here:

      • Vladimiro Sassone, On the category of Petri net computations, 6th International Conference on Theory and Practice of Software Development, Proceedings of TAPSOFT ’95, Lecture Notes in Computer Science 915, Springer, Berlin, pp. 334-348.

      I’m sorry if I sound a bit fierce, but this is my core philosophy. Other approaches are of course worth exploring, but this is mine.

      Reply
      • Eugene Lerman says:
        19 November, 2011 at 2:11 pm

        It is a fierce comment. Since I don’t know what you know, I don’t see what you see. I do want to understand why you believe what you believe, hence the questions and musings. My comments are not meant as a challenge.

        I tried looking at Sassone’s paper when you first linked to it months ago. It feels like I don’t have the background to understand it. I am hoping you plan to explain it here at some point.

        But the concept of symmetric monoidal category is inevitable as soon as you ponder a bunch of things that can interact and also trade places (without getting tangled up).

        This is a bit like sayng the concept of a stack is inevitable as soon as you ponder orbifolds and their maps. I have pondered systems things that interact and can trade places. And I see answers that don’t look like symmetric monoidal categories.

        There is the groupoid formalism for coupled cell networks of Golubitsky, Stewart and their collaborators, where trading places is modeled as a groupoid symmetry of interactions.

        Recently a colleague of mine in engineering got me thinking about hybrid systems. While these kinds of systems are related to directed graphs, they are rather different from what people normally call dynamics on networks. In dynamics on networks, phase spaces are products. In hybrid systems phase spaces are nonlinear quivers (diagrams in an appropriate category of phase spaces). The dynamics is nondeterminsitic.

        Reply
  8. Network Theory (Part 18) « Azimuth says:
    21 November, 2011 at 7:07 am

    […] Last time we explained how ‘reaction networks’, as used in chemistry, are just another way of talking about Petri nets. We stated an amazing result on reaction networks: Feinberg’s deficiency zero theorem. This settles quite a number of questions about chemical reactions. Now let’s illustrate it with an example. […]

    Reply
  9. Arjun Jain says:
    3 June, 2013 at 8:44 pm

    Why are you referring to the deficiency as that of a reaction complex, rather than that of a reaction network?

    Reply
  10. Quantum Theory and Complex Networks – QuamPlexity.org says:
    24 April, 2016 at 6:17 pm

    […] Reaction networks versus Petri nets; the deficiency zero theorem, Network Theory Part 17  […]

    Reply

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.