### 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 theeulerian $(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 Applications19(2) (2017), 31–60

and

Tom Leinster and Michael Shulman, Magnitude homology of enriched categories and metric spaces,

Algebraic & Geometric Topology21 (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 thediscriminant $(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}$.*

ProofConsider 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}$.*

## 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

allthe $x_0, \ldots, x_k$ are distinct. No backtracking allowed! And these are theEulerian 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 chaingroup: $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

quotientof $MH$, but the fact that it’s adirect summandis 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…