## March 19, 2018

### Magnitude Homology Reading Seminar, I

#### Posted by Simon Willerton

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 $\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.

Posted at March 19, 2018 8:59 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3028

### Re: Magnitude Homology Reading Seminar, I

[This is possibly a caricature of what actually happened. It would be nice to have some references!]

This paper by Colin McLarty might be a good place to start, at least for the earlier parts of the story.

Posted by: Mark Meckes on March 19, 2018 2:36 PM | Permalink | Reply to this

### Re: Magnitude Homology Reading Seminar, I

Thanks Mark, I’ll have a look!

Posted by: Simon Willerton on March 19, 2018 4:53 PM | Permalink | Reply to this

### Re: Magnitude Homology Reading Seminar, I

The link to Hepworth-Willerton is incorrect.

Posted by: Yuzhou Gu on March 19, 2018 4:35 PM | Permalink | Reply to this

### Re: Magnitude Homology Reading Seminar, I

Fixed! Thank you.

Posted by: Simon Willerton on March 19, 2018 4:54 PM | Permalink | Reply to this

### Re: Magnitude Homology Reading Seminar, I

I am not sure this is the correct place but let me say some observations/results on magnitude homology of graphs.

1. Hepworth-Willerton asked whether there are graphs with same magnitude but different magnitude homology. Note that magnitude is computable in polynomial time but it is not obvious we can do so with magnitude homology. So hard graph isomorphism instances should suffice. Specifically, we can take the two graphs to be rook (4,4) graph and Shrikhande graph.

2. Calculations of magnitude homology can often be done using algebraic Morse theory (Jollenbeck 05, Skoldberg 06).

Let me give an example for odd cyclic graphs $C_{2m+1}$. Fixing a start point, any sequence of points $(x_0,x_1,\ldots,x_k)$ can be written as a sequence of numbers $(a_1,\ldots,a_k)$ in $\{-m,\ldots,-1, 1, \ldots,m\}$, where $a_i = x_i-x_{i-1} \pmod{(2m+1)}$. Deleting a point in the sequence is sequence is equivalent to merging to adjacent numbers. Two numbers can be merged if and only if (1) their signs are equal and (2) absolute value of their sum is $\le m$.

Using some tensor product decomposition we can reduce the problem to computing the homology of the chain complex generated by sequences only with positive numbers. The morse matching is: $(\cdots, k,m,1,\ldots,m,1)$-$(\cdots,k-1,1,m,1,\ldots,m,1)$ for $2\le k\le m$ and any prefix. The remaining elements are of the form $(1,m,1,\ldots,m,1)$ and $(m,1,\ldots,m,1)$.

For even cyclic graphs we can also compute magnitude homology using algebraic morse theory, but it is more complicated. (Results for cyclic graphs match predictions made in Hepworth-Willerton.) I also tried for some time proving Whitney twist, but did not succeed.

Posted by: Yuzhou Gu on March 19, 2018 6:04 PM | Permalink | Reply to this

### Re: Magnitude Homology Reading Seminar, I

Yuzhou, that sounds great. Are you planning on writing this up?

I don’t quite follow the reasoning in (1) probably because I don’t know anything about the hard isomorphism problem, and I don’t know anything about algebraic Morse theory in (2); so it would be nice to hear more about this.

I can, however, give some verification of your two graphs with the same magnitude but different magnitude homology groups.

Let’s start with the $4\times 4$ rook graph, $R_{4,4}$. This is isomorphic to the Cartesian product $K_4\square K_4$ where $K_4$ is the complete graph on four vertices. An easy computation (eg. by Speyer’s homogeneous magnitude formula) gives the magnitude function of this complete graph:

$|K_4|=\frac{4}{1+3q}.$

So by Tom’s multiplicativity result for the Cartesian product we have

$|R_{4,4}|= |K_4\square K_4| = |K_4|\cdot |K_4| = \frac{16}{9q^2 + 6q + 1}.$

