Network Theory News

You may be wondering, somewhere deep in the back of your mind, what happened to the Network Theory series on this blog. It’s nowhere near done! I plan to revive it, since soon I’ll be teaching a seminar on network theory at U.C. Riverside. It will start in October and go on at least until the end of March.

Network Theory Seminar

I’ll be running a seminar on Network Theory on Mondays from 3:10 to 4:30 pm in Surge 268 starting on October 6th.

Network theory uses the tools of modern math—categories, operads and more—to study complex systems made of interacting parts. The idea of this seminar is to start from scratch, explain what my grad students have been doing, and outline new projects that they and other students might want to work on. A lot has happened since I left town in January.

I hope to see you there!

If you want more detail, here is a sketch of what’s been happening.

1) Franciscus Rebro has been working on “cospans”, a very general way to treat a physical system with inputs and outputs and treat it as a morphism in category. This underlies all the other projects.

2) Brendan Fong, a student of mine at Oxford, is working on a category where the morphisms are electrical circuits, and composing morphisms is sticking together circuits:

• Brendan Fong, A compositional approach to control theory.

• John Baez and Brendan Fong, A compositional framework for passive linear networks.

The first paper here is an outline of the project; the second one actually carries out the project, or at least a large chunk of it.

3) Blake Pollard, a student in the physics department, has been studying Markov processes. In a Markov process, things randomly hop from one vertex of a graph to another along edges. Blake has created a category where morphisms are ‘open’ Markov process, in which things flow in and out of certain special vertices called ‘terminals’.

4) Jason Erbele has been working on categories in control theory, the branch of math used to study physical systems that interact with the outside world via inputs and outputs. After finishing this paper:

• John Baez and Brendan Fong, Categories in control.

he’s been taking more concept from control theory and formalizing them using categories.

5) Oh yeah, and what about me? I gave a series of lectures on network theory at Oxford, and you can see videos of them here:

• John Baez, Network Theory.

Jacob Biamonte and I have also more or less finished a book on chemical reaction networks and Petri nets:

• John Baez and Jacob Biamonte, Quantum Techniques for Stochastic Mechanics.

But I won’t be talking about that; I want to talk about the new work my students are doing!

8 Responses to Network Theory News

1. Blake Stacey says:

Typo in the Baez–Biamonte book (p. 4):

We thank the readers of Azimuth for many helpful online discussions, inclluding David Corfield, Manoj Gopalkrishnan, Greg Egan and Blake Stacey, but also many others we apologize for not listing here.

• John Baez says:

Whoops! I fixed it.

One of the ‘many others’ I want to actually list here is Arjun Jain. He solved a lot of the puzzles, and Jacob and I need to add his solutions to the book.

He also did a lot of work on how the master equation reduces to the rate equation in the large-number (or ‘classical’) limit. I think it’s really cool that one can use Poisson brackets to describe the rate equation in chemistry, and that commutator brackets reduce to Poisson brackets in the large-number limit, as the master equation goes to the rate equation.

Today I want to post another article on that… and this too should be added to the book.

2. Hi John, inspirational stuff; I’m really looking forward to learning more more network theory on this blog!

It would be great to have you talk about this stuff next summer in Nijmegen, what do you say?

Also, I hope you don’t mind that I advertise some recent related work:

With Filippo Bonchi and Fabio Zanasi in Lyon, we have been taking a very similar network theoretic approach to talk about signal flow graphs, which are classical structures from control theory and engineering; they are often attributed to Mason circa 1950s, but interestingly, were actually discovered by Shannon, of information theory fame, during the war. The underlying mathematics is extremely interesting: we call it Interacting Hopf Algebras and, to cut a long story short, they are a very different language for talking about several classical concepts of linear algebra.

Here are some references:
F. Bonchi, P. Sobociński, F. Zanasi, A Categorical Semantics of Signal Flow Graphs, In CONCUR14, 2014 pdf

F. Bonchi, P. Sobocinski, F. Zanasi, Interacting Hopf Algebras
arxiv

We also have an upcoming paper:

F. Bonchi, P. Sobocinski, F. Zanasi, Full abstraction for Signal Flow Graphs, to appear in PoPL 15

in which we relate the categorical story with real state-machines that compute recurrence relations; e.g. of our examples is a state machine for the Fibonacci numbers.

• John Baez says:

Unfortunately I’ll be in Singapore this summer. I plan to talk about your work on signal flow graphs in my seminar, because it’s very closely connected to Jason’s work:

• John Baez and Jason Erbele, Categories in control.

and I’d like to synthesize them.

By the way, there’s a question I’ve been meaning to ask you. In your papers you sometimes describe PROPs using “generators and relations”. For example, Definitions 2–4 of Interacting Hopf algebras are what I’d call generators and relations descriptions of PROPs. When Jason did his oral exam one examiner quizzed him on the foundations of this topic—presentations of PROPs using generators and relations. We never found a good treatment of it in the literature, so we made up our own treatment for the paper. Do you know a good treatment?

