## April 12, 2023

### Eulerian Magnitude Homology

#### Posted by Tom Leinster

Guest post by Giuliamaria Menara

Magnitude homology has been discussed extensively on this blog and definitely needs no introduction.

A lot of questions about magnitude homology have been answered and a number of possible application have been explored up to this point, but magnitude homology was never exploited for the structure analysis of a graph.

Being able to use magnitude homology to look for graph substructures seems a reasonable consequence of the definition of boundary map $\partial_{k,\ell}$. Indeed, a tuple $(x_0,\dots,x_k) \in MC_{k,\ell}$ is such that $\partial_{k,\ell}(x_0,\dots,x_k)=0$ if for every vertex $x_i \in \{x_1,\dots,x_{k-1} \}$ it holds that $len(x_{i-1},\hat{x_i},x_{i+1}) \lt len (x_{i-1},x_i,x_{i+1})$. In other words, if every vertex of the tuple is contained in a small enough substructure, which suggests the presence of a meaningful relationship between the rank of magnitude homology groups of a graph and the subgraph counting problem.

A major problem in exploring this relationship comes from the fact that the definition of $MC_{k,\ell}(G)$ only asks for consecutive vertices to be different. That is, if $x_0$ and $x_1$ are two adjacent vertices in $G$ an acceptable tuple in $MC_{5,4}(G)$ is $(x_0,x_1,x_0,x_1,x_0)$.

Tuples of this kind inducing a path that just revisits again and again the same edge (an more in general, tuples inducing non-eulerian trails) do not provide any insight about the meaning of magnitude homology. With this motivation, we introduce a slightly different definition of magnitude chain, considering the subgroup of $MC_{k,l}(G)$ where a vertex (and therefore an edge) is never required to be revisited.

Definition (Eulerian magnitude chain)   Let $G$ be a graph. We define the eulerian $(k,\ell)$-magnitude chain $EMC_{k,\ell}(G)$ to be the free abelian group generated by tuples $(x_0,\dots,x_k)$ of vertices of $G$ such that $x_i \neq x_j$ for all distinct $0\leq i,j \leq k$ and $len(x_0,\dots,x_k)=\ell$.

Taking as differential the one induced by $MC_{\ast,\ell}(G)$ we can construct the eulerian magnitude chain complex $EMC_{\ast,\ell}(G)$:

$\cdots \to EMC_{k+1,\ell}(G) \xrightarrow{\partial_{k+1,\ell}} EMC_{k,\ell}(G) \xrightarrow{\partial_{k,\ell}} EMC_{k-1,\ell}(G) \to \cdots$

and subsequently define the eulerian $(k,\ell)$-magnitude homology group

$EMH_{k,\ell}(G) = H_k(EMC_{\ast,\ell}(G)) = \frac{\ker(\partial_{k,\ell})}{\mathrm{im}(\partial_{k+1,\ell})}.$

Example   Consider the following graph $G$:

We want to compare $MH_{2,2}(G)$ and $EMH_{2,2}(G)$.

The magnitude chain $MC_{2,2}(G)$ is generated by

\begin{aligned} &(0,1,0), (0,1,2), (0,1,3), \\ &(1,0,1), (1,2,1), (1,2,3), (1,3,1), (1,3,2),\\ &(2,1,0), (2,1,2), (2,1,3), (2,3,1), (2,3,2),\\ &(3,1,0), (3,1,2), (3,1,3), (3,2,1), (3,2,3), \end{aligned}

while $MC_{1,2}(G)$ is generated by

$(0,2), (2,0), (0,3), (3,0).$

We see that $MH_{2,2}(G)=\ker(\partial_{2,2})$ is generated by all elements in $MC_{2,2}(G)$ apart from

$(0,1,2), (2,1,0), (0,1,3), (3,1,0)$

and thus has rank 14.

On the other hand, the eulerian chain $EMC_{2,2}(G)$ is generated by

$(0,1,2), (0,1,3), (1,2,3), (1,3,2), (2,1,0), (2,1,3), (2,3,1), (3,1,0), (3,1,2), (3,2,1),$

while $EMC_{1,2}(G)=MC_{1,2}$ is generated by