On the other hand, a quick check with SageMath, using the command graphs.ShrikhandeGraph().magnitude_function() gives the same answer for the Shrikhande graph, $S$:

$|S|= \frac{16}{9q^2 + 6q + 1}.$

So we do indeed have $|S| = |R_{4,4}|$. Taking the power series expansions gives us

\begin{aligned} \# S = \# R_{4,4} &= \sum_{i=0}^\infty 16 (i+1)(-3q)^i \\ &= 16 - 96q + 432q^2 - 1728q^3 +6480q^4 - 23328q^5 +\dots\,. \end{aligned}

Now for the magnitude homology. Let’s do the rooks graph first. From the result in mine and Richard’s paper we know that for the complete graph the magnitude homology $MH_{\ast,\ast}(K_4)$ is torsion-free and diagonal (where ‘diagonal’ means that the only non-trivial groups are $MH_{k,k}(K_4)$). Our Kunneth theorem then implies that $R_{4,4} = K_4\square K_4$ is also diagonal and torsion-free, so from the above magnitude expansion we have that in low degree $MH_{k,l}(R_{4,4})$ has rank as follows.

$\begin{array}{rrrrrrr} & & & & k\\ & 0 & 1& 2& 3 & 4& 5\\ 0:& 16 & & & & & \\ 1:& & 96 & & & & \\ 2:& & & 432 & & & \\ l\,\,\, 3:& & & & 1728 & & \\ 4:& & & & & 6480 & \\ 5:& & & & & & 23328 \end{array}$

Now for the Shrikande graph. A computation in SageMath for the Shrikhande graph gives us that, over the rationals, $MH_{k,l}(S)$ has the following rank:

$\begin{array}{rrrrrrr} & & & & k\\ & 0 & 1& 2& 3 & 4& 5\\ 0:& 16 & & & & & \\ 1:& & 96 & & & & \\ 2:& & & 432 & & & \\ l\,\,\, 3:& & & & 1728 & & \\ 4:& & & & 144 & 6624 & \\ 5:& & & & & 1632 & 24960 \end{array}$

Excellent! Different magnitude homology, as you said.

Posted by: Simon Willerton on March 20, 2018 1:07 PM | Permalink | Reply to this

### Re: Magnitude Homology Reading Seminar, I

Oh, “hard graph isomorphism instances should suffice” is not a theorem, but an idea of how we can generate graphs that are indistinguishable using magnitude but distinguishable using magnitude homology. Hard graph isomorphism instances mean two graphs that are (possibly) difficult to distinguish using polynomial-time algorithms. So magnitude, which is computable in polynomial time, probably cannot distinguish these two graphs. That magnitude homology can distinguish them is just a hope, since magnitude homology is so strong. So yes, this is not rigorous reasoning. Anyway this gives graphs we want.

I may write this up in May or June, when the school term ends.

If you want to learn about algebraic Morse theory, you can refer to Skoldberg, Morse theory from an algebraic viewpoint; or for a very quick introduction, refer to Section 1.1 of Lampret, Vavpetic, (Co)homology of Lie algebras via algebraic Morse theory.

Posted by: Yuzhou Gu on March 20, 2018 5:01 PM | Permalink | Reply to this

### Re: Magnitude Homology Reading Seminar, I

Splendid.

Can I ask how you proved that the magnitude homology of the two graphs are different? And did you come up with a list of potential candidates using hard graph isomorphism instances and then try them, or was this the first pair you tried?

Posted by: Simon Willerton on March 20, 2018 8:52 PM | Permalink | Reply to this

### Re: Magnitude Homology Reading Seminar, I

was this the first pair you tried?

Wikipedia rook graph does say

When $n = 4$, there is another strongly regular graph, the Shrikhande graph, with the same parameters as the $4\times 4$ rook’s graph. The Shrikhande graph obeys the same properties listed by Moon and Moser.

So I guess their similarity is well known by those who know such things.

Posted by: RodMcGuire on March 20, 2018 10:56 PM | Permalink | Reply to this

