Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

May 13, 2015

Categorifying the Magnitude of a Graph

Posted by Simon Willerton

Tom Leinster introduced the idea of the magnitude of graphs (first at the Café and then in a paper). I’ve been working with my mathematical brother Richard Hepworth on categorifying this and our paper has just appeared on the arXiv.

Categorifying the magnitude of a graph, Richard Hepworth and Simon Willerton.

The magnitude of a graph can be thought of as an integer power series. For example, consider the Petersen graph.

Petersen graph

Its magnitude starts in the following way. #P =1030q+30q 2+90q 3450q 4 +810q 5+270q 65670q 7+. \begin{aligned} \#P&=10-30q+30q^{2}+90q ^{3}-450q^{4}\\ &\quad\quad+810q^{5} + 270 q^{6} - 5670 q^{7} +\dots. \end{aligned}

Richard observed that associated to each graph GG there is a bigraded group MH *,*(G)\mathrm{MH}_{\ast ,\ast }(G), the graph magnitude homology of GG, that has the graph magnitude #G# G as its graded Euler characteristic. #G = k,l0(1) krank(MH k,l(G))q l = l0χ(MH *,l(G))q l. \begin{aligned} #G &= \sum _{k,l\geqslant 0} (-1)^{k}\cdot \mathrm{rank}\bigl (\mathrm{MH}_{k,l}(G)\bigr )\cdot q^{l}\\ &= \sum _{l\geqslant 0} \chi \bigl (\mathrm{MH}_{\ast ,l}(G)\bigr )\cdot q^{l}. \end{aligned} So graph magnitude homology categorifies graph magnitude in the same sense that Khovanov homology categorifies the Jones polynomial.

For instance, for the Petersen graph, the ranks of MH k,l(P)\mathrm{MH}_{k,l}(P) are given in the following table. You can check that the alternating sum of each row gives a coefficient in the above power series.

k 0 1 2 3 4 5 6 7 0 10 1 30 2 30 3 120 30 l 4 480 30 5 840 30 6 1440 1200 30 7 7200 1560 30 \begin{array}{rrrrrrrrrr} &&&&&&k\\ &&0&1&2&3&4&5&6&7 \\ &0 & 10\\ & 1 & & 30 \\ &2 & && 30 \\ &3 &&& 120 & 30 \\ l &4 &&&& 480 & 30 \\ &5 &&&&& 840 & 30 \\ &6 &&&&& 1440 & 1200 & 30 \\ &7 &&&&&& 7200 & 1560 & 30 \\ \\ \end{array}

Many of the properties that Tom proved for the magnitude are shadows of properties of magnitude homology and I’ll describe them here.

The definition