$(0,2), (2,0), (0,3), (3,0).$

We have now that $EMH_{2,2}(G)=\ker(\partial_{2,2})$ is generated by all elements in $MC_{2,2}(G)$ apart from

$(0,1,2), (2,1,0), (0,1,3), (3,1,0),$

and thus has rank 6, as the number of permutations of the triangle [1,2,3].

Remark   We point out that all definitions and properties regarding magnitude homology proved in

Richard Hepworth and Simon Willerton, Categorifying the magnitude of a graph, Homology, Homotopy and Applications 19(2) (2017), 31–60

and

Tom Leinster and Michael Shulman, Magnitude homology of enriched categories and metric spaces, Algebraic & Geometric Topology 21 (2021), no. 5, 2175–2221

continue to be valid for eulerian magnitude homology. In particular, with this new definition, $EMH_{0,0}(G)$ and $EMH_{1,1}(G)$ are still counting the number of vertices and edges in a graph respectively, since the generators of the groups $MC_{0,0}(G)$ and $MC_{1,1}(G)$ already satisfy the condition of not revisiting vertices.

Now, in order to account for the elements in $MC_{k,\ell}(G)$ containing the repetition of at least a vertex we define the discriminant magnitude chain as the quotient between the standard magnitude chain and the eulerian one.

Definition (Discriminant magnitude chain)   Let $G$ be a graph. We define the discriminant $(k,\ell)$-magnitude chain $DMC_{k,\ell}(G)$ as

$DMC_{k,\ell}(G) = \frac{MC_{k,\ell}(G)}{EMC_{k,\ell}(G)}$

Denoting by $[\cdot]_E$ the equivalence classes in $DMC_{k,\ell}(G)$, we define the differential map $\tilde{\partial}_{k,\ell}$ as

$\tilde{\partial}_{k,\ell}([x_0,\dots,x_k]_N) = [\partial_{k,\ell}(x_0,\dots,x_k)]_E.$

## Splitting result

(Section removed following the conversation below.)

## Applications

### Subgraph counting

The example above suggests the presence of the relation we were looking for between the subgraph counting problem and the ranks of magnitude homology groups.

Lemma  Let $Z$ be the number of basis elements $\overline{x} \in EMC_{2,2}$ such that $\partial_{2,2}(\overline{x})=0$. The number of triangles occurring in $G$ is $\frac{Z}{6}$.

Proof  Consider a $3$-tuple $\overline{x}=(x_0,x_1,x_2)$ of length 2. Since $\overline{x}$ has length 2, $\{x_0,x_1\}$ and $\{x_1,x_2\}$ are edges of $G$. Also, $\partial_{2,2}(\overline{x})=0$ if and only if the shortest path between $x_0$ and $x_2$ has length smaller than $2$, that is, if removing the required vertex $x_1$ we obtain a 2-tuple of length 1. This implies that there exists and edge $\{x_0,x_2\}$ and thus a triangle with vertices $x_0,x_1,x_2$.

It is immediate to see that the above holds for all permutations of $\overline{x}$, which implies that the number of triangles occurring in $G$ is given by the number of basis elements in the kernel of $\partial_{2,2}$ divided by the cardinality of the automorphisms group of the triangle $D_3$.

Proceeding in a similar way, it also possible to show that the number of $k$-cliques in $G$ is upper bounded by $\left\lfloor\frac{Z}{k!}\right\rfloor$, where $Z$ is the number of basis elements $\overline{x} \in EMC_{k,k}$ such that $\partial_{k,k}(\overline{x})=0$.

### A vanishing threshold for the first diagonal of EMH of Erdős–Rényi random graphs

Let $G=G=(n,p)=G(n,n^{-\alpha})$ be an Erdős–Rényi graph.

In order to produce a vanishing threshold for $EMH_{k,k}(G)$ we identify what kind of subgraph $H$ is induced by a cycle in $EMH_{k,k}(G)$ and give an estimate for the occurrences of $H$ in $G$.

Take $[x_0,\dots,x_k] \in EMH_{k,k}(G)$. Then for every $i=1,\dots,k-1$ the edge $(x_{i-1},x_{i+1})$ exists and the induced subgraph $H$ is as shown:





