In Sheffield we have started a reading seminar on the recent paper of Tom Leinster and Mike Shulman Magnitude homology of enriched categories and metric spaces. The plan was to write the talks up as blog posts. Various things, including the massive strike that has been going on in universities in the UK, have meant that I’m somewhat behind with putting the first talk up. The strike also means that we haven’t had many seminars yet!
I gave the first talk which is the one here. It is an introductory talk which just describes the idea of categorification and the paper I wrote with Richard Hepworth on categorifying the magnitude of finite graphs, this is the idea which was generalized by Tom and Mike.
Categorification
Categorification means many things. In this context it is supposed to be the idea of lifting an invariant from taking values in a set to values in a category. Let’s look at two examples.
[This is possibly a caricature of what actually happened. It would be nice to have some references!] In the eighteenth century, mathematicians such as Riemann knew about the Euler characteristic of surfaces (and possibly manifolds). This is a fundamental invariant which seems to crop up in all sorts of places. Towards the end of the century Poincar'e introduced homology groups H ⋆(M)\text{H}_\star(M) of a manifold MM and was aware
χ(M)=rank(H ⋆(M))=∑ i(−1) irank(H i(M)).
\chi(M)=rank(\text{H}_\star(M))= \sum_i (-1)^i rank (\text{H}_i(M)).
I get the impression the functorial nature of homology was not appreciated until later, but this adds another layer of structure.
Around 1985 Jones introduced his eponymous polynomial J(L)∈ℤ[q ±1]\text{J}(L)\in \mathbb{Z}[q^{\pm 1}] for a knot or link LL in 33-space. This gives a polynomial invariant of links. In around 1999, Khovanov introduced Khovanov homology Kh ⋆,⋆(L)Kh_{\star, \star}(L) for a link LL, this is bigraded group. The Jones polynomial is obtained from it by taking the dimension (or Euler characteristic!) in an appropriate graded sense:
J(L)=∑ i,j(−1) iq jrank(Kh i,j(L)).
\text{J}(L)= \sum_{i,j} (-1)^i q^j rank( Kh_{i,j}(L)).
In both these cases we lift an invariant which takes values in a set (either ℤ\mathbb{Z} or ℤ[q ±1] \mathbb{Z}[q^{\pm 1}]) to an invariant which takes values in a category (either graded groups or bigraded groups). This lifted invariant has a richer structure and functorial properties, but is probably harder to calculate! This is what we mean by categorifying an invariant.
Magnitude of enriched categories
There was a classical notion of Euler characteristic for finite groups and also one for finite posets. We know that finite groups and finite posets are both examples of finite categories (at one extreme with only one object and at the other extreme with at most one morphism between each pair of objects). Tom found a common generalization of these Euler characteristics which is the idea of an Euler characteristic for finite categories (we will see the definition next week). He further generalized that to the notion of an Euler characteristic for enriched categories (with a additional bit of structure, wait for next week). Finite metric spaces are examples of enriched categories and so have a notion of Euler characteristic. We decided the name was too confusing so after consulting a thesaurus we decided on “magnitude” (having toyed with the name “cardinality”). Tom later noticed something nice about the magnitude of the metric spaces that you get from finite graphs (partly because these have integer-valued metrics).
The journey from the Euler characteristics of finite posets and finite groups to the magnitude of finite graphs via a sequence of generalizations and specializations can be viewed as a trip up and then down the following picture.
Magnitude of metric spaces (more next week)
For X={x 1,…x n}X=\{x_1,\dots x_n\} a finite metric space with the metric we can define a matrix ZZ by Z i,j=e −d(x i,x j)Z_{i,j}=e^{-\text{d}(x_i,x_j)}. The magnitude |X||X| is defined to be the sum of the entries of the inverse matrix (if it exists): |X|:=∑ i,j(Z −1) i,j|X|:=\sum_{i,j}(Z^{-1})_{i,j}. It is actually more interesting if we look at what happens as we scale XX (or perhaps if we introduce an indeterminate into the metric). For t>0t> 0, we define t⋅Xt\cdot X to have the same underlying set, but with the metric scaled by a factor of tt. This gives us the magnitude function |t⋅X|\left|t\cdot X\right| which is a function of tt.
We can have a look at a simple example where we take XX to be a three-point metric space in which two points are much, much closer to each other than they are to the third point. Here is a picture of t⋅Xt\cdot X.
Here is the graph of the magnitude function of the metric space XX.
This shows in some sense how the magnitude can be viewed as an “effective number of points”. At small scales there is effectively one point, at middling scales there is effectively two points and at very large scales there are effectively three points.
Although the definition looks rather ad hoc, it turns out that it has various connections to thinks like measurements of biodiversity, Hausdorff dimension, volumes, potential theory and several other fun things.
Magnitude of graphs
Suppose that GG is a finite graph, then it gives rise to a finite metric space (which we will also write as GG) which has the vertices of GG as its points and the shortest path distance as its metric, where all edges have length one.
For example we have the five-cycle graph below with d(g 0,g 3)=2\text{d}(g_0, g_3)=2.
Tom noticed that we can use the magnitude function of the associated metric space to get an integral power series from the graph. Firstly, we can write q=e −tq=e^{-t} then the entries of the matrix ZZ are just integer powers of qq as all of the distances in GG are integral. This means that the entries of Z −1Z^{-1} are just rational functions of qq (with integer coefficients) and hence so is their sum, the magnitude function. Moreover the denominator of this rational function is the determinant of ZZ which, as the diagonal entries of ZZ are all e 0e^{0}, i.e., 11, is of the form 1+powers of q1+\text{powers of }q. So we can take a power series expansion of |t⋅G||t\cdot G| to get an integer power series in q=e −tq=e^{-t}. We denote this power series by #G\# G.
For example, for the five-cycle graph C 5C_5 pictured above we have
#C 5=5−10q+10q 2−20q 4+40q 5−40q 6+⋯.
\# C_5 = 5-10q+10q^2-20q^4+40q^5-40q^6+\cdots.
In general we can identify the first two coefficients as the number of vertices and −2-2 times the number of edges, respectively.
Categorifying the magnitude of graphs
As Richard Hepworth noticed, we can categorify this! In other words, we can find a homology theory which has the magnitude power series #G∈Z[q]\# G\in \Z[q] as its graded Euler characteristic.
For a finite graph GG define the magnitude chain groups as follows.
MC k,l(G)=⟨(x 0,…,x k)|x i−1≠x i,∑dd(x i−1,x i)=l⟩.
MC_{k,l}(G)=\left\langle (x_0,\dots, x_k) \big | x_{i-1}\ne x_{i},\quad \sum \dd(x_{i-1}, x_i)=l\right\rangle.
For example a chain group generator for the five-cycle graph from above is (g 0,g 1,g 2,g 4,g 2)∈MC 4,6(C 5)(g_0, g_1, g_2, g_4, g_2)\in MC_{4,6}(C_5).
We define maps ∂ i:MC k,l(G)→MC k−1,l(G)\partial_i\colon MC_{k,l}(G)\to MC_{k-1,l}(G) for i=1,…,k−1i=1,\dots, k-1:
∂ i(x 0,…,x k)={(x 0,…,x i^,…,x k) ifx i−1<x i<x i+1, 0 otherwise.
\partial_{i}(x_0,\ldots,x_k)
=
\begin{cases}
(x_0,\ldots,\widehat{x_i},\ldots,x_k)
&
\text{if}\,\,
x_{i-1}<x_{i}<x_{i+1},
\\
0
&
\text{otherwise}.
\end{cases}
where x i−1<x i<x i+1x_{i-1}<x_{i}<x_{i+1} means that x ix_i lies on a shortest path between x i−1x_{i-1} and x i+1x_{i+1}, i.e., d(x i−1,x i)+d(x i,x i+1)=d(x i−1,x i+1)\text{d}(x_{i-1},x_i)+\text{d}(x_i,x_{i+1})=\text{d}(x_{i-1},x_{i+1}).
So for our example chain generator in C 5C_5 you can check that we have
∂ i(g 0,g 1,g 2,g 4,g 2)={(g 0,g 2,g 4,g 2) ifi=1, 0 otherwise.
\partial_{i}(g_0, g_1, g_2, g_4, g_2)
=
\begin{cases}
(g_0, g_2, g_4, g_2)
&
\text{if}\,\,
i=1,
\\
0
&
{otherwise}.
\end{cases}
In the usual way, the differential ∂:MC k,l(G)→MC k−1,l(G)\partial\colon MC_{k,l}(G)\to MC_{k-1,l}(G) is defined
as the alternating sum
∂=∂ 1−∂ 2+⋯+(−1) k−1∂ k−1.
\partial=\partial_1-\partial_2+\cdots+(-1)^{k-1}\partial_{k-1}.
One can show that this is a differential, so that ∂∘∂=0\partial\circ\partial =0. Then taking homology gives what is defined to be magnitude homology groups of the graph:
MH k,l(G)=H k(MC *,l(G),∂).
\MH_{k,l}(G)= \text{H}_k(\MC_{\ast,l}(G), \partial).
By direct computation you can calculate the ranks of the magnitude homology groups of the five-cycle graph. The following table shows the ranks rank(MH k,l(C 5))rank(MH_{k,l}(C_5)) for small kk and ll.
k 0 1 2 3 4 5 6 χ(MH *,l(C 5)) 0 5 5 1 10 −10 2 10 10 l 3 10 10 0 4 30 10 −20 5 50 10 40 6 20 70 10 −40
\begin{array}{rrrrrrrrrrc}
&&&&&k\\
&&0&1&2&3&4&5&6&&\chi(MH_{\ast,l}(C_5))\\
&0 & 5&&&&&&&\qquad&5\\
& 1 & & 10 &&&&&&&-10 \\
&2 & && 10 &&&&&&10\\
l& 3 &&& 10 & 10 &&&&&0 \\
& 4 &&&& 30 & 10 &&&&-20\\
& 5 &&&&& 50 & 10 &&&40 \\
& 6 &&&&& 20 & 70 & 10 &&-40 \end{array}
The final column shows the Euler characteristics, which are just the alternating sums of entries in the rows. You can check that these are precisely the coefficients in the power series #C 5\# C_5 given above: this illustrates the fact that graph magnitude homology does indeed categorify graph magnitude in the sense of the following theorem.
Theorem
#G=∑ k,l≥0(−1) kq lrank(MH k,l(G))∈ℤ[[q]].
\#G = \sum_{k,l\geq 0} (-1)^k q^l \,rank
\bigl(MH_{k,l}(G)\bigr)\in \mathbb{Z}[[q]].
Thus we have MH *,*MH_{\ast,\ast} which a bigraded group valued invariant of graphs which is functorial with respect to certain maps of graphs and has properties like Kunneth Theorem and long exact sequences: richer but harder to calculate than the graph magnitude.
In the following weeks we will hopefully see how Mike and Tom have generalized this construction up to the top of the picture above, namely to certain enriched categories with extra structure.
Donald Trump reportedly 
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from
