The n-Category Café

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