Now, the number of edges contained in such graph is $k+(k-1)$ (black edges plus blue edges). Hence, calling $a_H$ the number of automorphisms of $H$, the number of copies of $H$ expected in $G$ is

\begin{aligned} N_H &= \binom{n}{k+1} a_H p^{2k-1} \\ &\sim n^{k+1} \frac{a_H}{(k+1)!} n^{\alpha(1-2k)} \\ &= \frac{a_H}{(k+1)!} n^{\alpha(1-2k)+(k+1)} \xrightarrow{n\to \infty} \begin{cases} 0, \ \text{ if } \ \alpha \gt \frac{k+1}{2k-1} \\ \infty, \ \text{ if }\ 0 \lt \alpha \lt \frac{k+1}{2k-1}. \end{cases} \end{aligned}

The computation above implies the following.

Lemma  Let $G$ be an Erdős–Rényi graph on $n$ vertices and set $p=n^{-\alpha}$. The first diagonal of the eulerian magnitude homology $EMH_{k,k}(G)$ vanishes for $\alpha \gt \frac{k+1}{2k-1}$.

Posted at April 12, 2023 9:34 AM UTC

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

### Re: Eulerian Magnitude Homology

Thanks for this post, Giulia!

Sorry about the various formatting glitches when I posted this earlier today. Hopefully they’re all fixed now, but I trust people will let me know if I missed any.

Let me see if I can start to get to grips with this.

When we look at the magnitude homology of a graph, we usually take the $k$-chains to be generated by $(k+1)$-tuples of vertices $(x_0, \ldots, x_k)$ where

$x_0 \neq x_1 \neq \cdots \neq x_k.$

In other words, $x_i$ is never equal to $x_{i + 1}$ — but it could, for instance, be equal to $x_{i + 2}$.

You go further, and look at the $(k + 1)$-tuples where all the $x_0, \ldots, x_k$ are distinct. No backtracking allowed! And these are the Eulerian magnitude chains.

Of course, there are far fewer Eulerian chains than ordinary ones, because the nondegeneracy condition is more stringent. So that should make computations easier.

You then measure the difference between the ordinary and Eulerian magnitude chains, or more exactly the quotient of the former by the latter. And that’s your discriminant magnitude chain group: $DMC = MC/EMC$.

The cool thing is, at the homological level, this quotient splits:

$MH = EMH \oplus DMH.$

It’s clear from the definitions that $DMH$ is going to be a quotient of $MH$, but the fact that it’s a direct summand is less obvious.

The upshot is that we can split magnitude homology into two parts: essentially, those generated by the chains $(x_0, \ldots, x_k)$ containing no repeats, and those containing some repeats. This is nice!

That’s just about the splitting result so far, without touching the stuff on Erdős–Rényi graphs…

Posted by: Tom Leinster on April 12, 2023 10:18 PM | Permalink | Reply to this

### Re: Eulerian Magnitude Homology

I haven’t understood the splitting result. Is it possible to elaborate?

From the lemma it seems that there is a short exact sequence

$0 \to EMH_{k,\ell}(G) \xrightarrow{\iota_\ast} MH_{k,\ell}(G) \xrightarrow{\pi_\ast} DMH_{k,\ell}(G) \to 0.$

“It follows that” there is a splitting

$MH_{k,\ell}(G)\cong EMH_{k,\ell}(G) \oplus DMH_{k,\ell}(G).$

How does this follow? Is this a canonical splitting?

Unless I’ve confused myself, a classic example of a short exact sequence that doesn’t split is the following.

$0 \to \mathbb{Z} \xrightarrow{\times 2} \mathbb{Z} \xrightarrow{ } \mathbb{Z}/2\mathbb{Z} \to 0.$

Posted by: Simon Willerton on April 13, 2023 10:45 AM | Permalink | Reply to this

### Re: Eulerian Magnitude Homology