### Re: Magnitude Homology Reading Seminar, I

To your disappointment, I verified that using code provided at arXiv. (On the other hand, the proof that their magnitude are the same is slightly simpler than yours: observe that both graphs are vertex-transitive and then use Speyer’s formula.)

This pair is the first pair I tried. I just tried another pair: Dodecahedral graph and Desargues graph, and it worked. (The hardest part is to find two vertex-transitive graphs such that the multisets $\{d(g,v): v\in V\}$ are the same.) Magnitude homology indeed does well in distinguishing graphs.

Posted by: Yuzhou Gu on March 20, 2018 11:20 PM | Permalink | Reply to this

### Re: Magnitude Homology Reading Seminar, I

Cool! These are exciting developments.

Posted by: Tom Leinster on March 21, 2018 4:34 PM | Permalink | Reply to this

### Re: Magnitude Homology Reading Seminar, I

Simon wrote:

Towards the end of the century Poincaré introduced homology group $H_*(M)$ of a manifold $M$

I’ve looked at his Analysis Situs and I don’t remember anything about homology groups, just Betti numbers and perhaps other numerical invariants associated to what we’d now call the torsion part of the homology groups. I think it was Emmy Noether who explicitly introduced homology groups, though in retrospect we can find them lurking in earlier work — indeed, we can scarcely understand earlier work without thinking about homology groups! So I’d say Noether categorified earlier work, by treating Betti numbers as ranks of homology groups. This set the stage for mathematicians to study the effect of maps on homology, which in turn led Eilenberg and Mac Lane to invent ‘functors’.

Here’s what I said in a talk on The Rise and Spread of Algebraic Topology:

We now say the $i$th Betti number of a topological space $X$ is the rank of $H_i(X)$. But that’s not what Enrico Betti said!

Betti defined his numbers in 1871. In 1895 Poincaré recalled them in his Analysis Situs. In what would later be seen as a massive understatement, he wrote:

Meanwhile, the field is by no means exhausted.

Poincaré said what it means for two oriented submanifolds of a manifold $X$ to be homologous. He showed how to add and subtract homology classes. He essentially said that the $i$th Betti number of $X$ is $\beta_i$ if $X$ has at most $\beta_i$ linearly independent homology classes of $i$-dimensional submanifolds.

Only 20 years later, in 1915, did Alexander prove that Betti numbers are topological invariants.

In the summers of 1926–1928, Alexandroff and Hopf lectured on algebraic topology in Goettingen. Emmy Noether attended and pointed out that $i$th Betti number is the rank of an abelian group

$H_i(X) = \displaystyle{ \frac{\ker \partial_i}{\im \, \partial_{i+1}} }$

where

$\partial_i : C_i(X) \to C_{i-1}(X)$

is a map between ‘chain groups’. She also noticed that a map of simplicial complexes induced a map of homology groups. All this was new!

Noether never published a single paper about these ideas, and they spread slowly.

All these ideas were a very long time in the making because the people doing homology and homotopy theory were not algebraists and the algebraists didn’t take any interest. The only person who took any interest was Emmy Noether.Peter Hilton

Posted by: John Baez on March 24, 2018 7:50 AM | Permalink | Reply to this

### Re: Magnitude Homology Reading Seminar, I

Based on a cursory reading of the paper by Colin McLarty I linked to above, and some of its references, it seems that some people (including Mac Lane and McLarty) contend that Poincaré understood perfectly well that in his adding and subtracting of homology classes amounted to working with groups, but that for reasons I don’t find very clear, Poincaré avoided using the term “group” in this context. Others (notably Dieudonné) disagree. (McLarty also claims that Lefschetz used the term “homology group” before Noether did.)

Of course, no one disputes the central role that Noether played in creating homology theory in its modern form. McLarty’s focus is in particular on how Noether set the stage for the invention of functors.

Posted by: Mark Meckes on March 24, 2018 5:54 PM | Permalink | Reply to this

Post a New Comment