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.

April 11, 2018

Torsion: Graph Magnitude Homology Meets Combinatorial Topology

Posted by Simon Willerton

As I explained in my previous post, magnitude homology categorifies the magnitude of graphs. There are two questions that will jump out to seasoned students of homology.

  • Are there two graphs which have the same magnitude but different homology groups?
  • Is there a graph with torsion in its homology groups?

Both of these were stated as open questions by Richard Hepworth and me in our paper as we were unable to answer them, despite thinking about them a fair bit. However, recently both of these have been answered positively!

The first question has been answered positively by Yuzhou Gu in a reply to my post. Well, this is essentially answered, in the sense that he has given two graphs both of which we know (provably) the magnitude of, one of which we know (provably) the magnitude homology groups of and the other of which we can compute the magnitude homology of using mine and James Cranch’s SageMath software. So this just requires verification that the program result is correct! I have no doubt that it is correct though.

The second question on the existence of torsion is what I want to concentrate on in this post. This question has been answered positively by Ryuki Kaneta and Masahiko Yoshinaga in their paper

It is a consequence of what they prove in their paper that the graph below has 22-torsion in its magnitude homology; SageMath has drawn it as a directed graph, but you can ignore the arrows. (Click on it to see a bigger version.)

graph

In their paper they prove that if you have a finite triangulation TT of an mm-dimensional manifold MM then you can construct a graph G((T)G((T) so that the reduced homology groups of MM embed in the magnitude homology groups of G((T)G((T):

H˜ i(M)MH i+2,m+2(G(T))for 0im. \widetilde{\mathrm{H}}_i(M)\hookrightarrow MH_{i+2, m+2}( G(T)) \,\,\,\, \text{for }\,\,0\le i \le m.

Following the suggestion in their paper, I’ve taken a minimal triangulation T 0T_0 of the real projective plane P 2\mathbb{R} P^2 and used that to construct the above graph. As we know H 1(P 2)=/2\mathrm{H}_1(\mathbb{R} P^2)=\mathbb{Z}/2\mathbb{Z}, we know that there is 22-torsion in MH 3,4(G(T 0))MH_{3,4}(G({T_0})).

In the rest of this post I’ll explain the construction of the graph and show explicitly how to give a 22-torsion class in MH 3,4(G(T 0))MH_{3,4}(G({T_0})). I’ll illustrate the theory of Kaneta and Yoshinaga by working through a specific example. Barycentric subdivision plays a key role!

The minimal triangulation of the projective plane

We are going to construct our graph from the minimal triangulation of P 2\mathbb{R} P^2 so let’s have a look at that first. We want to see how the 22-torsion in the homology of P 2\mathbb{R} P^2 can be expressed using this triangulation as we will need that later for the 22-torsion in the graph magnitude homology.

The real projective plane can be thought of as the two-sphere quotiented out by the antipodal map. The antipodal map acts on the icosahedral triangulation of the two-sphere. So quotienting the icosahedron by the antipodal map gives us a triangulation T 0T_0 of P 2\mathbb{R} P^2 which is in fact the triangulation with fewest simplices. Here is a picture of it.

rp2_minimal_triangulation.png

I’ve numbered the vertices and we will label each simplex by its vertices, so (0,1,2)(0, 1, 2) is a 2-simplex you can see in the triangulation above. The label for a simplex will have the vertices in linear order.

Let’s recall how we get the 22-torsion element in homology. If we take the boundary \partial of the ten 2-simplices with the orientation drawn above then we get

(3,4)+(4,5)(3,5)+(3,4)+(4,5)(3,5). (3, 4)+(4,5)-(3,5) + (3, 4)+(4,5)-(3,5).

(We write (3,5)-(3,5) rather than (5,3)(5,3) because of the orientation conventions which I will gloss over. You can figure them out if you’re interested/concerned. I think they are right!)

As 2=0\partial^2=0 this boundary chain is a cycle. To get homology we quotient cycles out by boundaries, so this cycle is trivial in homology, which means

2[(3,4)+(4,5)(3,5)]=0H 1 simp(T 0). 2[(3, 4)+(4,5)-(3,5)] = 0 \in \mathrm{H}_1^{\mathrm{simp}}(T_0).

Thus [(3,4)+(4,5)(3,5)][(3, 4)+(4,5)-(3,5)] is a 22-torsion element. Off the top of my head I can’t think of a nice argument showing that this is non-trivial in homology, but hopefully someone can provide one in the comments! Anyway, we’re going to need this later.

Constructing the graph and the magnitude cycles

Following Kaneta and Yoshinaga, we are now going to use the above triangulation T 0T_0 to build our graph G(T 0)G({T_0}). We take the simplices of the triangulation as the nodes of the graph and have an edge στ\sigma \to \tau if σ\sigma is a facet of τ\tau, remember that a facet is a face of maximal dimension. We then add top and bottom nodes, so bottom\mathrm{bottom} has an arrow to each 00-simplex and top\mathrm{top} has an arrow from each 22-dimensional simplex. Here is the graph again. You should be able to see the six vertices, fifteen edges and ten faces of the original triangulation.

graph

A more sophisticated way of saying what we’ve done is the following. The vertices in the triangulation form a poset, the face poset, with the ordering is ‘is a face of’. We add top and bottom elements to that poset. We then take the Hasse diagram which is the graph which has the elements of the poset as its nodes and where there is an edge xyx\to y if xyx\le y but there is no zz with xzyx\le z\le y. Clearly this process gives us a graph G(T)G({T}) from any triangulation TT of a manifold.

We can obtain the graph G(T 0)G({T_0}) in SageMath with a couple of commands:

triangulation = simplicial_complexes.RealProjectivePlane()
poset = triangulation.face_poset().with_bounds()
graph = poset.hasse_diagram()

To see the above picture you can use the following command:

show(poset.plot())

For what we do next it doesn’t matter if we stick with this directed graph or take the associated undirected graph as we are going to be forced to only consider upward pointing edges.

The magnitude chains for this graph

In the previous post I explained that for a finite graph GG the magnitude chain groups are defined as follows.

A chain generator is a tuple of the form c=(x 0,x 1,,x k1,x k),c= (x_0, x_1,\dots, x_{k-1},x_k), where each x ix_i is a node of the graph GG and x i1x ix_{i-1}\ne x_{i}. The degree is deg(c)=k\mathrm{deg}(c)=k and the length is len(c)=d(x i1,x i)\mathrm{len}(c)=\sum \mathrm{d}(x_{i-1}, x_i).

The face map i\partial_i for i=1,,k1i=1,\dots, k-1 is defined by:

i(x 0,,x k)={(x 0,,x i^,,x k) ifx i1<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} \lt x_{i} \lt x_{i+1}, \\ 0 & \text{otherwise}. \end{cases}

where x i1<x i<x i+1x_{i-1} \lt x_{i}\lt x_{i+1} means that x ix_i lies on a shortest path between x i1x_{i-1} and x i+1x_{i+1}, i.e., d(x i1,x i)+d(x i,x i+1)=d(x i1,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}).

Neither the length nor the endpoints of chains are altered by the face maps, so the magnitude complex splits up into subcomplexes with specified endpoints. So if we define

MC k,l y,z(G)=(y,x 1,,x k1,z)|chain generator of length l. MC^{y,z}_{k,l}(G)=\left\langle (y, x_1,\dots, x_{k-1},z) \,\, |\,\, \text{chain generator of length }\,\,l\right\rangle.

Then the magnitude chain complex splits as

MC *,*(G)= y,zG lMC *,l y,z(G) MC_{\ast,\ast}(G)=\bigoplus_{y,z\in G}\bigoplus_l MC^{y,z}_{\ast,l}(G)

We will concentrate on the subcomplex of length-four chains from the bottom element to the top element in our graph (here, four is dimension of P 2\mathbb{R} P^2 plus two). Writing b\mathrm{b} and t\mathrm{t} for the bottom and top elements we consider the magnitude chain complex MC *,4 b,t(G(T 0)MC^{\mathrm{b},\mathrm{t}}_{\ast,4}(G({T_0}). We will see that the homology of this is isomorphic to H˜ *+2(P 2)\widetilde{\mathrm{H}}_{\ast+2}(\mathbb{R} P_2) and so we get the embedding H˜ *(P 2)MC *+2,4(G)\widetilde{\mathrm{H}}_{\ast}(\mathbb{R} P_2)\hookrightarrow MC_{\ast+2,4}(G).

Looking at our graph it is easy to see that a length four chain must be of the form

(b,σ 1,,σ k1,t) (\mathrm{b}, \sigma_1, \dots,\sigma_{k-1},\mathrm{t})

where σ 1σ k1\sigma_1\subset \dots\subset\sigma_{k-1} is a sequence of simplices, each of which is a face of the following one, in other words it is flag of simplices in our original triangulation. Such a flag can be a full flag like (0)(0,1)(0,1,2)(0)\subset(0,1)\subset(0,1,2) in which each is a facet of the following simplex, or it can be a partial flag like (0)(0,1,2)(0)\subset (0,1,2).

Looking at the formula for the face maps you can see that given a generator corresponding to a flag of simplices, each facet of the generator corresponds to a flag with one of the simplices removed.

Those of you familiar with combinatorial topology might have spotted the connection with the barycentric subdivision construction. We will look a little more closely at these flags now.

Barycentric subdivision

One of the things you usually learn in a first course on algebraic topology is that if you have a triangulation of a space then you can form a finer triangulation – the barycentric subdivision – in the following way. Take the midpoint of each simplex in the original triangulation and use these as the vertices of the new triangulation, decomposing each of the old nn-simplices into (n+1)!(n+1)! new nn-simplices in ‘the obvious fashion.

For instance, if we take a triangle in our triangulation then each 11-simplex gets split into 22 new 11-simplices and the 22-simplex gets split into 66 new 22-simplices.

flags_of_simplices.png

Each new vertex can be labelled by the nn-simplex that it is the midpoint of. What then is ‘the obvious fashion’ for creating the new simplices? Well each new nn-simplex in the subdivision corresponds to a flag of old simplices σ 0σ 1σ n\sigma_0\subset \sigma_1\subset \dots \subset \sigma_n. We can picture the 22-simplex corresponding to (0)(0,1)(0,1,2)(0)\subset(0,1)\subset(0,1,2) and the 11-simplex corresponding to (0)(0,1,2)(0)\subset (0,1,2) as follows.

flags_of_simplices.png

It ought to be clear that for the nn-simplex in the subdivision corresponding to a flag σ 0σ 1σ n\sigma_0\subset \sigma_1\subset \dots \subset \sigma_n, each facet corresponds to a flag where one of the old simplices have been removed. So for (0)(0,1)(0,1,2)(0)\subset(0,1)\subset(0,1,2) the facets correspond to (0,1)(0,1,2)(0,1)\subset(0,1,2), (0)(0,1,2)(0)\subset(0,1,2) and (0)(0,1)(0)\subset(0,1).

So the barycentric subdivision TT', as a simplicial complex is isomorphic to the simplicial complex of flags where an nn-simplex is a flag σ 0σ 1σ n\sigma_0\subset \sigma_1\subset \dots \subset \sigma_n of simplices of the original triangulation TT. Well, there’s a subtlety here in that we shouldn’t forget the empty flag! The flags naturally form an augmented simplicial complex, meaning that there is a unique simplex in degree 1-1, the empty flag, which is the facet of every 00-simplex.

So the augmented chain complex C˜ * simp(T)\widetilde{\mathrm{C}}_\ast^{\mathrm{simp}}(T'), which is obtained from the usual chain complex by sticking a unique generator in degree 1-1, is isomorphic to the complex of flags. The homology of the augmented chain complex gives the reduced homology H˜ * simp(T)H˜ *(M)\widetilde{\mathrm{H}}_\ast^{\mathrm{simp}}(T')\cong \widetilde{\mathrm{H}}_\ast(M) which in practice means you kill off a copy of Z\mathrm{Z} in degree zero from the usual homology.

The important thing is that we are seeing here precisely the same structure that we saw in the magnitude chain group MC *,l b,t(G)MC_{\ast, l}^{b,t}(G). We should now make precise.

Synthesis of the two sides: the theorem

I’ve hopefully given the impression that a complex of flags of simplices is isomorphic to both the augmented chain complex of the barycentric subdivision of a triangulation and to a subcomplex of the magnitude chain complex of the graph of the triangulation. Let’s give a proper statement of this now. Kaneta and Yoshinaga have a more general statement in their paper, involving ranked posets rather than just triangulations, but for the purpose of finding torsion, the following will suffice.

Theorem. Suppose that TT is a finite triangulation of a mm-manifold MM, and that TT' is its barycentric subdivision, with G(T)G({T}) the graph obtained as above from the poset structure, then the isomorphism of (augmented) chain groups for k1k\ge -1

C˜ k simp(T) MC k+2,m+2 b,t(G(T)); σ 0σ 1σ k (b,σ 0,,σ k,t) \begin{aligned} \widetilde{\mathrm{C}}^{\mathrm{simp}}_k (T')&\xrightarrow{\sim} MC^{\mathrm{b},\mathrm{t}}_{k+2,m+2}(G({T})); \\ \sigma_0\subset \sigma_1\subset \dots \subset \sigma_k &\mapsto (b, \sigma_0,\dots, \sigma_k,t) \end{aligned}

commutes up to sign with the differentials. Thus this induces an isomorphism of homology groups

H˜ * simp(T)MH *+2,m+2 b,t(G(T)). \widetilde{\mathrm{H}}^{\mathrm{simp}}_\ast (T')\xrightarrow{\simeq} MH^{b,t}_{\ast+2,m+2}(G({T})).

As a corollary we get that the homology of MM embeds in the magnitude homology of the graph.

Corollary. With MM, TT, TT' and G(T)G({T}) as in the above theorem, the homology of MM embeds in the magnitude homology of the graph G(T)G({T}) via the following sequence of isomorphisms and embeddings:

H˜ *(M)H˜ * simp(T)H˜ * simp(T)MH *+2,m+2 b,t(G(T))MH *+2,m+2(G(T)). \widetilde{\mathrm{H}}_\ast(M) \cong \widetilde{\mathrm{H}}_\ast^{\mathrm{simp}}(T) \xrightarrow{\simeq} \widetilde{\mathrm{H}}^{\mathrm{simp}}_\ast (T') \xrightarrow{\simeq} MH^{b,t}_{\ast+2,m+2}(G({T})) \hookrightarrow MH_{\ast+2,m+2}(G({T})).

The payoff: a torsion element in the homology of our graph

We saw earlier on in this post that

[(3,4)+(4,5)(3,5)]H 1 simp(T 0). [(3, 4)+(4,5)-(3,5)] \in \mathrm{H}_1^{\mathrm{simp}}(T_0).

is the non-trivial 22-torsion element. We can follow this element through the sequence of maps above. We just need to note that the map 11-chains on TT to 11-chains on TT' rewrites each edge as the (signed) sum of its two half-edges, namely

C 1 simp(T) C 1 simp(T) (a,b) ((a)(a,b))((b)(a,b)). \begin{aligned} \mathrm{C}_1^{\mathrm{simp}}(T) &\to \mathrm{C}_1^{\mathrm{simp}}(T') \\ (a,b)&\mapsto \bigl((a) \subset (a,b)\bigr) - \bigl((b)\subset (a,b)\bigr). \end{aligned}

Then we get our non-trivial 22-torsion element in MH 3,4(G(T 0))MH_{3,4}(G({T_0})) to be

[(b,(3),(3,4),t) (b,(4),(3,4),t)+(b,(4),(4,5),t) (b,(5),(4,5),t)+(b,(5),(3,5),t)(b,(3),(3,5),t)]. \begin{split} [(\mathrm{b}, (3), (3,4), \mathrm{t}) &-(\mathrm{b}, (4), (3,4), \mathrm{t}) +(\mathrm{b}, (4), (4,5), \mathrm{t})\\ &-(\mathrm{b}, (5), (4,5), \mathrm{t}) +(\mathrm{b}, (5), (3,5), \mathrm{t}) -(\mathrm{b}, (3), (3,5), \mathrm{t})]. \end{split}

Thus we have a graph with torsion in its magnitude homology groups!

Posted at April 11, 2018 4:15 PM UTC

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

2 Comments & 0 Trackbacks

Re: Torsion: Graph Magnitude Homology Meets Combinatorial Topology

Thanks a lot for explaining (this aspect of) Kaneta and Yoshinaga’s paper, and thanks moreover for making the graph and the torsion class explicit.

Now that there is one example of a graph whose magnitude homology contains torsion, I can’t help wishing for more, especially since the graph G(T 0)G(T_0) constructed above has 33 vertices and 76 edges, which seems pretty big to me.

Q: Is there a graph / metric space which has fewer than 33 vertices / elements and whose magnitude homology has torsion?

One could consider starting with G(T 0)G(T_0) and then deleting or contracting edges to make a smaller graph. You told me by email that deleting edges destroys the torsion property. (Because in some sense this corresponds to puncturing P 2\mathbb{R}P^2.) But do you know anything about what happens if you contract?

Q: Is there a graph or metric space with torsion in MH 2,l()MH_{2,l}(-)?

Posted by: Richard Hepworth on April 23, 2018 11:07 AM | Permalink | Reply to this

Re: Torsion: Graph Magnitude Homology Meets Combinatorial Topology

Good questions! And I know the answer to neither of them.

When I said that you’d destroy the torsion by removing edges or vertices, what I meant was that I couldn’t see how to remove things without destroying the torsion, as all of the the edges are used in showing that the given class is torsion. I didn’t mean to say that I knew that it couldn’t be done.

Posted by: Simon Willerton on April 23, 2018 10:27 PM | Permalink | Reply to this

Post a New Comment