If I thought about all of this correctly, the point is that we can consider a cycle in $EMH_{k,\ell}(G)$ as a cycle in $MH_{k,\ell}$. Then this gives us a homology class $[(x_0,\dots,x_k)]_E \in EMH_{k,\ell}(G)$ and also $[(x_0,\dots,x_k)] \in MH_{k,\ell}(G)$. In these terms, the homomorphism induced by the inclusion is $[(x_0,\dots,x_k)]_E \overset{i_{*}}{\rightarrow} [(x_0,\dots,x_k)]$, and because of the specific (very rigid) construction it cannot happen that a cycle $(x_0,\dots,x_k)$ which is non-trivial in $EMH$ becomes trivial in $MH$.

Then we define the splitting sequence $0 \to EMH_{k,\ell}(G) \overset{i_{*}}{\rightarrow} MH_{k,\ell}(G) \to coker(i) \to 0$ and verify that $coker(i) \cong DMH_{k,\ell}(G)$.

Posted by: Giuliamaria Menara on April 13, 2023 3:22 PM | Permalink | Reply to this

### Re: Eulerian Magnitude Homology

Hi Giuliamaria, we might have crossed wires here. I’m willing to believe the lemma (but I haven’t checked it), so you have the short exact sequence. However, I don’t see how you then get the splitting. These are two different things. In general, it does not follow from a short exact sequence of abelian groups

$0 \to A \to B \to C \to 0$

that there is a splitting

$B \cong A \oplus C;$

you would typically need some more structure, for instance having a morphism $C \to B$, in order to deduce the existence of a splitting.

Do you have a morphism $DMH_{k,\ell}(G) \to MH_{k,\ell}(G)$?

Another situation in which a short exact sequence leads to a splitting is when you are talking about vector spaces rather than abelian groups. You didn’t define precisely what you meant by the homology groups: if you were working with, say, rational coefficients then the sequence would split, though it wouldn’t necessarily split canonically.

Posted by: Simon Willerton on April 13, 2023 5:00 PM | Permalink | Reply to this

Hello Simon. As a matter of fact, at an initial stage I was working with $\mathbb{Q}$ coefficients (to kill torsion) and I first came to the splitting result in the context of vector spaces (and you are right, I should have specified this).

Although, even in the case of abelian groups the result does hold. Indeed, from the construction of $EMH_{k,\ell}$ you get that the kernel of $i_{\star}$ is trivial. Then $i_{\star}$ is injective, so it admits a left inverse, and by the splitting lemma this is enough for the sequence to split.

Posted by: Giuliamaria Menara on April 14, 2023 9:52 AM | Permalink | Reply to this

### Re: Eulerian Magnitude Homology

Then $i_\ast$ is injective, so it admits a left inverse

I don’t follow this step. The map $i_\ast$ is an injective homomorphism of abelian groups, but that by itself doesn’t imply it admits a left inverse. (E.g. multiplication by $2$ is an injective homomorphism of abelian groups $\mathbb{Z} \to \mathbb{Z}$, but has no left inverse.) What’s going on?

Posted by: Tom Leinster on April 14, 2023 3:50 PM | Permalink | Reply to this

### Re: Eulerian Magnitude Homology

I was really sloppy in giving this argument. I am going to construct a morphism $j_{*}: MH_{k,\ell} \to EMH_{k,\ell}$ such that its composition with $i_{\star}$ is the identity on $EMH_{k,\ell}$.

First, notice that since the basis of $EMC_{k,\ell}$ is a subset of the basis of $MC_{k,\ell}$ and because the boundary map of the eulerian magnitude chain is defined as just a restriction of the boundary map on the magnitude chain $MC_{*,\ell}$, the an element $[\bar{x}]_E \in EMH_{k,\ell}$ can be mapped by $i_{\star}$ to the element $[\bar{x}] \in MH_{k,\ell}$ with the same representative and it never happens that a non-trivial cycle in $EMH$ becomes trivial in $MH$.