Let’s have a quick look at the definition first: this is a typical piece of homological algebra. For each graph GG we define a kk-chain on GG to be a k+1k+1-tuple of vertices of GG such that adjacent vertices are distinct: (a 0,,a k),a iVertices(G),a ia i+1. (a_{0},\dots ,a_{k}),\quad a_{i}\in \mathrm{Vertices}(G),\quad a_{i}\ne a_{i+1}. We equip the graph with the path length metric, so each edge has length 11, and we define the length of a chain to be the length of the path obtained by traversing its vertices: ((a 0,,a k)) i=0 k1d(a i,a i+1). \ell ((a_{0},\dots ,a_{k}))\coloneqq \sum _{i=0}^{k-1}d(a_{i},a_{i+1}). The chain group MC k,l(G)\mathrm{MC}_{k,l}(G) is defined to be the free abelian group on the set of kk-chains of length ll. We define the differential :MC k,lMC k1,l\partial \colon \mathrm{MC}_{k,l}\to \mathrm{MC}_{k-1,l} by (1) i i\partial \coloneqq \sum (-1)^{i}\partial _{i} where i(a 0,,a k){(a 0,,a i^,,a k) if(a 0,,a i^,,a k)=l, 0 otherwise. \partial _{i}(a_{0},\ldots ,a_{k}) \coloneqq \begin{cases} (a_{0},\ldots ,\widehat{a_{i}},\ldots ,a_{k}) & \mathrm{if } \ell (a_{0},\ldots ,\widehat{a_{i}},\ldots ,a_{k})=l, \\ 0 & \mathrm{otherwise}. \end{cases} Here, as usual, x^\widehat{x} means “omit xx”. The graph magnitude is then defined to be the homology of this differential: MH k,l(G)H k(MC *,l(G),). \mathrm{MH}_{k,l}(G)\coloneqq \mathrm{H}_{k}(\mathrm{MC}_{\ast ,l}(G),\partial ). Unfortunately, I don’t know of any intuitive interpretation of the chain groups.

Functoriality

One standard advantage of this sort of categorification is that it has functoriality where the original invariant did not. We don’t usually have morphisms between numbers or polynomials, but we do have morphisms between groups. In the case here we have the category of graphs with the morphisms sending vertices to vertices with edges either preserved or contracted, and graph magnitude homology gives a functor from that to the category of bigraded groups and homomorphisms.

Categorifying properties of magnitude

Here are some of the properties of magnitude that we can categorify. With the exception of disjoint unions, all of the other categorification results require some decidedly non-trivial homological algebra to prove.

Disjoint unions

Tom showed that magnitude is additive with respect to the disjoint union of graphs: #(GH)=#G+#H. #(G\sqcup H) = #G + #H. Our categorification of this is the additivity of the magnitude homology: MH *,*(GH)MH *,*(G)MH *,*(H). \mathrm{MH}_{\ast ,\ast }(G\sqcup H) \cong \mathrm{MH}_{\ast ,\ast }(G) \oplus \mathrm{MH}_{\ast ,\ast }(H).

Products

Tom showed that magnitude is multiplicative with respect to the cartesian product \square of graphs #(GH)=#G#H. #(G\Box H) = #G\cdot #H. The categorification of this is a Künneth Theorem which says that there is a non-naturally split, short exact sequence: 0MH *,*(G)MH *,*(H)MH *,*(GH) Tor(MH *+1,*(G),MH *,*(H))0. \begin{aligned} 0\to \mathrm{MH}_{\ast ,\ast }(G)\otimes \mathrm{MH}_{\ast ,\ast }(H) \to \mathrm{MH}_{\ast ,\ast }(G\square H)\\ \to \mathrm{Tor}\bigl (\mathrm{MH}_{\ast +1,\ast }(G), \mathrm{MH}_{\ast ,\ast }(H)\bigr ) \to 0. \end{aligned} If either GG or HH has torsion-free magnitude homology, then this sequence reduces to an isomorphism MH *,*(GH)MH *,*(G)MH *,*(H). \mathrm{MH}_{\ast ,\ast }(G{\square }H)\cong \mathrm{MH}_{\ast ,\ast }(G)\otimes \mathrm{MH}_{\ast ,\ast }(H). Despite quite a bit of computation, we don’t know whether any graphs have torsion in their magnitude homology.

Unions

Tom showed that a form of the inclusion-exclusion formula holds for certain graphs. We need a pile of definitions first.

Definition. A subgraph UXU\subset X is called convex if d U(u,v)=d X(u,v)d_{U}(u,v)=d_{X}(u,v) for all u,vUu,v\in U.

One way of reading this is that for uu and vv in UU there is a geodesic joining them that lies in UU.

Definition. Let UXU\subset X be a convex subgraph. We say that XX projects to UU if for every xXx\in X that can be connected by an edge-path to some vertex of UU, there is π(x)U\pi (x)\in U such that for all uUu\in U we have d(x,u)=d(x,π(x))+d(π(x),u). d(x,u) = d(x,\pi (x)) + d(\pi (x),u).

For instance, a four-cycle graph projects to any edge, whereas a five cycle does not project to an edge.

Definition. A projecting decomposition is a triple (X;G,H)(X;G,H) consisting of a graph XX and subgraphs GG and HH such that

  • X=GHX=G\cup H,

  • GHG\cap H is convex in XX,

  • HH projects to GHG\cap H.

Tom showed that if (X;G,H)(X;G,H) is a projecting decomposition then #X+#(GH)=#G+#H. #X +# (G\cap H)= #G +#H . Our categorification of this result is that if (X;G,H)(X;G,H) is a projecting decomposition, then there is a naturally split short exact sequence 0MH *,*(GH)MH *,*(G)MH *,*(H)MH *,*(X)0 0\to \mathrm{MH}_{\ast ,\ast }(G\cap H)\to \mathrm{MH}_{\ast ,\ast }(G)\oplus \mathrm{MH}_{\ast ,\ast }(H)\to \mathrm{MH}_{\ast ,\ast }(X)\to 0 (which is a form of Mayer-Vietoris sequence) and consequently there is a natural isomorphism MH *,*(X)MH *,*(GH)MH *,*(G)MH *,*(H). \mathrm{MH}_{\ast ,\ast }(X)\oplus \mathrm{MH}_{\ast ,\ast }(G\cap H) \cong \mathrm{MH}_{\ast ,\ast }(G)\oplus \mathrm{MH}_{\ast ,\ast }(H).

Diagonality

Tom noted many examples of graphs which had magnitude with coefficients which alternate in sign; these examples included complete graphs, complete bipartite graphs, forests and graphs with up to four vertices.

Our categorification of this is that in all of these cases the magnitude homology is supported on the diagonal: we say a graph GG is diagonal if MH k,l(G)=0\mathrm{MH}_{k,l}(G)=0 if klk\neq l. In this case the magnitude is given by #G= l0(1) lrankMH l,l(G)q l, #G=\sum _{l\geq 0}(-1)^{l}\cdot \mathrm{rank}\mathrm{MH}_{l,l}(G)\cdot q^{l}, and it means in particular that the coefficients of the magnitude alternate in sign.

The join GHG\star H of graphs GG and HH is obtained by adding an edge between every vertex of GG and every vertex of HH. This is a very drastic operation, for instance the diameter of the resulting join is at most 22.

Theorem. If GG and HH are non-empty graphs then the join GHG\star H is diagonal.

This tells us immediately that complete graphs and complete bipartite graphs are diagonal. Together with the other properties of magnitude homology mentioned above, we recover the alternating magnitude property of all the graphs noted by Leinster, as well as many more.

However, there is one graph that appears to be diagonal, at least up to degree 77 according to our computer calculations but which we can’t prove is diagonal, i.e. it doesn’t follow from the results above. This graph is the icosahedron graph which is the one-skeleton of the icosahedron.

icosahedron

Where next?

There are plenty of questions that you can ask about magnitude homology, a fundamental one is whether there are graphs with the same magnitude but different magnitude homology and a related one is whether you can categorify Tom’s result (conjectured by me and David Speyer) on the magnitude of graphs which differ by certain Whitney twists.

One interesting thing demonstrated here is that magnitude has its tendrils in homological algebra, yet another area of mathematics to add to the list which includes biodiversity, enriched category theory, curvature and Minkowski dimension.

Posted at May 13, 2015 4:18 PM UTC

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

19 Comments & 0 Trackbacks

Re: Categorifying the Magnitude of a Graph

Because this works via graph as metric space, so an enriched category, does this give it a different flavour to Tom’s paper where there was talk of the Euler characteristic of (directed) graphs as that of the category it freely generates?

What had been categorified back there? There was poset homology mentioned. Was there ever a homology for categories?

Posted by: David Corfield on May 18, 2015 4:53 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

Running with the metric space aspect, the magnitude homology seems to be in some way related to the “non-geodesic” nature of the space, or its “slackness”. It’s interesting to notice that the differential is zero on a path which is completely “slack” or “nowhere geodesic” in the sense that for any points x i,x i+2x_i,x_{i+2}, we have d(x i,x i+2)<d(x i,x i+1)+d(x i+1,x i+2)d(x_i,x_{i+2}) \lt d(x_i,x_{i+1}) + d(x_{i+1},x_{i+2}). And it’s almost the case that a path is a boundary if an intermediate point yy can be placed between some x i,x i+1x_i,x_{i+1} in a “non-slack” or “geodesic” way, in the sense that d(x i,x i+1)=d(x i,y)+d(y,x i+1)d(x_i,x_{i+1}) = d(x_i,y) + d(y,x_{i+1}). I think the magnitude homology will be zero if the space is geodesic in the sense that there is a geodesic path (in the usual, real interval sense) between every two points. On the other hand, a space like the circle with the metric inherited from the Euclidean plane is far from geodesic; I think its differentials are all zero and its magnitude homology is free on its paths.

Posted by: Tim Campion on May 18, 2015 7:40 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

Yes, there is a homology for categories. Categories present spaces: given a category you can write down a space called the geometric realization of its nerve, so if you want to you can take the homology of that space. Combinatorialists do this for posets, and many people do it for groups, where it recovers group homology. On “big” categories (categories of mathematical objects, as opposed to categories as mathematical objects) this construction tends to be uninteresting: for example, if a category has either an initial or a terminal object, then its nerve is contractible.

Posted by: Qiaochu Yuan on May 18, 2015 8:44 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

In the case of posets, homology is usually or at least often defined as that of the poset obtained by removing top and bottom. See for example here, page 5.

Posted by: Todd Trimble on May 19, 2015 2:07 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

Todd — yes, I’ve seen that before and it’s puzzled me. Do you know why they do that?

There’s the obvious answer that the homology is trivial if the poset has a top or a bottom… but that doesn’t seem very convincing.

I know it’s the case that if you start with a poset PP (perhaps both topless and bottomless), and freely adjoin a top 1 and a bottom 0, then the Euler characteristic of PP (or of its classifying space) is equal to 1+μ(0,1)1 + \mu(0, 1). Here μ\mu is the Möbius function of the enlarged poset. And in fact the same is true for categories in general, interpreting “top” as “terminal object” and “bottom” as “initial object”.

But is that relevant?

Posted by: Tom Leinster on May 20, 2015 2:27 AM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

It seems to me your construction outputs a lot more than a bigraded abelian group. What it actually outputs, although it’s buried a bit in the paper, is a sequence of simplicial sets (do you know if they organize into a bisimplicial set?), analogous to the nerve of a category, which you then take the homology of. By contrast, I don’t know if anyone knows how to present Khovanov homology this way, so I think the analogy between them is less tight than it at first appears.

Some of the mysteries of the construction might be less mysterious if you studied these simplicial sets more directly; you could try to compute, for example, their homotopy groups.

Posted by: Qiaochu Yuan on May 18, 2015 8:14 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

Looks like my comment crossed with yours. I guess your suggestion amounts to doing the filtration on the simplicial set level rather than the chain level?

Posted by: Mike Shulman on May 18, 2015 8:30 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

Yes indeed! The (pointed) simplicial sets make an appearance in the paper in Section 8, where we prove our Kunneth theorem by appealing to the Kunneth theorem for simplicial sets.

In more detail, we introduced pointed simplicial sets M l(G)M_l(G) whose (normalised, reduced) simplicial chains are literally the chain complexes MC *,l(G)MC_{\ast,l}(G). Although we didn’t say it, these simplicial sets are filtration quotients

(1)M l(G)=F lMS(G)/F l1MS(G). M_l(G) = F_l MS(G) / F_{l-1} MS(G).

As in Mike’s comment MS(G)MS(G) denotes the simplicial set whose kk-simplices are (k+1)(k+1)-tuples of vertices of GG, and F lMS(G)MS(G)F_l MS(G)\subset MS(G) denotes the simplicial subset consisting of tuples of `length’ at most ll.

I don’t see any reason why these simplicial sets should assemble to a bisimplicial set.

One of my reasons for downplaying this aspect of the construction was to minimise the paper’s technical requirements, sticking to graphs and chain complexes where possible. Another was that it’s going too far too soon. We don’t yet know any graphs whose homology contains torsion, so to show that the M l(G)M_l(G) have (say) an interesting homotopy type is a big ask!

I conjecture, presumably to my forthcoming regret, that the stronger analogy is with Heegaard-Floer homology, rather than Khovanov homology.

Posted by: Richard Hepworth on May 18, 2015 11:02 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

Thinking out loud: there is a simplicial set MS(G)MS(G) whose kk-simplices are the kk-chains in GG. (It’s just the codiscrete simplicial set on the set of vertices of GG.) The associated (singly graded) chain complex MC(G)=MS(G)MC(G) = \mathbb{Z} MS(G) has MC k(G)= lMC k,l(G)MC_k(G) = \bigoplus_l MC_{k,l}(G), so each group is equipped with a natural grading. The differential doesn’t preserve the grading, but (by equation (2) in your paper) it does preserve the filtrations defined by

F lMC k(G) mlMC k,m(G). F_l MC_k(G) \coloneqq \bigoplus_{m\le l} MC_{k,m}(G).

That is, the differential d:MC k(G)MC k1(G)d : MC_k(G) \to MC_{k-1}(G) maps F lMC k(G)F_l MC_k(G) into F lMC k1(G)F_l MC_{k-1}(G). Thus we have a filtered complex, which gives rise to a spectral sequence. Unless I’m mistaken, your graph magnitude homology is the E 1E^1 page of this spectral sequence (the E 0E^0 page is the magnitude chain groups).

The spectral sequence indexing is usually shifted, which I think in your case gives E p,q 1=MH p+q,pE^1_{p,q} = MH_{p+q,p} or MH k,l=E l,kl 1MH_{k,l}=E^1_{l,k-l}. This corresponds to shifting the l thl^{th} row of your tables to the left by ll, so that the diagonal becomes the negative yy-axis, then rotating counterclockwise by 90 90^\circ, so that the nontrivial groups live in quadrant IV. The degrees of the differential d rd^r in (p,q)(p,q) terms is (r,r1)(-r,r-1), which in (k,l)(k,l) terms becomes (1,r)(-1,-r). Thus, on your tables, d 0d^0 goes one space left (coinciding with your differential on the magnitude chain groups), d 1d^1 goes one space left and one space up (in particular, along the diagonal), d 2d^2 goes one space left and two spaces up, and so on. Boundedness should imply that the spectral sequence converges to the homology of MC(G)MC(G) — which should be trivial (except for H 0=H_0 = \mathbb{Z}), since the simplicial set MS(G)MS(G) is contractible.

Assuming I haven’t made a mistake (which is quite an assumption), this means there is some interesting extra structure on your magnitude homology groups. For instance, if a graph is diagonal, we have E 2=E =0E^2=E^\infty = 0, and so its magnitude homology groups (the E 1E^1 page) form a chain complex that is quasi-isomorphic to \mathbb{Z}. I wonder if this perspective could also bring some general machinery to bear on the Kunneth and Mayer-Vietoris theorems.

Posted by: Mike Shulman on May 18, 2015 8:23 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

I agree about this as well. The magnitude chains on a (connected!) graph GG are the filtration quotients of an acyclic chain complex. Consequently there is a (convergent, I now believe) spectral sequence whose E 1E^1 page is

(1)E s,t 1=MH s+t,s(G) E^1_{s,t} = MH_{s+t,s}(G)

whose E E^\infty page consists of only Z\Z in degree (0,0)(0,0). This should be an interesting structure (or strong constraint) on the magnitude homology.

I think I have heard something similar happening in Heegaard-Floer homology: Given a knot in a 3-manifold, one has the (bigraded) knot Floer homology of the knot, and the (singly graded) Heegaard-Floer homology of the 3-manifold, and there is a spectral sequence with E 1E^1-page the first thing, converging to the second thing.

Posted by: Richard Hepworth on May 18, 2015 11:26 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

Ah, yes, I missed that the graph has to be connected for the filtration to be exhaustive.

Posted by: Mike Shulman on May 19, 2015 12:08 AM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

I read this (post and comment) yesterday and it’s been bugging me ever since. Why, if we have a filtration of such a nice simplicial set, are all the edges double counted in the homological degree one term? Ofcourse it’s because paths a -> b -> a have greater length than paths a -> b and b -> a, but shouldn’t there be a better explanation.

I’m not sure it’s better, but it’s eased my unease: the filtration doesn’t respect the nerve like properties of the construction. For example the associated simplicial sets aren’t Kan complexes. So the homology itself picks up some of the directed nature of the simplices.

Given that the graph isn’t directed, there should be some extra structure on these groups that witness this fact. The “degree zero” structure might be reversals of paths. But could be higher structure as well?

Posted by: James Griffin on May 21, 2015 11:49 AM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

What do you mean by “double counted”?

Posted by: Mike Shulman on May 21, 2015 9:40 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

I think James means that MH 1,1(G)MH_{1,1}(G) is freely generated by the directed edges of GG.

Posted by: Simon Willerton on May 21, 2015 10:23 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

Apparently I also missed the requirement that adjacent vertices in a chain are distinct, which (seems bizarre to me and) means the simplicial set MS(G)MS(G) that I had in mind doesn’t work. Maybe your pointed simplicial sets are the only way to go.

Posted by: Mike Shulman on May 21, 2015 9:39 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

There’ve been a couple of comments asking why we want adjacent vertices to be distinct. I’ll explain how our definition of magnitude chains, and this aspect in particular, is the “natural” definition.

“Deducing” the definition of MC k,l(G)MC_{k,l} (G)

Tom’s counting formula for the magnitude of a graph GG is

(1)#G= k=0 x 0x 1x kq (x 0,,x k) \# G = \sum_{k=0}^\infty \sum_{x_0\neq x_1\neq\cdots\neq x_k} q^{\ell(x_0,\ldots,x_k)}

where

(2)(x 0,,x l)=d(x 0,x 1)++d(x k1,x k). \ell(x_0,\ldots,x_l)=d(x_0,x_1)+\cdots+d(x_{k-1},x_k).

We would like to categorify this in the same way that Khovanov homology categorifies the Jones polynomial. That means we would like to find a sequence of chain complexes MC *,0(G),MC *,1(G),MC_{\ast,0} (G), MC_{\ast,1} (G),\ldots such that

(3)#G= l=0 k=0 (1) krkMC k,l(G)q l. #G = \sum_{l=0}^\infty \sum_{k=0}^{\infty} (-1)^k \cdot\rk MC_{k,l} (G)\cdot q^l.

Comparing this with Tom’s formula, we see that the “simplest” way for this to hold is if rkMC k,l(G)\rk MC_{k,l} (G) is the number of kk-tuples (x 0,,x k)(x_0,\ldots,x_k ) satisfying x 0x 1x kx_0\neq x_1\neq\cdots\neq x_k and (x 0,,x k)=l\ell(x_0,\ldots,x_k)=l. And the “simplest” way for that to hold is if MC k,l(G)MC_{k,l} (G) is the free abelian group generated by exactly these kk-tuples! If we choose this definition then we have categorified the magnitude in the way we wanted.

“Deducing” the definition of MC *,l(G)MC_{\ast,l} (G)

We’re not done, because we want to assemble the groups MC k,l(G)MC_{k,l} (G) into a chain complex MC *,l(G)MC_{\ast,l} (G). If you showed our definition of MC k,l(G)MC_{k,l} (G) to a homological algebraist, they would immediately tell you that we make this into a chain complex by defining

(4)(x 0,,x k)= j=0 k(1) j(x 0,,x j^,,x k). \partial(x_0,\ldots,x_k) = \sum_{j=0}^k(-1)^j (x_0,\ldots,\widehat{x_j},\ldots,x_k).

However, they would quickly notice that this doesn’t work, since the new tuples (x 0,,x j^,,x k)(x_0,\ldots,\widehat{x_j},\ldots,x_k) obtained by deleting an entry might not be generators of our chain complex. Indeed, we may have reduced ()\ell(-), and we may have created an adjacent pair of equal vertices (in which case we definitely reduced ()\ell(-)). We therefore try to define \partial as above, but omitting any term where ()\ell(-) has been reduced. And we check directly that this does still satisfy =0\partial\circ\partial=0!

What if we allowed x j1=x jx_{j-1}=x_j instead?

Everything breaks. For now we could replace (x 0,,x k)(x_0,\ldots,x_k) with (x 0,x 0,,x k)(x_0,x_0,\ldots,x_k) or (x 0,x 0,x 0,,x k)(x_0,x_0,x_0,\ldots,x_k) or anything else with as many repeated entries as we like. These will all have the same ()\ell(-), and so we see that (the modification of) Tom’s formula for the magnitude will feature an infinite sum, even if we only look at the coefficient of q lq^l for a fixed ll. On the other hand, …

Everything still works. For the new MC *,*(G)MC_{\ast,\ast} (G) is still a chain complex, and contains the old version as a chain deformation retract, and in particular still categorifies the magnitude. It’s just that the proof of categorification with the new definition starts by going back to the old one.

There are other good reasons why we want to have x j1x jx_{j-1}\neq x_j. One is that, when we prove the Mayer-Vietoris theorem or that joins have diagonal homology, we do it by finding useful filtrations of the chain complexes at hand. We do this by looking at a tuple and “scanning along” its entries for the first occurence of a certain phenomenon; the position of this first occurence then determines which term of the filtration our element lies in. If we allowed repeated adjacent entries, this question of “position” within a tuple (x 0,,x k)(x_0,\ldots,x_k) gets way more complicated, and indeed I don’t know how we would prove our main theorems in this context.

Sometime I’ll write another comment surveying the various filtration / simplicial possibilities that people have noticed.

Posted by: Richard Hepworth on May 21, 2015 11:50 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

Is it essentially the comparison between chains and normalized chains on a simplicial set?

Posted by: Mike Shulman on May 22, 2015 3:23 AM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

I’m confused about something basic. You say a kk-chain is a list of vertices (a 0,,a k)(a_0,\dots,a_k) such that adjacent vertices are distinct: a ia i+1a_i \ne a_{i+1}. Then you define a differential that involves omitting one of the vertices. I don’t see how we know the adjacent vertices are distinct after that.

Posted by: John Baez on May 21, 2015 4:59 PM | Permalink | Reply to this

Re: Categorifying the Magnitude of a Graph

I believe what happens is that if a i1a_{i-1} and a i+1a_{i+1} are equal, then d(a i1,a i+1)d(a i1,a i)+d(a i,a i+1)d(a_{i-1},a_{i+1}) \neq d(a_{i-1},a_i)+d(a_i,a_{i+1}). So in this case, the differential is not given by omitting a ia_i, but is just 00.

Posted by: Aaron Greenspan on May 21, 2015 7:19 PM | Permalink | Reply to this

Post a New Comment