guest post by Eugene Lerman
Hi, I’m Eugene Lerman. I met John back in the mid 1980s when John and I were grad students at MIT. John was doing mathematical physics and I was studying symplectic geometry. We never talked about networks. Now I teach in the math department at the University of Illinois at Urbana, and we occasionally talk about networks on his blog.
A few years ago a friend of mine who studies locomotion in humans and other primates asked me if I knew of any math that could be useful to him.
I remember coming across an expository paper on ‘coupled cell networks':
• Martin Golubitsky and Ian Stewart, Nonlinear dynamics of networks: the groupoid formalism, Bull. Amer. Math. Soc. 43 (2006), 305–364.
In this paper, Golubitsky and Stewart used the study of animal gaits and models for the hypothetical neural networks called ‘central pattern generators’ that give rise to these gaits to motivate the study of networks of ordinary differential equations with symmetry. In particular they were interested in ‘synchrony’. When a horse trots, or canters, or gallops, its limbs move in an appropriate pattern, with different pairs of legs moving in synchrony:
They explained that synchrony (and the patterns) could arise when the differential equations have finite group symmetries. They also proposed several systems of symmetric ordinary differential equations that could generate the appropriate patterns.
Later on Golubitsky and Stewart noticed that there are systems of ODEs that have no group symmetries but whose solutions nonetheless exhibit certain synchrony. They found an explanation: these ODEs were ‘groupoid invariant’. I thought that it would be fun to understand what ‘groupoid invariant’ meant and why such invariance leads to synchrony.
I talked my colleague Lee DeVille into joining me on this adventure. At the time Lee had just arrived at Urbana after a postdoc at NYU. After a few years of thinking about these networks Lee and I realized that strictly speaking one doesn’t really need groupoids for these synchrony results and it’s better to think of the social life of networks instead. Here is what we figured out—a full and much too precise story is here:
• Eugene Lerman and Lee DeVille, Dynamics on networks of manifolds.
Let’s start with an example of a class of ODEs with a mysterious property:
Example. Consider this ordinary differential equation for a function
for some function It is easy to see that a function solving
gives a solution of these equations if we set
You can think of the differential equations in this example as describing the dynamics of a complex system built out of three interacting subsystems. Then any solution of the form
may be thought of as a synchronization: the three subsystems are evolving in lockstep.
One can also view the result geometrically: the diagonal
is an invariant subsystem of the continuous-time dynamical system defined by the differential equations. Remarkably enough, such a subsystem exists for any choice of a function
Where does such a synchronization or invariant subsystem come from? There is no apparent symmetry of that preserves the differential equations and fixes the diagonal and thus could account for this invariant subsystem. It turns out that what matters is the structure of the mutual dependencies of the three subsystems making up the big system. That is, the evolution of depends only on and the evolution of depends only on and and the evolution of depends only on and
These dependencies can be conveniently pictured as a directed graph:
The graph has no symmetries. Nonetheless, the existence of the invariant subsystem living on the diagonal can be deduced from certain properties of the graph The key is the existence of a surjective map of graphs
from our graph to a graph with exactly one node, call it and one arrow. It is also crucial that has the following lifting property: there is a unique way to lift the one and only arrow of to an arrow of once we specify the target node of the lift.
We now formally define the notion of a ‘network of phase spaces’ and of a continuous-time dynamical system on such a network. Equivalently, we define a ‘network of continuous-time dynamical systems’. We start with a directed graph
Here is the set of edges, is the set of nodes, and the two arrows assign to an edge its source and target, respectively. To each node we attach a phase space (or more formally a manifold, perhaps with boundary or corners). Here ‘attach’ means that we choose a function it assigns to each node a phase space
In our running example, to each node of the graph we attach the real line (If we think of the set as a discrete category and as a category of manifolds and smooth maps, then is simply a functor.)
Thus a network of phase spaces is a pair where is a directed graph and is an assignment of phase spaces to the nodes of
We think of the collection as the collection of phase spaces of the subsystems constituting the network We refer to as a phase space function. Since the state of the network should be determined completely and uniquely by the states of its subsystems, it is reasonable to take the total phase space of the network to be the product
In the example the total phase space of the network is while the phase space of the network is the real line
Finally we need to interpret the arrows. An arrow in a graph should encode the fact that the dynamics of the subsystem associated to the node depends on the states of the subsystem associated to the node To make this precise requires the notion of an ‘open system’, or ‘control system’, which we define below. It also requires a way to associate an open system to the set of arrows coming into a node/vertex
To a first approximation an open system (or control system, I use the two terms interchangeably) is a system of ODEs depending on parameters. I like to think of a control system geometrically: a control system on a phase space controlled by the the phase space is a map
where is the tangent bundle of the space so that for all is a vector tangent to at the point Given phase spaces and the set of all corresponding control systems forms a vector space which we denote by
(More generally one can talk about the space of control systems associated with a surjective submersion For us, submersions of the form are general enough.)
To encode the incoming arrows, we introduce the input tree (this is a very short tree, a corolla if you like). The input tree of a node of a graph is a directed graph whose arrows are precisely the arrows of coming into the vertex but any two parallel arrows of with target will have disjoint sources in In the example the input tree of the one node of of is the tree
There is always a map of graphs For instance for the input tree in the example we just discussed, is the map
Consequently if is a network and is an input tree of a node of then is also a network. This allows us to talk about the phase space of an input tree. In our running example,
Given a network there is a vector space of open systems associated with every node of
In our running example, the vector space associated to the one node of is
In the same example, the network has three nodes and we associate the same vector space to each one of them.
We then construct an interconnection map
from the product of spaces of all control systems to the space of vector fields
on the total phase space of the network. (We use the standard notation to denote the tangent bundle of a manifold by and the space of vector fields on by ). In our running example the interconnection map for the network is the map
The interconnection map for the network is the map
To summarize: a dynamical system on a network of phase spaces is the data where is a directed graph, is a phase space function and is a collection of open systems compatible with the graph and the phase space function. The corresponding vector field on the total space of the network is obtained by interconnecting the open systems.
Dynamical systems on networks can be made into the objects of a category. Carrying this out gives us a way to associate maps of dynamical systems to combinatorial data.
The first step is to form the category of networks of phase spaces, which we call In this category, by definition, a morphism from a network to a network is a map of directed graphs which is compatible with the phase space functions:
Using the universal properties of products it is easy to show that a map of networks defines a map of total phase spaces in the opposite direction:
In the category theory language the total phase space assignment extends to a contravariant functor
We call this functor the total phase space functor. In our running example, the map
is given by
Continuous-time dynamical systems also form a category, which we denote by The objects of this category are pairs consisting of a phase space and a vector field on this phase space. A morphism in this category is a smooth map of phase spaces that intertwines the two vector fields. That is:
for any pair of objects in
In general, morphisms in this category are difficult to determine explicitly. For example if then a morphism from to some dynamical system is simply a piece of an integral curve of the vector field defined on an interval And if is the constant vector field on the circle then a morphism from to is a periodic orbit of Proving that a given dynamical system has a periodic orbit is usually hard.
Consequently, given a map of networks
and a collection of open systems
on we expect it to be very difficult if not impossible to find a collection of open systems so that
is a map of dynamical systems.
It is therefore somewhat surprising that there is a class of maps of graphs for which the above problem has an easy solution! The graph maps of this class are known by several different names. Following Boldi and Vigna we refer to them as graph fibrations. Note that despite what the name suggests, graph fibrations in general are not required to be surjective on nodes or edges. For example, the inclusion
is a graph fibration. We say that a map of networks
is a fibration of networks if is a graph fibration. With some work one can show that a fibration of networks induces a pullback map
on the sets of tuples of the associated open systems. The main result of Dynamics on networks of manifolds is a proof that for a fibration of networks the maps and the two interconnection maps and are compatible:
Theorem. Let be a fibration of networks of manifolds. Then the pullback map
is compatible with the interconnection maps
Namely for any collection of open systems on the network the diagram
commutes. In other words,
is a map of continuous-time dynamical systems, a morphism in
At this point the pure mathematician in me is quite happy: I have a theorem! Better yet, the theorem solves the puzzle at the beginning of this post. But if you have read this far, you may well be wondering: “Ok, you told us about your theorem. Very nice. Now what?”
There is plenty to do. On the practical side of things, the continuous-time dynamical systems are much too limited for contemporary engineers. Most of the engineers I know care a lot more about hybrid systems. These kinds of systems exhibit both continuous time behavior and abrupt transitions, hence the name. For example, anti-lock breaks on a car is just that kind of a system — if a sensor detects that the car is skidding and the foot break is pressed, it starts pulsing the breaks. This is not your father’s continuous time dynamical system! Hybrid dynamical systems are very hard to understand. They have been all the rage in the engineering literature for the last 10-15 years. Sadly, most pure mathematicians never heard of them. It would be interesting to extend the theorem I am bragging about to hybrid systems.
Here is another problem that may be worth thinking about: how much of the theorem holds up to numerical simulation? My feeling is that any explicit numerical integration method will behave well. Implicit methods I am not sure about.
And finally a more general issue. John has been talking about networks quite a bit on this blog. But his networks and my networks look like very different mathematical structures. What do they have in common besides nodes and arrows? What mathematical structure are they glimpses of?