Then, consider the morphism $(\pi \circ \phi) : \ker(\partial_{k,\ell}(MC_{k,\ell})) \to EMH_{k,\ell}$. The first map $\phi : \ker(\partial_{k,\ell}(MC_{k,\ell})) \to \ker(\partial_{k,\ell}(EMC_{k,\ell}))$ sends a basis element $\bar{x}$ of $\ker(\partial_{k,\ell}(MC_{k,\ell}))$ to itself if $\bar{x} \in \ker(\partial_{k,\ell}(EMC_{k,\ell}))$ (i.e. if all vertices in $\bar{x}$ are different) and to the identity otherwise. The second map is the quotient $\pi: \ker(\partial_{k,\ell}(EMC_{k,\ell})) \to \frac{\ker(\partial_{k,\ell}(EMC_{k,\ell}))}{im(\partial_{k+1,\ell}(EMC_{k+1,\ell}))} = EMH_{k,\ell}$.

Now, since $im(\partial_{k+1,\ell}(MC_{k+1,\ell})) \subseteq \ker(\pi \circ \phi)$ then the morphism $(\pi \circ \phi)$ factors through $\frac{\ker(\partial_{k,\ell}(MC_{k,\ell}))}{im(\partial_{k+1,\ell}(MC_{k+1,\ell}))} = MH_{k,\ell}$, providing us with a morphism $j_{*}: MH_{k,\ell} \to EMH_{k,\ell}$.

With this construction, $j_{*} \circ i_{\star}$ is the identity on $EMH_{k,\ell}$.

Posted by: Giuliamaria Menara on April 17, 2023 12:05 PM | Permalink | Reply to this

### Re: Eulerian Magnitude Homology

Thanks for expanding. I have another question!

You said

First, notice that since the basis of $\mathrm{EMC}_{k,\ell}$ is a subset of the basis of $\mathrm{MC}_{k,\ell}$ and because the boundary map of the eulerian magnitude chain is defined as just a restriction of the boundary map on the magnitude chain [… then] it never happens that a non-trivial cycle in EMH becomes trivial in MH.

I don’t see how that follows. You’re saying that it is never the case that the boundary of a non-Eulerian chain is Eulerian. That may be true but it doesn’t seem to follow from the first half of the sentence.

Consider the chain complex $\mathrm{C}$ generated in degree one by $a$ and in degree two by $b$, with $\mathrm{d}(b) = a$ and $\mathrm{d}(a) = 0$. Take $\mathrm{EC}$ to be the sub-chain complex generated by $a$ with $\mathrm{d}(a) = 0$. This seems to satisfy the first half of your sentence. But it doesn’t seem to satisfy the conclusion of the sentence as $[a]$ is non-trivial in the homology of $\mathrm{EC}$ but trivial when mapped into the homology of $\mathrm{C}$.

Posted by: Simon Willerton on April 17, 2023 1:52 PM | Permalink | Reply to this

### Re: Eulerian Magnitude Homology

Given the splitting result, we should be now able to define the Eulerian magnitude and discriminant magnitude of a graph as the graded Euler characteristics of $EMH(G)$ and $DMH(G)$ respectively, with the usual magnitude being the sum of Eulerian magnitude and discriminant magnitude, right?

I wonder if there is a more direct, decategorified way of defining those. Not that I see any immediate motivation for doing so, I’m just trying to clarify what’s going on here for myself.

Posted by: Mark Meckes on April 14, 2023 3:20 PM | Permalink | Reply to this

### Just a comment on the formatting:

Posted by: Jacques Distler on April 13, 2023 5:26 AM | Permalink | PGP Sig | Reply to this

### Re: Just a comment on the formatting:

Aha, thanks, Jacques. Evidently I missed a trick: I could have just included the tikz code that Giuliamaria sent me, rather than using an image file. I’ve made this improvement now. Much appreciated.

Posted by: Tom Leinster on April 13, 2023 11:28 PM | Permalink | Reply to this

### Re: Just a comment on the formatting:

Evidently I missed a trick: I could have just included the tikz code that Giuliamaria sent me, rather than using an image file.

Right. And, as you can see, it can also be used in comments.

The only non-obvious thing is that, if you have a \usetikzlibrary{...} command (which would normally be placed in the header of your LaTeX file), you should embed it in the tikz code instead.

Posted by: Jacques Distler on April 14, 2023 3:06 AM | Permalink | PGP Sig | Reply to this

### Re: Eulerian Magnitude Homology

Thanks, this looks interesting.