There’s a rather sophisticated approach that uses the fact that PROPs are algebras of a multi-typed algebraic theory, and algebras of any algebraic theory can be presented using generators and relations. But we preferred to take an approach that uses less mathematical technology. This less stressful approach also deals with the fact that many symmetric monoidal categories arising in nature are equivalent to PROPs but are not technically PROPs. (They have a skeleton which is a PROP.)

I think I understand this subject well enough, but I’d prefer to cite a paper than do what we do now, namely to explain things ourselves.

• In short, no, I don’t know of any formal treatment. I have seen people referring to “free PROPs” is some papers so perhaps writing this out in full detail has been considered as obvious?

So we too have rolled our own: our approach explained more or less in our conference papers and will appear properly in a journal paper that we are currently preparing.

In general we take what may be considered a logical approach, in that we divide our PROPs into syntactic ones (ie those that are defined as the free PROP obtained from generators and relations — more on what this means below!) and semantic PROPs, ie those that are not defined in this way. We also try to be careful to use the term (one sorted) symmetric monoidal theory when talking about the syntactic case.

Now to explain what the “syntactic” case, ie the free PROP on generators G and relations R means formally. We consider the set T of terms generated from:

* the generators in G
* two “special” generators $\mathrm{id}:1 \to 1$ and the twist $\mathrm{tw}: 2 \to 2.$
* monoidal product $\otimes$ and the composition ; (the latter defined only when the numbers of ports match up!)

My favorite intuition/mental image is thinking of the generators together with the identity and twist as special Lego bricks that we can stack on top of another (monoidal product) and compose when the bricks fit. Of coarse, these are special Lego bricks that are stretchable.

Now if we just quotient this set of terms with respect to the axioms of symmetric monoidal categories (with the twist giving us the symmetry) the terms are now arrows of a PROP. Quotienting these with respect to the smallest congruence containing the relations gives us the free thing we were looking for.

Note that of course the syntactic/semantic terminology is all about presentation. One of Steve Lack’s first examples in the “Composing PROPs” paper is the “syntactic” PROP of commutative monoids, which of course is isomorphic to the “semantic” PROP of functions.

I hope that this clears things up somewhat!

• John Baez says:

Thanks! The ideas are all evident to me; what I really want are references to cite, so I don’t have to prove all the basic theorems myself!

For example:

There are a lot of basic theorems about presentations of groups (for example) which have analogues for PROPs. For example: every group has a presentation where all elements are generators, a homomorphism of groups is described in terms of presentations by any map sending generators of one to combinations of generators of the other that also sends relations to combinations of relations, etc. etc. All these results have been studied in considerable generality in universal algebra, both the old-fashioned Birkhoff-style universal algebra and the newer Lawvere style. And so, one should be able to simply cite these results and apply them to PROPs. In fact, since PROPs have been studied for many decades, someone should already have written a little paper stating all these results for PROPs, deriving them from more general results. Then I could just cite that little paper! But I haven’t found that paper yet.

And one problem is that a lot of work on universal algebra focuses on single-sorted algebraic structures, while PROPs, alas, are multi-sorted entities. This is true even for so-called ‘single-sorted’ PROPs! In a single-sorted PROP, for each $m, n \ge 0$ there is a set $P(m,n)$ of $m$-input, $n$-output operations. So, there are infinitely many sorts of operations. So, PROPs are algebras of a multi-sorted Lawvere theory, not a single-sorted Lawvere theory.

Anyway, I will probably try to publish our paper now as it was written, but if you write (or find) a paper that states the basic theorems about presentations for PROPs (some of which you just sketched), please let me know!

3. Ah now I see what you were looking for. If I find something then I will let you know — but I suspect that this “little paper” does not exist.

Apropos the historical work done on PROPs, to be honest I’m not aware of much done between Mac Lane’s original Categorical Algebra paper in the 1960s and a few papers in the early 2000s — although I have heard or read allusions to a PROP community; do you know anything about this?

• John Baez says:

In some sense the most important work on PROPs is Boardmann and Vogt’s 1973 book Homotopy Invariant Algebraic Structures on Topological Spaces, since this explained what they’re good for in algebraic topology, and singled out the special class of PROPS which Peter May later called ‘operads’ (namely, those generated by operations with just one output).

For a while operads sort of took over in algebraic topology, but PROPs became important again when algebraic topology met quantum field theory in the 1990s. For example, see these lecture notes:

• Alexander Voronov, Math 8390: Topics in Mathematical Physics , 2001.

That’s the highest course number I’ve ever seen! It makes me want to teach something like Math 10100.

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