The n-Category Café

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 $\text{H}_\star(M)$ of a manifold $M$ and was aware

$$\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 $\text{J}(L)\in \mathbb{Z}[q^{\pm 1}]$ for a knot or link $L$ in $3$-space. This gives a polynomial invariant of links. In around 1999, Khovanov introduced Khovanov homology $Kh_{\star, \star}(L)$ for a link $L$, this is bigraded group. The Jones polynomial is obtained from it by taking the dimension (or Euler characteristic!) in an appropriate graded sense:

$$\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 $\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,\dots x_n\}$ a finite metric space with the metric we can define a matrix $Z$ by $Z_{i,j}=e^{-\text{d}(x_i,x_j)}$. The magnitude $|X|$ is defined to be the sum of the entries of the inverse matrix (if it exists): $|X|:=\sum_{i,j}(Z^{-1})_{i,j}$. It is actually more interesting if we look at what happens as we scale $X$ (or perhaps if we introduce an indeterminate into the metric). For $t> 0$, we define $t\cdot X$ to have the same underlying set, but with the metric scaled by a factor of $t$. This gives us the magnitude function $\left|t\cdot X\right|$ which is a function of $t$.

We can have a look at a simple example where we take $X$ 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\cdot X$.

Here is the graph of the magnitude function of the metric space $X$.

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 $G$ is a finite graph, then it gives rise to a finite metric space (which we will also write as $G$) which has the vertices of $G$ 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 $\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^{-t}$ then the entries of the matrix $Z$ are just integer powers of $q$ as all of the distances in $G$ are integral. This means that the entries of $Z^{-1}$ are just rational functions of $q$ (with integer coefficients) and hence so is their sum, the magnitude function. Moreover the denominator of this rational function is the determinant of $Z$ which, as the diagonal entries of $Z$ are all $e^{0}$, i.e., $1$, is of the form $1+\text{powers of }q$. So we can take a power series expansion of $|t\cdot G|$ to get an integer power series in $q=e^{-t}$. We denote this power series by $\# G$.

For example, for the five-cycle graph $C_5$ pictured above we have

$$\# 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$ 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\in \Z[q]$ as its graded Euler characteristic.

For a finite graph $G$ define the magnitude chain groups as follows.

$$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)\in MC_{4,6}(C_5)$.

We define maps $\partial_i\colon MC_{k,l}(G)\to MC_{k-1,l}(G)$ for $i=1,\dots, k-1$:

$$\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+1}$ means that $x_i$ lies on a shortest path between $x_{i-1}$ and $x_{i+1}$, i.e., $\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_5$ you can check that we have

$$\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 $\partial\colon MC_{k,l}(G)\to MC_{k-1,l}(G)$ is defined as the alternating sum

$$\partial=\partial_1-\partial_2+\cdots+(-1)^{k-1}\partial_{k-1}.$$

One can show that this is a differential, so that $\partial\circ\partial =0$. Then taking homology gives what is defined to be magnitude homology groups of the graph:

$$\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))$ for small $k$ and $l$.

$$\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$ given above: this illustrates the fact that graph magnitude homology does indeed categorify graph magnitude in the sense of the following theorem.

Theorem $$\#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_{\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.