It would be nice to see more computations and maybe I can help with that. This is an invitation for anyone interest in this to lend a hand. The SageMath code for computing graph magnitude homology has not been as obviously available as it might have been (it was buried in the arxiv submission) so I’ve just uploaded a jupyter notebook to GitHub.

I don’t have the time or energy to modify this to compute Eulerian magnitude homology but it shouldn’t be difficult and it should be fun! However, be aware that the code was written quite a while ago and I would probably write it neater now.

Now for some confessions of ignorance on the latest “best practice” for scientific code.

1. I don’t know if a jupyter notebook is the best format or not but it looks easier to read than straight code.
2. I don’t know if GitHub is the right place for the code, but it was a quick and easy place to put it.
3. I don’t know much about GitHub conventions, so I might not have the repository set up sensibly.

Please let me know if you are more knowledgeable in such things and can help me improve the availability of the code.

Posted by: Simon Willerton on April 13, 2023 10:19 AM | Permalink | Reply to this

### Re: Eulerian Magnitude Homology

I coded MH up in MATLAB a few years back and am doing it again from scratch on my personal time. I plan to incorporate EMH (which BTW Giulia this is lovely). Stay tuned.

NB. Because for symmetric dissimilarities blurred MH is basically Vietoris-Rips, it’s particularly interesting to consider asymmetric dissimilarities. For example I’ve computed the MH of DAGs that correspond to neural network architectures and it’s considerably richer than path homology, and also more scalable because of the direct sum decomposition on sources and targets. EMH should of course help further with scalability. I imagine there are lots of applications to cyber and connectome data in the directed arena.

Posted by: Steve Huntsman on April 13, 2023 1:13 PM | Permalink | Reply to this

### Re: Eulerian Magnitude Homology

Adrian Doña Mateo (currently doing a PhD with me) did unearth the Sage code from your arXiv submission, and got it working, but I think he said he first had to spend a while updating it so that it worked with the current version of Python. Presumably the code you just put on GitHub does have that virtue, even given your other humble disclaimers :-)

Posted by: Tom Leinster on April 13, 2023 11:31 PM | Permalink | Reply to this

### Re: Eulerian Magnitude Homology

Ah, yes, I forgot about the changes, thanks for mentioning it.

Last year, Emily Roff (previously doing a PhD with you) pointed out to me, while I was visiting, that she couldn’t get the code to work with the current version of SageMath. This was mainly because of a big switch in SageMath 9 in which they moved to using Python 3. A significant difference between Python 2 and Python 3 is that in one you can type print a and in the other you need to type print(a).

Anyway, I fixed all the print statements and made some very minor changes to the code so Emily could run it directly in SageMath. The version I’ve put on GitHub is just a slightly prettier version in that I broke parts of it into notebook cells.

Posted by: Simon Willerton on April 14, 2023 8:57 AM | Permalink | Reply to this

### Re: Eulerian Magnitude Homology

I’m trying to understand the proof of lemma for the splitting result. In the post it says the following.

$\partial_{k+1}(x_0,\dots,x_{k+1})]= \begin{cases} [y_0,\dots,y_k], \ \text{ if }\ y_i\neq y_j \ \text{ for all }\ i,j,\\ [0], \text{ otherwise.} \end{cases}$

The left-hand side seems to have a couple of typos. Are you missing a $[$ and an $\ell$?

As for the right-hand side, I don’t think you’ve said what $y_i$ is. Can you say what $y_i$ is?

Also, does $[]_N$ mean the same as $[]_E$?

Posted by: Simon Willerton on April 17, 2023 1:19 PM | Permalink | Reply to this

### Re: Eulerian Magnitude Homology

Hello Simon, sorry for the late reply. Yes there are a few typos: the missing $[$ and $\ell$, and $[]_N$ instead of $[]_E$.

Posted by: Giuliamaria Menara on April 21, 2023 8:45 AM | Permalink | Reply to this

### Re: Eulerian Magnitude Homology

Also, $y_i$ is a vertex and $[y_0,...y_k]$ is an element in $EMH_{k,\ell}$ - I just didn’t want to use the same vertex notation for elements in $DMH$ and $EMH$.

Posted by: Giuliamaria Menara on April 21, 2023 10:10 AM | Permalink | Reply to this

Post a New Comment