I’m excited! In early December I’m going to a workshop on ‘compositionality’, meaning how big complex things can be built by sticking together smaller, simpler parts:
• Compositionality, 5-9 December 2016, workshop at the Simons Institute for the Theory of Computing, Berkeley. Organized by Samson Abramsky, Lucien Hardy and Michael Mislove.
In 2007 Jim Simons, the guy who helped invent Chern–Simons theory and then went on to make billions using math to run a hedge fund, founded a research center for geometry and physics on Long Island. More recently he’s also set up this institute for theoretical computer science, in Berkeley. I’ve never been there before.
‘Compositionality’ sounds like an incredibly broad topic, but since it’s part of a semester-long program on Logical structures in computation, this workshop will be aimed at theoretical computer scientists, who have specific ideas about compositionality. And these theoretical computer scientists tend to like category theory. After all, category theory is about morphisms, which you can compose.
Here’s the idea:
The compositional description of complex objects is a fundamental feature of the logical structure of computation. The use of logical languages in database theory and in algorithmic and finite model theory provides a basic level of compositionality, but establishing systematic relationships between compositional descriptions and complexity remains elusive. Compositional models of probabilistic systems and languages have been developed, but inferring probabilistic properties of systems in a compositional fashion is an important challenge. In quantum computation, the phenomenon of entanglement poses a challenge at a fundamental level to the scope of compositional descriptions. At the same time, compositionally has been proposed as a fundamental principle for the development of physical theories. This workshop will focus on the common structures and methods centered on compositionality that run through all these areas.
So, some physics and quantum computation will get into the mix!
A lot of people working on categories and computation will be at this workshop. Here’s what I know about the talks so far. If you click on the talk titles you’ll get abstracts, at least for most of them.
The program
| 9 – 9:30 am |
Coffee and Check-In
|
|
| 9:30 – 10:30 am | ||
| 10:30 – 11 am |
Break
|
|
| 11 – 11:20 am | ||
| 11:25 – 11:45 am | ||
| 11:50 am – 12:25 pm | ||
| 12:30 – 2 pm |
Lunch
|
| 9:30 – 10:05 am | ||
| 10 am – 10:45 am | ||
| 10:50 – 11:20 am |
Break
|
|
| 11:20 – 11:55 am | ||
| 12 – 12:35 pm | ||
| 12:40 – 2 pm |
Lunch
|
|
| 2 – 3 pm |
Discussion
|
|
| 3 – 3:40 pm |
Posted by John Baez 
This has two terminals—the two ends of the resistor—and at each terminal, we may measure the potential and the current. Thus the universum of this system is the set 
where the summands represent respectively the potentials and currents at each of the two terminals. The resistor is governed by Kirchhoff’s current law, or conservation of charge,
Thus the behaviour of the resistor is the set
with extra structure. Our motivating example is cospans of finite sets decorated by graphs, as in this picture:
be a category with finite colimits, writing its as coproduct as 
and let 
be a braided monoidal category. Decorated cospans provide a method of producing a hypergraph category from a lax braided monoidal functor
while the morphisms are pairs comprising a cospan 
in 
in 
—the so-called decoration. We will also describe how to construct hypergraph functors between decorated cospan categories. In particular, this provides a useful tool for constructing a hypergraph category that captures the syntax of a network-style diagrammatic language.
on a category 
we define a corelation to be a cospan 
is a morphism in 
Factorising maps 
using the factorisation system leads to a notion of equivalence on cospans, and this helps us describe when two diagrams are equivalent. Like cospans, corelations form hypergraph categories.
This has a space 
of 0-chains, which are formal linear combinations of vertices, and a space 
of 1-chains, which are formal linear combinations of edges.
in 
starting at this vertex determines a 1-chain 
namely the sum of its edges. These 1-chains give some points in 
These points are the vertices of a graph 
called the maximal abelian cover of 
to 
whenever the path 
is obtained by adding an extra edge to 
We can think of this edge as a straight line segment from 
There’s an inner product on the space of 1-chains such that edges form an orthonormal basis, so we get an orthogonal projection
is one-to-one on 
But that’s what I explained last time! It’s true whenever our original graph 
while the line segments between them are the edges of 
lattice’ and studied its energy minimization properties. Theoretically it seems to be a stable form of carbon. Crystals in this pattern have not yet been seen, but this pattern plays a role in the structure of certain butterfly wings.
holes from old ones.
there is a covering map
consisting of all symmetries of 
also acts as symmetries of the topological crystal associated to 
is the group of all symmetries of 
acts as translations of the crystal, in a way that preserves the color of every vertex.
by 
Beware the notation here: this is not the alternating group on the 3 letters. In fact it’s the permutation group on 4 letters, namely the vertices of the tetrahedron!
by 
Similarly, the octahedron gives a 7-dimensional topological crystal whose group of covering symmetries, an extension of 
we have the ‘hexagonal hosohedron’:
and its group of covering symmetries is an extension of 
by 
The case 
gives the graphene crystal, while 
gives the diamond.
It has 10 vertices and 15 edges, so its Euler characteristic is 
which implies that its space of 1-cycles is 6-dimensional. It thus gives a 6-dimensional crystal whose group of covering symmetries is an extension of 
by 
acts as isometries. These isometries preserve a tiling of Klein’s quartic curve by 56 triangles, with 7 meeting at each vertex. This picture is topologically correct, though not geometrically:
edges and 
vertices, so it has Euler characteristic 
It thus gives a 61-dimensional topological crystal whose group of covering symmetries is extension of 
From this we obtain a 29-dimensional topological crystal whose group of covering symmetries is an extension of 
of atoms is periodic. It’s usually not a lattice. But it’s contained in the lattice 
obtained by projecting the integral 1-chains down to the space of 1-cycles:
acts as translations on both 
we can define it to be
is the set of vertices and 
is the set of spanning trees. The main tool used to prove this is 
goes from a vertex called its source 
to a vertex called its target 
. We write 
to indicate that 
to 
. You can think of the edge as having an arrow on it, and if you turn the arrow around you get the inverse edge, 
. Also, 
.
, is the free abelian group on the set of vertices of 
, is the quotient of the free abelian group on the set of edges of 
for every edge 
in 
are composable then
whenever this equation makes sense. Each path 
gives a morphism which I’ll call ![[[\gamma]] : x \to y](https://s0.wp.com/latex.php?latex=%5B%5B%5Cgamma%5D%5D+%3A+x+%5Cto+y&bg=ffffff&fg=333333&s=0 "[[\gamma]] : x \to y")
in the abelianized fundamental groupoid. We say two paths 
are homologous if ![[[\gamma]] = [[\gamma']]](https://s0.wp.com/latex.php?latex=%5B%5B%5Cgamma%5D%5D+%3D+%5B%5B%5Cgamma%27%5D%5D&bg=ffffff&fg=333333&s=0 "[[\gamma]] = [[\gamma']]")
.
in 
.
be the kernel of this linear map, or equivalently,
counting as the negative of 
. We define an atom to be a homology class of paths starting at the basepoint, like![[[\alpha]] : x_0 \to x](https://s0.wp.com/latex.php?latex=%5B%5B%5Calpha%5D%5D+%3A+x_0+%5Cto+x++&bg=ffffff&fg=333333&s=0 "[[\alpha]] : x_0 \to x")
![i([[ \alpha ]]) = \pi(c_\alpha) .](https://s0.wp.com/latex.php?latex=i%28%5B%5B+%5Calpha+%5D%5D%29+%3D+%5Cpi%28c_%5Calpha%29+.&bg=ffffff&fg=333333&s=0 "i([[ \alpha ]]) = \pi(c_\alpha) .")
is well-defined follows from Lemma A. The interesting part is this:
is one-to-one.![[[ \alpha ]]](https://s0.wp.com/latex.php?latex=%5B%5B+%5Calpha+%5D%5D&bg=ffffff&fg=333333&s=0 "[[ \alpha ]]")
and ![[[ \beta ]]](https://s0.wp.com/latex.php?latex=%5B%5B+%5Cbeta+%5D%5D&bg=ffffff&fg=333333&s=0 "[[ \beta ]]")
, ![i([[ \alpha ]]) = i([[ \beta ]])](https://s0.wp.com/latex.php?latex=i%28%5B%5B+%5Calpha+%5D%5D%29++%3D+i%28%5B%5B+%5Cbeta+%5D%5D%29&bg=ffffff&fg=333333&s=0 "i([[ \alpha ]]) = i([[ \beta ]])")
implies ![[[ \alpha ]]= [[ \beta ]]](https://s0.wp.com/latex.php?latex=%5B%5B+%5Calpha+%5D%5D%3D+%5B%5B+%5Cbeta+%5D%5D&bg=ffffff&fg=333333&s=0 "[[ \alpha ]]= [[ \beta ]]")
. Note that 
is a path in 
, so![\pi(c_\gamma) = \pi(c_{\alpha} - c_\beta) = i([[ \alpha ]]) - i([[ \beta ]])](https://s0.wp.com/latex.php?latex=%5Cpi%28c_%5Cgamma%29+%3D+%5Cpi%28c_%7B%5Calpha%7D+-+c_%5Cbeta%29+%3D++i%28%5B%5B+%5Calpha+%5D%5D%29+-+i%28%5B%5B+%5Cbeta+%5D%5D%29+&bg=ffffff&fg=333333&s=0 "\pi(c_\gamma) = \pi(c_{\alpha} - c_\beta) = i([[ \alpha ]]) - i([[ \beta ]])")
vanishes if and only if ![c_{\gamma} \textrm{ is orthogonal to every 1-cycle} \; \iff \; i([[ \alpha ]]) = i([[ \beta ]])](https://s0.wp.com/latex.php?latex=c_%7B%5Cgamma%7D+%5Ctextrm%7B+is+orthogonal+to+every+1-cycle%7D+++%5C%3B+%5Ciff+%5C%3B+++i%28%5B%5B+%5Calpha+%5D%5D%29++%3D+i%28%5B%5B+%5Cbeta+%5D%5D%29++++&bg=ffffff&fg=333333&s=0 "c_{\gamma} \textrm{ is orthogonal to every 1-cycle} \; \iff \; i([[ \alpha ]]) = i([[ \beta ]])")
![c_\gamma = 0 \; \iff \; [[ \alpha ]]= [[ \beta ]].](https://s0.wp.com/latex.php?latex=c_%5Cgamma+%3D+0+%5C%3B+%5Ciff+%5C%3B+%5B%5B+%5Calpha+%5D%5D%3D+%5B%5B+%5Cbeta+%5D%5D.&bg=ffffff&fg=333333&s=0 "c_\gamma = 0 \; \iff \; [[ \alpha ]]= [[ \beta ]].")
(2), it suffices to that show that 
orthogonal to every 1-cycle has 
. This is Lemma D below. █
in which each vertex except 
, denoted 
, be the set of edges 
. This excludes edges with 
, but also those with 
, which are inverses of edges in the support. Note that
are simple loops with 
.
with
. We subtract this from 
until there’s nothing left. █
be a path in a graph 
we can write
is a simple path and 
.
for a simple path 
.
that’s orthogonal to all 1-cycles, so the hard part is showing that for a bridgeless graph, if 
. We hit this path with Lemma C, which lets us replace 
and write it out as 
. Since the last edge 
is not a bridge, there must be a path from 
. Remember, for us a graph is an abstract combinatorial gadget; its geometric realization is a topological space where the edges become closed intervals.
maps each edge of 
extends to a continuous map
in its 
. We can similarly define the Jacobian of a graph 
. Theorem B yields a way to embed a graph, or more precisely its geometric realization 
, into its Jacobian. This is the analogue, for graphs, of the Abel–Jacobi map.
Now let me say a bit more about the maximal abelian cover. It’s not nearly as famous as the universal cover, but it’s very nice.
is a covering space of 
and 
in either order, and the resulting morphisms 
and 
have the same source and the same target. And if you work out what that means, you’ll see it means
has a set 
of edges, maps 
assigning to each edge its source and target, and a map 
sending each edge to its inverse, obeying
and 
we write 
and draw 
to 
We write 
as 
and draw 
but with its arrow reversed. The equations obeyed by 
gives an edge 
and that 
No edge can be its own inverse.
is a pair of functions, one sending vertices to vertices and one sending edges to edges, that preserve the source, target and inverse maps. By abuse of notation we call both of these functions 
![[0,1]](https://s0.wp.com/latex.php?latex=%5B0%2C1%5D&bg=ffffff&fg=333333&s=0 "[0,1]")
for each edge 
to 
to 
and then identifying the interval for each edge 
and similarly for other topological invariants of 
However, sometimes I’ll need to distinguish between a graph 
acts as deck transformations of 
meaning invertible maps 
such that 
We can take the quotient of 
and get a cover 
to be the commutator subgroup of 
the maximal abelian cover of the graph 
This is just the first homology group 
In particular, if the space corresponding to 
in 
with 
for some vertices 
with 
and 
We allow the word to be empty if and only if 
; this gives the trivial path from 
and we write the trivial path from 
We define the composite of paths 
and 
via concatenation of words, obtaining a path we call 
We call a path from a vertex 
where 
If ![[\gamma]](https://s0.wp.com/latex.php?latex=%5B%5Cgamma%5D&bg=ffffff&fg=333333&s=0 "[\gamma]")
is a homotopy class of paths from 
we write ![[\gamma] : x \to y.](https://s0.wp.com/latex.php?latex=%5B%5Cgamma%5D+%3A+x+%5Cto+y.&bg=ffffff&fg=333333&s=0 "[\gamma] : x \to y.")
We can compose homotopy classes ![[\gamma] : x \to y](https://s0.wp.com/latex.php?latex=%5B%5Cgamma%5D+%3A+x+%5Cto+y&bg=ffffff&fg=333333&s=0 "[\gamma] : x \to y")
and ![[\delta] : y \to z](https://s0.wp.com/latex.php?latex=%5B%5Cdelta%5D+%3A+y+%5Cto+z&bg=ffffff&fg=333333&s=0 "[\delta] : y \to z")
by setting ![[\gamma] [\delta] = [\gamma \delta].](https://s0.wp.com/latex.php?latex=%5B%5Cgamma%5D+%5B%5Cdelta%5D+%3D+%5B%5Cgamma+%5Cdelta%5D.&bg=ffffff&fg=333333&s=0 "[\gamma] [\delta] = [\gamma \delta].")
![[\gamma] : x_0 \to x](https://s0.wp.com/latex.php?latex=%5B%5Cgamma%5D+%3A+x_0+%5Cto+x&bg=ffffff&fg=333333&s=0 "[\gamma] : x_0 \to x")
where ![[\delta] : x_0 \to y](https://s0.wp.com/latex.php?latex=%5B%5Cdelta%5D+%3A+x_0+%5Cto+y&bg=ffffff&fg=333333&s=0 "[\delta] : x_0 \to y")
are defined to be the edges 
with ![[\gamma e] = [\delta].](https://s0.wp.com/latex.php?latex=%5B%5Cgamma+e%5D+%3D+%5B%5Cdelta%5D.&bg=ffffff&fg=333333&s=0 "[\gamma e] = [\delta].")
In fact, there is always at most one such edge. There is an obvious map of graphs
the composites 
and 
are both well-defined if and only if 
and 
In this case, 
and 
and 
If all four of these equations hold, both 
and/or
and 
are loops based at the same vertex.![[[ \gamma ]].](https://s0.wp.com/latex.php?latex=%5B%5B+%5Cgamma+%5D%5D.&bg=ffffff&fg=333333&s=0 "[[ \gamma ]].")
Note that if two paths 
are homologous then ![[[ \gamma ]] : x \to y .](https://s0.wp.com/latex.php?latex=%5B%5B+%5Cgamma+%5D%5D+%3A+x+%5Cto+y+.&bg=ffffff&fg=333333&s=0 "[[ \gamma ]] : x \to y .")
The composite of homology classes is also well-defined if we set![[[ \gamma ]] [[ \delta ]] = [[ \gamma \delta ]]](https://s0.wp.com/latex.php?latex=%5B%5B+%5Cgamma+%5D%5D+%5B%5B+%5Cdelta+%5D%5D+%3D+%5B%5B+%5Cgamma+%5Cdelta+%5D%5D&bg=ffffff&fg=333333&s=0 "[[ \gamma ]] [[ \delta ]] = [[ \gamma \delta ]]")
![[[\gamma]] : x_0 \to x](https://s0.wp.com/latex.php?latex=%5B%5B%5Cgamma%5D%5D+%3A+x_0+%5Cto+x&bg=ffffff&fg=333333&s=0 "[[\gamma]] : x_0 \to x")
where ![[[ \gamma]] : x_0 \to x](https://s0.wp.com/latex.php?latex=%5B%5B+%5Cgamma%5D%5D+%3A+x_0+%5Cto+x&bg=ffffff&fg=333333&s=0 "[[ \gamma]] : x_0 \to x")
to the some atom ![[[ \delta ]] : x_0 \to y.](https://s0.wp.com/latex.php?latex=%5B%5B+%5Cdelta+%5D%5D+%3A+x_0+%5Cto+y.&bg=ffffff&fg=333333&s=0 "[[ \delta ]] : x_0 \to y.")
The bonds from ![[[ \gamma]]](https://s0.wp.com/latex.php?latex=%5B%5B+%5Cgamma%5D%5D&bg=ffffff&fg=333333&s=0 "[[ \gamma]]")
to ![[[ \delta ]]](https://s0.wp.com/latex.php?latex=%5B%5B+%5Cdelta+%5D%5D+&bg=ffffff&fg=333333&s=0 "[[ \delta ]]")
are defined to be the edges ![[[ \gamma e ]] = [[ \delta ]].](https://s0.wp.com/latex.php?latex=%5B%5B+%5Cgamma+e+%5D%5D+%3D+%5B%5B+%5Cdelta+%5D%5D.&bg=ffffff&fg=333333&s=0 "[[ \gamma e ]] = [[ \delta ]].")
There is at most one bond between any two atoms. Again we have a covering map
Furthermore, any element ![[\gamma] \in \pi_1(X)](https://s0.wp.com/latex.php?latex=%5B%5Cgamma%5D+%5Cin+%5Cpi_1%28X%29+&bg=ffffff&fg=333333&s=0 "[\gamma] \in \pi_1(X)")
defines a deck transformation of ![[\delta] : x_0 \to x](https://s0.wp.com/latex.php?latex=%5B%5Cdelta%5D+%3A+x_0+%5Cto+x+&bg=ffffff&fg=333333&s=0 "[\delta] : x_0 \to x")
to the vertex ![[\gamma] [\delta] : x_0 \to x.](https://s0.wp.com/latex.php?latex=%5B%5Cgamma%5D+%5B%5Cdelta%5D+%3A+x_0+%5Cto+x.&bg=ffffff&fg=333333&s=0 "[\gamma] [\delta] : x_0 \to x.")
Furthermore, any element ![[[\gamma]] \in H_1(X,\mathbb{Z})](https://s0.wp.com/latex.php?latex=%5B%5B%5Cgamma%5D%5D+%5Cin+H_1%28X%2C%5Cmathbb%7BZ%7D%29+&bg=ffffff&fg=333333&s=0 "[[\gamma]] \in H_1(X,\mathbb{Z})")
defines a deck transformation of ![[[\delta]] : x_0 \to x](https://s0.wp.com/latex.php?latex=%5B%5B%5Cdelta%5D%5D+%3A+x_0+%5Cto+x+&bg=ffffff&fg=333333&s=0 "[[\delta]] : x_0 \to x")
to the vertex ![[[\gamma]] [[\delta]] : x_0 \to x.](https://s0.wp.com/latex.php?latex=%5B%5B%5Cgamma%5D%5D+%5B%5B%5Cdelta%5D%5D+%3A+x_0+%5Cto+x.&bg=ffffff&fg=333333&s=0 "[[\gamma]] [[\delta]] : x_0 \to x.")
