Girth, magnitude homology and phase transition of diagonality

Abstract

This paper studies the magnitude homology of graphs focusing mainly on the relationship between its diagonality and the girth. The magnitude and magnitude homology are formulations of the Euler characteristic and the corresponding homology, respectively, for finite metric spaces, first introduced by Leinster and Hepworth–Willerton. Several authors study them restricting to graphs with path metric, and some properties which are similar to the ordinary homology theory have come to light. However, the whole picture of their behaviour is still unrevealed, and it is expected that they catch some geometric properties of graphs. In this article, we show that the girth of graphs partially determines the magnitude homology, that is, the larger girth a graph has, the more homologies near the diagonal part vanish. Furthermore, applying this result to a typical random graph, we investigate how the diagonality of graphs varies statistically as the edge density increases. In particular, we show that there exists a phase transition phenomenon for the diagonality.

1. Introduction

The magnitude of finite metric spaces was introduced by Leinster [12] as a formulation of the Euler characteristic of finite metric spaces. The magnitude has several interesting properties such as the multiplicativity property and the inclusion–exclusion principle, which seems parallel to the case of the ordinary Euler characteristic of topological spaces. However, the whole picture of the behaviour of the magnitude is unrevealed, and that is attracting people in several areas of mathematics. In particular, the magnitude of finite graphs, which takes values in formal power series with $\mathbb {Z}$-coefficients, is studied by several authors so far [1, 4, 8, 9, 11]. Throughout this article, we call a finite, simple and undirected graph without loops just a graph.

The magnitude homology of graphs is a categorification of the magnitude, first introduced by Hepworth–Willerton [9] as an analogy of ordinary homology theory. It is a bigraded abelian group whose Euler characteristic coincides with the magnitude, and the multiplicativity property and the inclusion–exclusion principle are formulated as the Künneth and the Mayer–Vietoris theorems, respectively [9]. Their beautiful theory enables us to compute the magnitude and magnitude homology of graphs. For example, Gu [8] showed a remarkable compatibility of the magnitude homology with the algebraic Morse theory, and he computed the magnitude homology of several types of graphs including well-known classical ones. Bottinelli–Kaiser [4] studied the magnitude homology of median graphs, using the retraction between the homology groups. More or less, the remarkable property concerned in their works is the diagonality of graphs, first suggested in [9], which guarantees a simpleness of the magnitude homology in some sense.

In this article, we show that the girth of graphs partially determines the magnitude homology. More specifically, the larger girth a graph has, the more homologies near the diagonal part vanish. Furthermore, by using this result, we investigate how the diagonality of graphs varies statistically as the edge density (proportion of the number of edges to that of possible edges) increases. In particular, we show that there exists a phase transition phenomenon for the diagonality. As shown in [9], a tree (or more generally, a forest) which has low edge density is diagonal. It is also known that a few graphs with high edge density are diagonal. This fact is shown in [9] for complete graph, and in [8] for pawful graph (see definition 2.9). However, graphs with intermediate edge density are more likely to be non-diagonal. To describe this phenomenon statistically, we consider the Erdős–Rényi graph model which is a typical random graph model extensively studied since the 1960s [5–7]. Given $n\in \mathbb {N}$ and $p\in [0,1]$, an Erdős–Rényi graph $G_{n,p}$ with parameters $n$ and $p$ is a random graph with $n$ vertices, where the edge between each pair of vertices is added independently with probability $p$.

Now, we explain our results in the following. We first state a relationship between the girth of graphs and the magnitude homology. They will be proved in an algebraic and combinatorial way in § 3. Let $G$ be a graph and $x \in V(G)$ be a vertex. We define the local girth of $G$ at $x$ by

\[ \operatorname{gir}_x(G) := \inf\{i\ge3\mid\text{ there exists a cycle of length}\ i\ \text{in}\ G\ \text{containing}\ x\}. \]

We also define the girth of $G$ by $\operatorname {gir}(G) := \min _{x} \operatorname {gir}_{x}(G).$ Note that the following statements are compatible with the computation of the magnitude homology for trees and cycle graphs in [8, 9], respectively. In particular, corollary 1.4 is a generalization of the computation of the magnitude homology of trees in [9, corollary 6.8]. Below, $\operatorname {MH}_{*,*}(G)$ is the magnitude homology of $G$, and the superscript $x$ of $\operatorname {MH}_{*,*}^x(G)$ indicates the restriction on the starting point (see § 2.2 for the definitions).

Theorem 1.1 Let $\ell \geq 1$. If $\operatorname {gir}_{x}(G)\geq 5$, then $\operatorname {MH}^{x}_{\ell, \ell }(G) \cong \mathbb {Z}^{{\rm deg}\,x}.$ Here, ${\rm deg}\,x$ denotes the degree of the vertex $x$.

The following is an immediate corollary of theorem 1.1. It is also obtained by Sazdanovic–Summers in [14, thoerem 4.3].

Corollary 1.2 Let $\ell \geq 1$. If $\operatorname {gir}(G)\geq 5$, then $\operatorname {MH}_{\ell, \ell }(G) \cong \mathbb {Z}^{2\#E(G)}.$ Here, $\#E(G)$ denotes the number of edges of $G$.

The following are extensions of the above.

Theorem 1.3 Let $\ell \geq 1$ and $i\ge 0$. If $\operatorname {gir}_{x}(G)\geq 2i + 5$, then

\[ \operatorname{MH}^{x}_{\ell -j, \ell}(G) \cong\begin{cases} \mathbb{Z}^{{\rm deg}\,x}, & j = 0,\\ 0, & 1 \leq j \leq i. \end{cases} \]

Corollary 1.4 Let $\ell \geq 1$ and $i\ge 0$. If $\operatorname {gir}(G)\geq 2i + 5$, then

\[ \operatorname{MH}_{\ell -j, \ell}(G) \cong\begin{cases} \mathbb{Z}^{2\# E(G)}, & j = 0,\\ 0, & 1 \leq j \leq i. \end{cases} \]

The above results will be proved by using the algebraic Morse theory. The following gives a criterion for the diagonality of graphs. Let $e \in E(G)$ be an edge. We define the local girth of $G$ at $e$ by

\[ \operatorname{gir}_e(G) := \inf\{i\ge3\mid\text{there exists a cycle of length}\ i\ \text{in}\ G\ \text{containing}\ e\}. \]

Note that we have $\operatorname {gir}(G) = \min _{e} \operatorname {gir}_{e}(G)$.

Theorem 1.5 Let $G$ be a graph and $e \in E(G)$ be an edge. If $k := \operatorname {gir}_e(G)\in [5,\infty )$, then $\operatorname {MH}_{2, \ell }(G) \neq 0$ for $\ell = \lfloor {(k+1)}/{2} \rfloor$.

Corollary 1.6 If $G$ is a diagonal graph, then $\operatorname {gir}(G)=3,4$, or $\infty$.

By considering $k = 2i + 5$ or $2i+6$ in theorem 1.5, it turns out that the range $1 \leq j \leq i$ guaranteeing the vanishing of the magnitude homology groups in corollary 1.4 is optimal (see table I).

TABLE I. Ranks of the magnitude homology described in corollary 1.4 and theorem 1.5

Next we state several stochastic properties of the magnitude homology of the Erdős–Rényi random graph model. They will be shown in § 4. In the study of the Erdős–Rényi graph $G_{n,p}$, one is usually concerned with the asymptotic behaviour of $G_{n,p}$ as the number of vertices $n$ tends to infinity, where $p$ is typically regarded as a function of $n$. For a graph property $\mathcal {P}$, we say that $G_{n,p}$ satisfies $\mathcal {P}$ asymptotically almost surely (a.a.s.) if $\lim _{n\to \infty }\mathbb {P}(G_{n,p}\text { satisfies }\mathcal {P})=1$. We also use the Bachmann–Landau big-$O$/little-$o$ notation with respect to the number of vertices $n$ tending to infinity. Additionally, for non-negative functions $f(n)$ and $g(n)$, $f(n)\ll g(n)$ means that $f(n)=o(g(n))$. One of the most classical themes is searching the threshold probability $p(n)$ for various graph properties $\mathcal {P}$. Here, we call the probability $p(n)$ a threshold for $\mathcal {P}$ if $p\ll p(n)$ implies that $G_{n,p}$ satisfies $\mathcal {P}$ a.a.s. and $p\gg p(n)$ implies that $G_{n,p}$ does not satisfy $\mathcal {P}$ a.a.s. For example, $p(n)=n^{-1}$ is the threshold probability for the appearance of a cycle in $G_{n,p}$.

The first result exhibits a phase transition for the diagonality of Erdős–Rényi graphs. This is where the magnitude homology of Erdős–Rényi graph suddenly becomes non-diagonal.

Theorem 1.7 Let $G_{n,p}$ be an Erdős–Rényi graph with parameters $n$ and $p$. Then, the following $(1)$, $(2)$ and $(3)$ hold.

1. (1) If $p\ll n^{-1}$, then $G_{n,p}$ is diagonal a.a.s.

2. (2) If $p=cn^{-1}$, then

   \begin{align*} & \lim_{n\to\infty}\!\mathbb{P}(G_{n,p}\!\text{ is non-diagonal})\\& \quad =\begin{cases} 1-\sqrt{1-c}\exp(c/2+c^2/4+c^3/6+c^4/8), & \hspace{-.08in}c<1,\\ 1, & \hspace{-.08in}c>1. \end{cases} \end{align*}

3. (3) If $n^{-1}\ll p\ll n^{-3/4}$, then $G_{n,p}$ is non-diagonal a.a.s.

As seen in figure 1, the probability that $G_{n,c/n}$ is non-diagonal approaches an explicit constant bounded away from one whenever $c<1$. Meanwhile, when $c>1$, $G_{n,c/n}$ is non-diagonal a.a.s.

FIG. 1. Limiting function of $c$ appearing in theorem 1.7 (2).

Now, a natural question is whether $G_{n,p}$ is non-diagonal a.a.s. above the order $p = n^{-3/4}$. In the theory of random graphs, it is frequently asked whether a graph property is monotone since the monotonicity guarantees the existence of its probability threshold in Erdős–Rényi graphs [3]. Here, a graph property $\mathcal {P}$ is said to be monotone increasing if whenever a graph $G$ satisfies $\mathcal {P}$ and $G$ is a subgraph of a graph $G'$ then $G'$ also satisfies $\mathcal {P}$. However, since the non-diagonality is not a monotone property, the above question is not straightforward. The following theorem partially answers this question.

Theorem 1.8 Let $\varepsilon >0$ be fixed, and let $G_{n,p}$ be an Erdős–Rényi graph with parameters $n$ and $p$. If $p\ge \left (({(3+\varepsilon )\log n})/n\right )^{1/3}$, then $G_{n,p}$ is diagonal a.a.s.

The study of $\mathbb {P}(G_{n,p}\!\text { is non-diagonal})$ in the regime of $p$ not covered by theorems 1.7 and 1.8 will be our future work. At this moment, even the existence of the threshold where $G_{n,p}$ again becomes diagonal is still unknown.

Finally, we show the asymptotic behaviour of each rank of the magnitude homology around the threshold probability. The following result can be regarded as a weak law of large numbers for the rank of the magnitude homology.

Theorem 1.9 Let $k,\ell \in \mathbb {N}$ and $p=cn^{-1}$ for some fixed $c>0$. Let $G_{n,p}$ be an Erdős–Rényi graph with parameters $n$ and $p$. Then,

\[ \lim_{n\to\infty}\frac{\mathbb{E}[\operatorname{rk}(\operatorname{MH}_{k,\ell}(G_{n,p}))]}n=c\delta_{k,\ell}, \]

where $\delta _{k,\ell }$ is the Kronecker delta function. Moreover, for any $\varepsilon >0$,

\[ \lim_{n\to\infty}\mathbb{P}\left(\left|\frac{\operatorname{rk}(\operatorname{MH}_{k,\ell}(G_{n,p}))}n-c\delta_{k,\ell}\right|>\varepsilon\right)=0. \]

Remark 1.10 Theorem 1.9 immediately implies $\lim _{n\to \infty }\mathbb {E}[\operatorname {rk}(\operatorname {MH}_{k,\ell }^x(G_{n,c/n}))]=c\delta _{k,\ell }$ for any vertex $x$ in $G_{n,p}$. Note that the value $c$ appearing here coincides with the limit of the expected degree of $x$ in $G_{n,c/n}$. This means that $\mathbb {E}[\operatorname {rk}(\operatorname {MH}_{k,\ell }^x(G_{n,p}))]$ and $\mathbb {E}[(\deg x)\delta _{k,\ell }]$ are asymptotically equal. On the other hand, it is shown in [9] that $\operatorname {rk}(\operatorname {MH}_{k,\ell }^x(T))=(\deg x)\delta _{k, \ell }$ for any tree $T$ and its vertex $x$. Therefore, $\mathbb {E}[\operatorname {rk}(\operatorname {MH}_{k,\ell }^x(G_{n,p}))]$ and $\operatorname {rk}(\operatorname {MH}_{k,\ell }^x(T))$ depend only on the degree of $x$ asymptotically. This property is compatible with the fact that $G_{n,c/n}$ has locally tree-like structure.

The magnitude $\#G(q)$ of a graph $G$, which takes value in the formal power series $\mathbb {Z}[\![q]\!]$, is determined by the magnitude homology of $G$ (cf. [9, theorem 2.8]):

\[ \#G(q)=\sum_{\ell=0}^\infty\left(\sum_{k=0}^\ell({-}1)^k\operatorname{rk}(\operatorname{MH}_{k,\ell}(G))\right)q^\ell. \]

For $\ell \ge 0$, define $\chi _\ell (G)$ as the coefficient of $q^\ell$ in the above equation. Then, the following corollary of theorem 1.9 immediately follows.

Corollary 1.11 Let $\ell \in \mathbb {N}$ and $p=cn^{-1}$ for some fixed $c>0$. Let $G_{n,p}$ be an Erdős–Rényi graph with parameters $n$ and $p$. Then,

\[ \lim_{n\to\infty}\frac{\mathbb{E}[\chi_\ell(G_{n,p})]}n=({-}1)^\ell c. \]

Moreover, for any $\varepsilon >0$,

\[ \lim_{n\to\infty}\mathbb{P}\left(\left|\frac{\chi_\ell(G_{n,p})}n-({-}1)^\ell c\right|>\varepsilon\right)=0. \]

This article is organized as follows. In § 2, we briefly review some basic definitions of the magnitude homology of graphs. In § 3, we study the magnitude homology of graphs and its diagonality from a viewpoint of the girth. We use the algebraic Morse theory and combinatorial arguments on graphs. Finally, in § 4, we study the magnitude homology of Erdős–Rényi graphs using theorems obtained in § 3 together with classical results on random graphs.

2. Notations for the magnitude homology of graphs

In this section, we recall some definitions of the magnitude homology of graphs.

2.1 Graph

A finite simple undirected graph without loops is a pair of a nonempty finite set $V$ and a collection $E$ of subsets in $V$ of cardinality two. We regard $V$ and $E$ as a vertex set and an edge set, respectively. Throughout this article, we call a finite simple undirected graph without loops just a graph. Below, we describe some notation and terminology for a given graph $G=(V(G),E(G))$.

Definition 2.1 We say that $x\in V(G)$ is adjacent to $y\in V(G)$ if $\{x,y\}\in E(G)$, and denote $x\sim y$. For $x\in V(G)$, the degree $\deg x$ indicates the number of vertices that are adjacent to $x$.

Definition 2.2 A tuple $(x_0,x_1,\ldots,x_k)\in V(G)^{k+1}$ is called a path between $x,y\in V(G)$ if $x_0=x$, $x_k=y$, and $x_{i-1}\sim x_i$ for all $i=1,2,\ldots,k$. Here, $k$ is called the length of the path. A graph $G$ is said to be connected if for any two vertices $x,y\in V(G)$, there exists a path between $x$ and $y$.

Definition 2.3 For vertices $x,y\in V(G)$, an extended metric ${\rm d}(x,y)$ is defined as the length of shortest path between $x$ and $y$, that is, the minimum number of edges connecting $x$ and $y$. If there exist no such paths, we set ${\rm d}(x,y)=\infty$.

Definition 2.4 Let $i \geq 3$. An $i$-cycle or cycle in a graph $G$ is a tuple $(x_{0}, \dots, x_{i})$ of vertices in $G$ satisfying (1) $\{x_{k}, x_{k+1}\} \in E(G)$ for $0 \leq k \leq i-1$, (2) $x_{0} = x_{i}$, and (3) $x_{0}, \dots, x_{i-1}$ are all distinct.

Definition 2.5 A tree is a connected graph that has no cycles, while a connected graph that has exactly one cycle is called a unicyclic graph.

2.2 Magnitude homology

In this subsection, we briefly recall the definition of the magnitude homology. The readers not familiar with this subject should refer to [9] for details. Let $G=(V(G),E(G))$ be a graph. For a tuple $(x_0,x_1,\ldots,x_k)\in V(G)^{k+1}$, we define $L(x_0,x_1,\ldots,x_k) := \sum _{i=1}^k {\rm d}(x_{i-1},x_i).$ Let $\ell \in \mathbb {Z}_{\ge 0}$ be fixed, and for any $k\in \mathbb {Z}_{\ge 0}$, we define a free $\mathbb {Z}$-module $\operatorname {MC}_{k,\ell }(G)$ generated by a set

\[ \{(x_0,x_1,\ldots,x_k)\in V(G)^{k+1}\mid x_i\neq x_{i+1} \text{ for } 0\leq i \leq k-1, L(x_0,\ldots,x_k)=\ell\}. \]

We note from the definition that $\operatorname {MC}_{k,\ell }(G)=0$ for $k>\ell$. We can decompose $\operatorname {MC}_{k,\ell }(G)$ into spatially localized versions as follows. For any $k\in \mathbb {Z}_{\ge 0}$ and $x, y \in V(G)$, we define free $\mathbb {Z}$-modules $\operatorname {MC}_{k,\ell }^x(G)$ and $\operatorname {MC}_{k,\ell }^{x, y}(G)$ generated by sets

\[ \left\{(x_0,x_1,\ldots,x_k)\in V(G)^{k+1}\left|\begin{array}{@{}l@{}} x_0=x, L(x_0,\ldots,x_k)=\ell,\\ x_i\neq x_{i+1} \text{ for } 0\leq i \leq k-1\end{array}\right.\right\} \]

and

\[ \left\{(x_0,x_1,\ldots,x_k)\in V(G)^{k+1}\left| \begin{array}{@{}l@{}} x_0=x , x_k = y, L(x_0,\ldots,x_k)=\ell,\\ x_i\neq x_{i+1} \text{ for } 0\leq i \leq k-1 \end{array}\right.\right\}, \]

respectively. Then we have the following obvious decompositions by the start points and the end points of tuples:

(2.1)\begin{equation} \operatorname{MC}_{k,\ell}(G) \cong \bigoplus_{x\in V(G)}\operatorname{MC}_{k,\ell}^x(G) \cong \bigoplus_{x, y\in V(G)}\operatorname{MC}_{k,\ell}^{x, y}(G). \end{equation}

Definition 2.6 Given $(x_0,\ldots,x_i,\ldots,x_k)\in \operatorname {MC}_{k,\ell }(G)$, we say that $x_i$ is a smooth point of $(x_0,\ldots,x_i,\ldots,x_k)$ if $L(x_0,\ldots,x_k)=L(x_0,\ldots,\hat x_i,\ldots,x_k)$, that is, ${\rm d}(x_{i-1},x_{i+1})={\rm d}(x_{i-1},x_i)+{\rm d}(x_i,x_{i+1}).$ Here, the hat symbol over $x_i$ indicates that this vertex is deleted from $(x_0,\ldots,x_i,\ldots,x_k)$. We say that $x_i$ is a singular point of $(x_0,\ldots,x_i,\ldots,x_k)$ if it is not a smooth point of $(x_0,\ldots,x_i,\ldots,x_k)$.

For $k\ge 1$, the boundary map $\partial _{k,\ell }(G)\colon \operatorname {MC}_{k,\ell }(G)\to \operatorname {MC}_{k-1,\ell }(G)$ is defined as the linear extension of

\[ \partial_{k,\ell}(G)(x_0,\ldots,x_k)=\sum_{i=1}^{k-1}({-}1)^i1_{\{x_i\text{ is smooth}\}}(x_0,\ldots,\hat x_i,\ldots,x_k) \]

for $(x_0,\ldots,x_k)\in \operatorname {MC}_{k,\ell }(G)$ (see [9, definition 2.2]). By convention, we also define $\operatorname {MC}_{-1,l}(G)=0$ and $\partial _{0,l}(G)=0$. Then, it holds that $\partial _{k,\ell }(G)\circ \partial _{k+1,\ell }(G)=0$ for $k\ge 0$, that is, $\ker \partial _{k,\ell }(G)\supset \operatorname {Im}\partial _{k+1,\ell }(G)$ (see [9, lemma 2.11]). The magnitude homology group $\operatorname {MH}_{k,\ell }(G)$ of length $\ell$ is defined by $\operatorname {MH}_{k,\ell }(G) := \ker \partial _{k,\ell }(G)/\operatorname {Im}\partial _{k+1,\ell }(G)$.

Obviously, the boundary maps are compatible with the decompositions (2.1). Hence it induces the decompositions

(2.2)\begin{equation} \operatorname{MH}_{k,\ell}(G) \cong \bigoplus_{x\in V(G)}\operatorname{MH}_{k,\ell}^x(G) \cong \bigoplus_{x, y\in V(G)}\operatorname{MH}_{k,\ell}^{x, y}(G). \end{equation}

Note that, if $x$ and $y$ are adjacent, we have a tuple $(x, y, x, \dots )$ which is a homology cycle in $\operatorname {MH}_{\ell,\ell }^{x}(G)$. Hence we have $\operatorname {rk} (\operatorname {MH}_{\ell, \ell }^{x}(G)) \geq \deg x$. In particular, $\operatorname {rk} (\operatorname {MH}_{\ell, \ell }(G)) \geq 2\# E(G)$ holds from equation (2.2).

Example 2.7 [9, corollary 6.8]

Let $T$ be a tree, and $x\in V(T)$ be fixed. Then we have

\[ \operatorname{MH}_{k,\ell}^x(T)\simeq\begin{cases} \mathbb{Z}, & k=\ell=0,\\ \mathbb{Z}^{\deg x}, & k=\ell\ge1,\\ 0, & k\neq\ell. \end{cases} \]

This is verified by using Mayer–Vietoris theorem in [9, theorem 6.6] after checking that it is compatible with the decompositions (2.2). Moreover, equation (2.2) yields

\[ \operatorname{MH}_{k,\ell}(T)\simeq\begin{cases} \mathbb{Z}^{\#V(T)}, & k=\ell=0,\\ \mathbb{Z}^{2\#E(T)}, & k=\ell\ge1,\\ 0, & k\neq\ell. \end{cases} \]

Definition 2.8 [9, definition 7.1]

A graph $G$ is called diagonal if $\operatorname {MH}_{k, \ell }(G) = 0$ for $k\neq \ell$.

Definition 2.9 [8, definition 4.2]

A graph of diameter at most two is called pawful if any distinct vertices $x,y,z\in V(G)$ with ${\rm d}(x,y)={\rm d}(y,z)=2$ and ${\rm d}(z,x)=1$ have a common neighbour. Here, for $S\subset V(G)$, a vertex $w\in V(G)$ is said to be a common neighbour of $S$ if $w$ is adjacent to all the vertices in $S$.

Example 2.10 Trees are diagonal, as seen in example 2.7. Join graphs, in particular complete graphs, are also diagonal [9, theorem 7.5]. Moreover, pawful graphs are diagonal [8, theorem 4.4].

3. Girth and the magnitude homology of graphs

In this section, we study the magnitude homology of graphs by a method of algebraic topology. First in § 3.1, we briefly review the algebraic Morse theory, which is a crucial tool for the later parts. In § 3.2 and 3.3, we compute the $(\ell - i, \ell )$-part $\operatorname {MH}_{\ell - i, \ell }(G)$ of the magnitude homology for a general graph $G$ and for some $0 \leq i \leq \ell -1$. In § 3.4, we give a criterion for graphs to be diagonal. All the main results proved in this section, especially theorems 1.3 and 1.5, will be key lemmas for the probabilistic study of the magnitude homology in § 4.

3.1 Algebraic Morse theory

For our computation, we use the algebraic Morse theory studied in [15]. The matching that we construct in § 3.2 and3.3 is quite similar to that of Gu's [8]. While he constructs matchings for several specific graphs in [8], we improve them to make it applicable to general graphs. In this subsection, we briefly review the algebraic Morse theory. It is almost the same instruction as in [8], and see [15] for the details.

Let $C_{\ast } = (C_{\ast }, \partial _{\ast })$ be a chain complex of finite rank-free $\mathbb {Z}$-modules. We choose a basis $I_k$ of $C_k$, and we set $C_{k} = \bigoplus _{\alpha \in I_{k}} C_{k, \alpha } \cong \bigoplus _{\alpha \in I_{k}}\mathbb {Z}$ for each $k \geq 0$. We denote differentials restricted to each component as $f_{\beta \alpha }\colon C_{k+1, \alpha } \hookrightarrow C_{k+1} \xrightarrow {\partial _{k+1}} C_{k} \twoheadrightarrow C_{k, \beta }$.

Let $\Gamma _{C_{\ast }}$ be a directed graph whose vertex set is $\coprod _{k} I_{k}$, and directed edges are $\{\alpha \to \beta \mid f_{\beta \alpha } \neq 0\}$. Recall that a matching of a directed graph is a subset $M$ of the edge set such that any two distinct edges in $M$ have no common vertices. For a matching $M$ of $\Gamma _{C_{\ast }}$, we define a new directed graph $\Gamma _{C_{\ast }}^{M}$ by inverting the direction of all edges in $M$.

Definition 3.1 The matching $M$ is called Morse matching if the directed graph $\Gamma _{C_{\ast }}^{M}$ is acyclic, and all the homomorphisms of the form $f_{\beta \alpha }\colon C_{k+1, \alpha } \hookrightarrow C_{k+1} \xrightarrow {\partial _{k+1}} C_{k} \twoheadrightarrow C_{k, \beta }$ corresponding to the edges in $M$ are isomorphisms.

Here we remark that $\Gamma _{C_{\ast }}^{M}$ is acyclic if and only if there are no closed paths in $\Gamma _{C_{\ast }}^{M}$ of the form $a_{1} \longrightarrow b_{1} \longrightarrow \cdots \longrightarrow b_{p-1} \longrightarrow a_{p}=a_1$ with $a_{i} \in C_{k+1}$ and $b_{i}\in C_{k}$ for some $k$.

Theorem 3.2 [15]

For a Morse matching $M$, the chain complex $C_{\ast }$ is homotopy equivalent to the chain complex $\mathring C_{\ast }$ defined as follows$:$ let $\mathring {I}_{k}$ be the set of vertices in $I_{k}$ unmatched by $M$. We define $\mathring {C}_{k} = \bigoplus _{\alpha \in \mathring {I}_{k}} C_{k, \alpha }$ for each $k \geq 0$. For each $\alpha \in \mathring {I}_{k}$ and $\beta \in \mathring {I}_{k-1}$, let $\Gamma _{\alpha, \beta }^{M}$ be the set of paths in $\Gamma _{C_{\ast }}^{M}$ connecting $\alpha$ and $\beta$ in this order. For $\gamma \in \Gamma _{\alpha, \beta }^{M}$, we define $\mathring {\partial }_{\gamma }\colon C_{k, \alpha } \to C_{k-1, \beta }$ as $\mathring {\partial }_{\gamma } = (-1)^{i/2}f_{\beta v_{i}}\circ f_{v_{i-1} v_{i}}^{-1} \circ \dots \circ f_{v_3 v_2}\circ f_{v_{1} v_{2}}^{-1}\circ f_{v_{1}\alpha },$ where $\gamma = (\alpha \to v_{1} \to \dots \to v_{i} \to \beta )$. Then the differential $\mathring {\partial }_{k}$ restricted on $C_{k, \alpha }$ for $\alpha \in \mathring {I}_{k}$ is defined as

\[ \mathring{\partial}_{k}|_{C_{k, \alpha}} = \sum_{\beta \in \mathring{I}_{k-1}, \gamma \in \Gamma_{\alpha, \beta}^{M}} \mathring{\partial}_{\gamma}. \]

In particular, we have $\mathring {\partial }_{k} = 0$ if the original differential $\partial _{k}$ vanishes on $\mathring {C}_{k}$.

3.2 Computation for diagonal part

In this subsection, we study the diagonal part ($(\ell, \ell )$-part) of the magnitude homology. In the following, we assume that $\ell \geq 1$ unless otherwise noted. We first recall the definition of the local girth of a graph at a fixed vertex, as seen in the Introduction.

Definition 3.3 Let $G$ be a graph and $x \in V(G)$ be a vertex. We define the local girth of $G$ at $x$ by $\operatorname {gir}_x(G) := \inf \{i\ge 3\mid\ \text{there exists an}\ \text{i-cycle in}\ G\ \text{containing}\ x\}.$ We also define the girth of $G$ by $\operatorname {gir}(G) := \min _{x} \operatorname {gir}_{x}(G)$.

Our aim in this subsection is to prove theorem 1.1. We use the algebraic Morse theory for the proof. Let us consider a truncated chain complex

\[ 0 \longrightarrow \operatorname{MC}^{x}_{\ell, \ell}(G) \longrightarrow \operatorname{MC}^{x}_{\ell -1, \ell}(G) \longrightarrow 0 \]

and denote it by $C_{\ast }$. It is easy to see that the first homology of $C_{\ast }$ is isomorphic to $\operatorname {MH}^{x}_{\ell, \ell }(G)$. In the following, we give a Morse matching on $\Gamma _{C_{\ast }}$ for graphs that have neither $3$- nor $4$-cycles containing $x$ as their vertex.

Lemma 3.4 Let $\ell \geq 1$ and $i \geq 1$. Let $G$ be a graph with $\operatorname {gir}_{x}(G)\geq 4$ for a vertex $x \in V(G)$. Let $(x = x_{0}, \dots, x_{\ell }) \in \operatorname {MC}^{x}_{\ell, \ell }(G)$ be a chain, and suppose that $x_{j}$ is its singular point for $0 \leq j \leq i-1$. Then $x_{j} \in \{x_{0}, x_{1}\}$ for $0 \leq j \leq i$.

Proof. We prove by induction on $i$. For $i = 1$, the statement is trivially true. Suppose that $x_{j}$ is singular for $0 \leq j \leq i-1$. Then it follows that $x_{j} \in \{x_{0}, x_{1}\}$ for $0 \leq j \leq i-1$ from the inductive assumption. Now we have $\{ x_{i-2}, x_{i-1}\} = \{x_{0}, x_{1}\}$ because $x_{i-2} \neq x_{i-1}$. Note here that we have ${\rm d}(x_{k}, x_{k+1}) =1$ for $0 \leq k \leq \ell -1$ by the definition of $\operatorname {MC}_{\ell, \ell }(G)$. Then by the assumption that $x_{i-1}$ is a singular point, we have ${\rm d}(x_{i-2}, x_{i}) \leq 1$. If we have ${\rm d}(x_{i-2}, x_{i}) = 1$, then these three points $x_{i-2}, x_{i-1}, x_{i}$ form a $3$-cycle containing $x$ because $x_{i-2}$ or $x_{i-1}$ coincides with $x$, which is not the case [see figure 2(a)]. Hence we obtain that ${\rm d}(x_{i-2}, x_{i}) = 0$, which implies that $x_{i} = x_{i-2} \in \{ x_{0}, x_{1}\}$.

FIG. 2. (a) Illustration of a $3$-cycle containing $x$ in the case that ${\rm d}(x_{i-2},x_i) = 1$. (b) Illustration of a $4$-cycle containing $x$. (c) Illustration of a $3$- or $4$-cycle containing $x$ in the case that $x_{i-1}\neq x_{i+1}$. A $3$-cycle appears when $x_i$ and $y_i$ are adjacent, otherwise a $4$-cycle appears.

Let $T_{\ell }$ be a subset of generators in $\operatorname {MC}^{x}_{\ell, \ell }(G)$ defined as

\[ T_{\ell} = \left\{ (x_{0}, \dots, x_{\ell}) \in \operatorname{MC}^{x}_{\ell, \ell}(G) \mid\text{$x_{i}$ is smooth for some $0\leq i \leq \ell$}\right\}. \]

Whenever $T_\ell \neq \emptyset$, we define a map $f_{\ell }\colon T_{\ell } \longrightarrow \operatorname {MC}^{x}_{\ell -1, \ell }(G)$ by deleting the first smooth point, that is, $f_{\ell }(x_{0}, \dots, x_{\ell }) = (x_{0}, \dots, \hat {x}_{i}, \dots, x_{\ell }),$ where $x_{j}$ is a singular point of $(x_{0}, \dots, x_{\ell })$ for $0 \leq j \leq i-1$, and $x_{i}$ is its smooth point.

Lemma 3.5 If $\operatorname {gir}_{x}(G) \geq 5$, the above map $f_{\ell }$ is injective.

Proof. Suppose that

\[ f_{\ell}(x_{0}, \dots, x_{\ell}) = (x_{0}, \dots, \hat{x}_{i}, \dots, x_{\ell}) = (y_{0}, \dots, \hat{y}_{j}, \dots, y_{\ell}) = f_{\ell}(y_{0}, \dots, y_{\ell}). \]

Then we have ${\rm d}(x_{i-1}, x_{i+1}) = 2$ and ${\rm d}(y_{j-1}, y_{j+1}) = 2$. Because the other pairs of adjacent points are apart from each other by distance $1$, we obtain $i = j$, which implies that $x_k = y_k$ for $0 \leq k \leq i-1$ and $i+1 \leq k \leq \ell$. If $i = j \geq 2$, then we have $x_{k}, y_{k} \in \{x_{0}, x_{1}\} = \{y_{0}, y_{1}\}$ for $0 \leq k \leq i = j$ by lemma 3.4. Then we obtain $x_{i} = y_{i}$ from $x_{i -1} = y_{i-1}$, indicating that $(x_{0}, \dots, x_{\ell }) =(y_{0}, \dots, y_{\ell })$. Suppose that $i = j = 1$ and $x_{1} \neq y_{1}$. Then we have $x_{0} = y_{0}$, $x_{2} = y_{2}$, ${\rm d}(x_{0}, x_{2}) = 2$, and ${\rm d}(x_{0}, x_{1}) = {\rm d}(x_{1}, x_{2}) = {\rm d}(x_{0}, y_{1}) = {\rm d}(y_{1}, x_{2}) = 1$ [see figure 2(b)]. Hence these four points form a $4$-cycle containing $x$, which is not the case. Thus we obtain $x_{1} = y_{1}$, indicating that $(x_{0}, \dots, x_{\ell }) =(y_{0}, \dots, y_{\ell })$.

By lemma 3.5, we can define a matching $M_{f_{\ell }} = \{\alpha \to \beta \mid f_{\ell } (\alpha ) = \beta \}$ on $\Gamma _{C_{\ast }}$ by the injective map $f_{\ell }$. When $T_{\ell }$ is empty, we define the empty matching.

Lemma 3.6 If $\operatorname {gir}_{x}(G) \geq 5$, then the above matching $M_{f_{\ell }}$ is a Morse matching.

Proof. Let $(x_{0}, \ldots, \hat {x}_{i}, \ldots, x_{\ell }) \in \operatorname {MC}^{x}_{\ell -1, \ell }(G),$ where $x_{i}$ is a smooth point of the tuple $(x_{0},\ldots, x_{\ell })\in \operatorname {MC}^{x}_{\ell, \ell }(G),$ but not the first one. Note that $i \geq 2$. We show that the tuple $(x_{0}, \ldots, \hat {x}_{i}, \ldots, x_{\ell })$ is not in the image of $f_\ell$. This implies that there is no directed path of length $\geq \! 3$ in $\Gamma ^{M_{f_\ell }}_{C_{\ast }}$, indicating that $\Gamma ^{M_{f_\ell }}_{C_{\ast }}$ is acyclic. Suppose that $f_{\ell }(y_{0}, \ldots, y_{\ell }) = (x_{0}, \ldots, \hat {x}_{i}, \ldots, x_{\ell })$, and let $y_{j}$ be the first smooth point of the tuple $(y_{0}, \dots, y_{\ell })$. Then we have $(y_{0}, \ldots, \hat {y}_{j}, \ldots, y_{\ell }) = (x_{0}, \ldots, \hat {x}_{i}, \ldots, x_{\ell }),$ hence we have $i = j$ by the same argument in the proof of lemma 3.5. Then, $x_k = y_k$ for $0 \leq k \leq i-1$ and $i+1 \leq k \leq \ell$, and also $x_{i} \neq y_{j}$. Because $y_{j}$ is the first smooth point, we have $\{y_{0}, \dots, y_{j}\} = \{y_{0}, y_{1}\}$ by lemma 3.4. Furthermore, since $x_{k} = y_{k}$ for $0 \leq k \leq i-1$, we obtain that $y_{i} = y_{i-2} = x_{i-2}$. Because $y_{i}$ is adjacent to $y_{i+1} = x_{i+1}$, we have ${\rm d}(x_{i-2}, x_{i+1}) = {\rm d}(x_{i+1}, x_{i}) = {\rm d}(x_{i}, x_{i-1}) = {\rm d}(x_{i-1}, x_{i-2}) = 1$ [see figure 2(c)]. Then there is a $3$- or $4$-cycle containing the edge $\{y_{i-2}, y_{i-1}\} = \{y_{0}, y_{1}\} = \{x_{0}, x_{1}\}$ unless we have $x_{i-1} = x_{i+1}$. The former case contradicts that $\operatorname {gir}_x(G)\ge 5$. The latter case contradicts the fact that $x_{i}$ is a smooth point of $(x_0,\ldots,x_\ell )\in \operatorname {MC}^x_{\ell,\ell }(G)$.

Proof of theorem 1.1. Proof of theorem 1.1

By theorem 3.2 and lemma 3.6, the chain complex $C_{\ast }$ is homotopy equivalent to the chain complex generated by the unmatched generators of the Morse matching $M_{f_\ell }$. The unmatched generators in $\operatorname {MC}^{x}_{\ell, \ell }(G)$ are exactly the tuples that have only singular points, and by lemma 3.4, they are of the form $(x, y, x, y, \ldots )$, where $y$ is adjacent to $x$. Because the differential of $\operatorname {MC}^{x}_{\ast, \ell }(G)$ vanishes on these generators, $\operatorname {MH}^{x}_{\ell, \ell }(G)$ is isomorphic to a free module generated by the tuples of the form $(x,y,x,y,\ldots )$. This completes the proof.

3.3 Computation for non-diagonal part

We extend our matching constructed above to a larger part of the magnitude chain complex. For a tuple $(x_{0}, \ldots, x_{n}) \in V(G)^{n+1}$, we call $(x_{g}, x_{g+1})$ a gap if ${\rm d}(x_{g}, x_{g+1}) \geq 2$, and we call it the first gap if additionally ${\rm d}(x_{j}, x_{j+1}) = 1$ for $0\leq j \leq g-1$. For $0\leq i \leq \ell -1$, let $T_{\ell - i}$ be a subset of $\operatorname {MC}^{x}_{\ell -i, \ell }(G)$ defined as

\[ T_{\ell-i} := \left\{(x_0,\ldots,x_{\ell-i})\in \operatorname{MC}^x_{\ell-i,\ell}(G)\left|\begin{array}{@{}l@{}} x_j\text{ is smooth for some }1\le j\le g-1,\\ \text{where}\ (x_g,x_{g+1})\ \text{is the first gap} \end{array}\right.\right\}. \]

Note that the subset $T_{\ell }$ defined here coincides with the one defined in the previous subsection. We simply say that $x_{j}$ is the first smooth point before the first gap of $(x_{0}, \dots, x_{\ell -i})$ if $x_{j}$ with $1\leq j \leq g-1$ is a smooth point and $x_k$'s are singular points for $0 \leq k \leq j-1$, where $(x_g, x_{g+1})$ is the first gap. Note that it means just the first smooth point for the case $i = 0$. Whenever $T_{\ell -i}\neq \emptyset$, we define a map $f_{\ell - i}\colon T_{\ell - i} \longrightarrow \operatorname {MC}^{x}_{\ell -i-1, \ell }(G)$ by deleting the first smooth point before the first gap, that is, $f_{\ell -i}(x_{0}, \ldots, x_{\ell - i}) = (x_{0}, \ldots, \hat {x}_{j}, \ldots, x_{\ell - i}),$ where $x_{j}$ is the first smooth point of $(x_{0}, \ldots, x_{\ell -i})$ before the first gap. Note that our definitions of $T_{\ell - i}$'s and $f_{\ell - i}$'s contain those of $f_{\ell }$ and $T_{\ell }$ defined in the previous subsection, respectively, by considering $i=0$. The image of the map $f_{\ell -i}$ is disjoint from the subset $T_{\ell - i -1}$ for $0 \leq i \leq \ell - 1$ since the deletion of a point by $f_{\ell -i}$ makes a new first gap before which there exists no smooth points.

Lemma 3.7 If $\operatorname {gir}_{x}(G) \geq 5$, then $f_{\ell - i}$ is injective for $0 \leq i \leq \ell -1$.

Proof. As shown in lemma 3.5, $f_\ell$ is injective. Hence, we assume that $i\ge 1$. Suppose that $f_{\ell -i}(x_{0}, \ldots, x_{\ell - i}) = f_{\ell - i}(y_{0}, \ldots, y_{\ell - i})$. By the same argument in the proof of lemma 3.5, the positions of the first smooth point and the first gap of the both tuples are same. By looking at the parts before the first gap, the statement follows from the same argument in the proof of lemma 3.5.

By lemma 3.7, we can define a matching $M_{f_{\ast }}$ of $\Gamma _{\operatorname {MC}^{x}_{\ast, \ell }(G)}$ by the injective maps $f_*=(f_{\ell - i})_{0 \leq i \leq \ell - 1}$. In the following, we assume $i$ to be in the range $0 \leq i \leq \ell - 1$ unless otherwise mentioned.

Lemma 3.8 If $\operatorname {gir}_{x}(G) \geq 5$, then the above matching $M_{f_{\ast }}$ is a Morse matching.

Proof. Let $(x_{0}, \ldots, \hat {x}_{j}, \ldots, x_{\ell - i}) \in \operatorname {MC}^{x}_{\ell -i -1, \ell }(G),$ where $x_{j}$ is a smooth point of the tuple $(x_{0},\ldots, x_{\ell - i})\in \operatorname {MC}^{x}_{\ell - i, \ell }(G),$ but not the first smooth point before the first gap. The case for $i = 0$ has been already considered in lemma 3.6, hence we assume $i \geq 1$. Let $(x_{g}, x_{g+1})$ be the first gap of the tuple $(x_{0},\ldots, x_{\ell - i})$. If $j = g$ or $g + 1$, then $(x_{0}, \ldots, \hat x_{j}, \ldots, x_{\ell - i})$ is not in the image of $f_{\ell - i}$. It is because the first gap $(x_{g-1}, x_{g+1})$ or $(x_{g}, x_{g+2})$ of $(x_{0}, \ldots, \hat x_{j}, \ldots, x_{\ell - i})$ must satisfy that ${\rm d}(x_{g-1}, x_{g+1}) \geq 3$ or ${\rm d}(x_{g}, x_{g+2}) \geq 3$ respectively, while the first gap of an image of $f_{\ell -i}$ must have distance 2. For the case that $j \leq g-1$, we can show that the tuple $(x_{0}, \ldots, \hat x_{j}, \ldots, x_{\ell - i})$ is not in the image of $f_{\ell - i}$ by the same argument in the proof of lemma 3.6. Hence the remained case is that $j \geq g+2$. In this case, if we have $(x_{0}, \ldots, \hat {x}_{j}, \ldots, x_{\ell - i}) = f_{\ell - i}(y_{0}, \ldots, y_{\ell - i}),$ then the tuple $(y_{0}, \ldots, y_{\ell - i})$ must be of the form $(x_{0}, \ldots, x_{g}, y_{\rm new}, x_{g+1}, \ldots, x_{j-1}, x_{j+1}, \ldots, x_{\ell - i})$ with ${\rm d}(x_{g}, x_{g+1}) = 2$. Here, $y_{\rm new}$ is the first smooth point before the first gap by the definition of $f_{\ell -i}$. Then the first gap $(y_{g'}, y_{g' + 1})$ of $(y_{0}, \ldots, y_{\ell - i})$ satisfies $g' \geq g+1$. Hence there cannot be a cycle of the form $a_{1} \longrightarrow b_{1} \longrightarrow \cdots \longrightarrow a_{p} \longrightarrow b_{p} \longrightarrow a_{1}$ in $\Gamma ^{M_{f_{\ast }}}_{\operatorname {MC}^{x}_{\ast, \ell }(G)}$ with $a_{k} \in \operatorname {MC}^{x}_{\ell - i, \ell }(G)$, $b_{k} \in \operatorname {MC}^{x}_{\ell - i - 1, \ell }(G)$ because the position of the first gap of $a_{k}$ moves backward. This completes the proof.

By lemma 3.8, we obtain a chain complex $(\mathring {\operatorname {MC}}^{x}_{\ast, \ell }(G), \mathring \partial _{\ast,\ell })$ consisting of the unmatched generators by the Morse matching $M_{f_*}$, which is homotopy equivalent to the original magnitude chain complex $(\operatorname {MC}^{x}_{\ast, \ell }(G), \partial _{\ast,\ell })$ by theorem 3.2. The following lemma characterizes the generators of $(\mathring {\operatorname {MC}}^{x}_{\ast, \ell }(G), \mathring \partial _{\ast,\ell })$.

Lemma 3.9 Let $\operatorname {gir}_{x}(G) \geq 5$. A tuple $(x_{0}, \ldots, x_{\ell - i}) \in \operatorname {MC}^{x}_{\ell - i, \ell }(G)$ is unmatched by the matching $M_{f_{\ast }}$ if and only if it satisfies one of the following conditions$:$

1. (i) It has no gaps and no smooth points.

2. (ii) It has the first gap $(x_{g}, x_{g+1})$ with $g \geq 1$ and ${\rm d}(x_{g}, x_{g+1}) \geq 3$ such that there is no smooth point before the first gap.

3. (iii) It has the first gap $(x_{g}, x_{g+1})$ with $g \geq 1$ and ${\rm d}(x_{g}, x_{g+1}) = 2$ such that there is no smooth point before the first gap. Furthermore, every vertex $z$ adjacent to both of $x_{g}$ and $x_{g+1}$ is the second smooth point of $(x_{0}, \ldots, x_{g}, z, x_{g+1}, \ldots, x_{\ell - i})$.

4. (iv) It has the first gap $(x_{0}, x_{1})$ with ${\rm d}(x_{0}, x_{1}) \geq 3$.

Proof. Let $(x_{0}, \ldots, x_{\ell - i}) \in \operatorname {MC}^{x}_{\ell - i, \ell }(G)$ satisfy none of the above conditions. We will show that $(x_{0}, \ldots, x_{\ell - i})$ is matched. If there is a smooth point before the first gap, then it is in $T_{\ell -i}$, hence it is matched. Hence we can suppose that $(x_{0}, \ldots, x_{\ell - i})$ has the first gap $(x_{g}, x_{g+1})$ with $g \geq 0$ and ${\rm d}(x_{g}, x_{g+1}) = 2$ such that there is no smooth point before the first gap, and furthermore, there is a vertex $z$ adjacent to $x_{g}$ and $x_{g+1}$ such that $z$ is the first smooth point before the first gap of $(x_{0}, \ldots, x_{g}, z, x_{g+1}, \ldots, x_{\ell - i})$. Then we have $f_{\ell - i+1}(x_{0}, \ldots, x_{g}, z, x_{g+1}, \ldots, x_{\ell - i}) = (x_{0}, \ldots, x_{\ell - i}),$ hence it is matched. Therefore the above conditions are necessary to be unmatched.

We show the sufficiency as follows. When a tuple satisfies (i), then it is in $\operatorname {MC}^{x}_{\ell, \ell }(G)$ and not in $T_\ell$, hence it is neither in the image nor domain of any $f_\ast$. When a tuple satisfies (ii), it is not in $T_{\ell - i}$. Furthermore, if it is in the image of $f_{\ell - i + 1}$, then its first gap $(x_g, x_{g+1})$ is obtained by omitting the first smooth point of a tuple in $T_{\ell - i+1}$, which implies that ${\rm d}(x_g, x_{g+1}) = 2$. This is a contradiction. When a tuple satisfies (iii), it is not in $T_{\ell - i}$. Furthermore, if it is in the image of $f_{\ell - i + 1}$, then it must be expressed as $f_{\ell - i + 1}(x_{0}, \ldots, x_{g}, z, x_{g+1}, \ldots, x_{\ell - i})$, where $z$ is a vertex adjacent to both $x_g$ and $x_{g+1}$. However, $z$ is not the first smooth point of the tuple $(x_{0}, \ldots, x_{g}, z, x_{g+1}, \ldots, x_{\ell - i})$, hence $f_{\ell - i + 1}(x_{0}, \ldots, x_{g}, z, x_{g+1}, \ldots, x_{\ell - i}) \neq (x_{0}, \ldots, x_{g}, x_{g+1}, \ldots, x_{\ell - i})$. This is a contradiction. When a tuple satisfies (iv), it is not in $T_{\ell - i}$. Furthermore, if it is in the image of $f_{\ell - i + 1}$, then its first gap $(x_0, x_{1})$ is obtained by omitting the first smooth point of a tuple in $T_{\ell - i+1}$, which implies that ${\rm d}(x_0, x_{1}) = 2$. This is a contradiction. This completes the proof.

Now we look at the differential $\mathring {\partial }_{\ast,\ell }$ on $\mathring {\operatorname {MC}}^{x}_{\ast, \ell }(G)$.

Lemma 3.10 Let $\operatorname {gir}_{x}(G) \geq 5$. Let $\alpha$ be a tuple satisfying one of the conditions in lemma 3.9. Then there are no paths of length $\geq 2$ in $\Gamma ^{M_{f_{\ast }}}_{\operatorname {MC}^{x}_{\ast, \ell }(G)}$ that start from $\alpha$.

Proof. Note that there exist no directed edges $\alpha \longrightarrow \beta$ such that $\alpha \in \operatorname {MC}^{x}_{\ell - i, \ell }(G)$, $\beta \in \operatorname {MC}^{x}_{\ell - i + 1, \ell }(G)$ by lemma 3.9. Hence, let $\alpha \longrightarrow \beta$ be a directed edge in $\Gamma ^{M_{f_{\ast }}}_{\operatorname {MC}^{x}_{\ast, \ell }(G)}$ with $\alpha \in \operatorname {MC}^{x}_{\ell - i, \ell }(G)$, $\beta \in \operatorname {MC}^{x}_{\ell - i - 1, \ell }(G)$. In order that this directed edge is extended to a path of length $2$, $\beta$ must be in the image of $f_{\ell - i}$. Note that, in order to be in the image of $f_{\ell - i}$, $\beta$ must have the first gap with distance exactly $2$. Hence $\alpha$ and $\beta$ must be of the forms $\alpha = (x_{0}, \ldots, x_{g}, x_{g+1}, \ldots,x_k,\ldots, x_{\ell -i})$ and $\beta = (x_{0}, \ldots, x_{g}, x_{g+1}, \ldots, \hat {x}_{k}, \ldots, x_{\ell - i})$, where $(x_g,x_{g+1})$ is the first gap of $\alpha$ and $\beta$ with $g\geq 0$, ${\rm d}(x_{g}, x_{g+1}) = 2$, and $g+2 \leq k \leq \ell - i - 1$. Further, $\alpha$ must satisfy (iii) of lemma 3.9 by the assumption. Hence every vertex $y$ adjacent to both of $x_{g}$ and $x_{g+1}$ is the second smooth point of the tuple $(x_{0}, \ldots, x_{g}, y, x_{g+1}, \ldots, \hat x_{k}, \ldots, x_{\ell - i}),$ which implies that $\beta$ cannot be in the image of $f_{\ell - i}$. Hence the statement follows.

We obtain the following by lemma 3.10 and theorem 3.2.

Lemma 3.11 Let $\operatorname {gir}_{x}(G) \geq 5$. The differentials on $\mathring {\operatorname {MC}}^{x}_{\ast, \ell }(G)$ are the restrictions of those on $\operatorname {MC}^{x}_{\ast, \ell }(G)$.

Now we further construct a Morse matching for $(\mathring {\operatorname {MC}}^{x}_{\ast, \ell }(G), \mathring \partial _{\ast,\ell })$. Before that, we study some properties of the unmatched tuples of the matching $M_{f_{\ast }}$ by the following three lemmas.

Lemma 3.12 Suppose that $\operatorname {gir}_{x}(G) \geq 5$. Let $(x_{0}, \ldots, x_{g}, x_{g+1}, \ldots, x_{\ell - i}) \in \mathring {\operatorname {MC}}^{x}_{\ell - i, \ell}(G),$ which satisfies the condition (ii) or (iii) in lemma 3.9 with the first gap $(x_{g}, x_{g+1})$, $g\geq 1$. If $x_{g}$ is its smooth point, then $x_{g-1}$ is a singular point of the tuple $(x_{0}, \ldots, x_{g-1}, \hat {x}_{g}, x_{g+1}, \ldots, x_{\ell - i})$.

Proof. By lemma 3.4, we have $x_{2m} = x_{2m+2}$ and $x_{2m+1} = x_{2m+3}$ for $0 \leq 2m \leq 2m+3 \leq g$. Since $x_{g}$ is a smooth point, we have that ${\rm d}(x_{g-1}, x_{g+1}) = {\rm d}(x_{g-1}, x_{g}) + {\rm d}(x_{g}, x_{g+1})$. Then we have that

\begin{align*} {\rm d}(x_{g-2} = x_{g}, x_{g-1}) + {\rm d}(x_{g-1}, x_{g+1}) & = {\rm d}(x_{g}, x_{g+1}) + 2{\rm d}(x_{g-1}, x_{g})\\ & > {\rm d}(x_{g-2}=x_{g}, x_{g+1}). \end{align*}

Hence $x_{g-1}$ is a singular point of the tuple $(x_{0}, \ldots, x_{g-2}, x_{g-1}, \hat {x}_{g}, x_{g+1}, \ldots, x_{\ell - i})$.

Lemma 3.13 Let $(x_{0}, \ldots, x_{g}, x_{g+1}, \ldots, x_{\ell - i}) \in \mathring {\operatorname {MC}}^{x}_{\ell - i, \ell }(G),$ which satisfies the condition (iii) in lemma 3.9 with the first gap $(x_{g}, x_{g+1})$. If $\operatorname {gir}_{x}(G) > 5$, then $x_{g}$ is a smooth point of $(x_0,\ldots,x_g,x_{g+1},\ldots,x_{\ell -i})$.

Proof. Note that $x \in \{x_{g-1}, x_{g}\}$ by the same argument as that in lemma 3.4. Assume that $x_{g}$ is a singular point of $(x_0,\ldots,x_g,x_{g+1},\ldots,x_{\ell -i})$. Let $z$ be a vertex adjacent to $x_{g}$ and $x_{g+1}$. Then we have ${\rm d}(x_{g-1}, z) = {\rm d}(x_{g-1}, x_{g}) + {\rm d}(x_{g}, z) = 2$ so that it satisfies (iii) of lemma 3.9. Hence we have $x_{g-1} \neq z$. Since $x_{g}$ is a singular point of $(x_0,\ldots,x_g,x_{g+1},\ldots,x_{\ell -i})$, we have ${\rm d}(x_{g-1}, x_{g+1}) < {\rm d}(x_{g-1}, x_{g}) + {\rm d}(x_{g}, x_{g+1}) = 3.$ If ${\rm d}(x_{g-1}, x_{g+1}) = 2$, then there exists a $5$-cycle containing $x$ because the point adjacent to $x_{g-1}$ and $x_{g+1}$ do not coincide with $x_{g}$ or $z$. This contradicts the assumption. If ${\rm d}(x_{g-1}, x_{g+1}) = 1$, then there exists a $4$-cycle containing $x$. Further, we have ${\rm d}(x_{g-1},x_{g+1})\neq 0$ because ${\rm d}(x_g,x_{g-1})=1$ and ${\rm d}(x_g,x_{g+1})=2$. Therefore, we conclude that $x_{g}$ can never be a singular point.

Lemma 3.14 Let $i\ge 1$. Let $(x_{0}, \ldots, x_{g}, x_{g+1}, \dots, x_{\ell - i}) \in \mathring {\operatorname {MC}}^{x}_{\ell - i, \ell }(G),$ which satisfies the condition (ii) or (iv) in lemma 3.9 with the first gap $(x_{g}, x_{g+1})$, $g\geq 0$. Suppose that $x_{g}$ is a singular point of $(x_0,\ldots,x_g,x_{g+1},\ldots,x_{\ell -i})$. If $\operatorname {gir}_{x}(G) \geq 2i + 4$, then $(x_{0}, \ldots, x_{g}, y, x_{g+1}, \ldots, x_{\ell - i}) \in \mathring {\operatorname {MC}}^{x}_{\ell - i + 1, \ell }(G),$ where $y$ is taken as $x_{g-1}$ for $g \geq 1$ and as an arbitrary vertex adjacent to $x_0$ that lies in a shortest path connecting $x_0$ and $x_1$ for $g = 0$.

Proof. Let $x_{g} = p_{0} \longrightarrow \cdots \longrightarrow p_{{\rm d}(x_{g}, x_{g+1})} = x_{g+1}$ be a shortest path connecting $x_{g}$ and $x_{g+1}$. When $g = 0$, we can take $y = p_{1}$ so that $y$ becomes a smooth point. If we have $g \geq 1$ and $p_{1} = x_{g-1}$, then we can take $y = p_{1} = x_{g-1}$ so that ${\rm d}(x_{g}, x_{g+1}) = {\rm d}(x_{g}, x_{g-1}) + {\rm d}(x_{g-1}, x_{g+1})$. Hence we suppose that $g \geq 1$ and $p_{1} \neq x_{g-1}$. Since $x_{g}$ is a singular point of $(x_0,\ldots,x_g,x_{g+1},\ldots,x_{\ell -i})$, there exist a shortest path $x_{g-1} = q_{0} \longrightarrow \cdots \longrightarrow q_{N} = x_{g+1}$ with $N < 1 + {\rm d}(x_{g}, x_{g+1})$ and $q_{1} \neq x_{g}$. Let $j$ be the minimum number such that $q_{j}$ coincides with some $p_{m}$. Then $x_{g} \longrightarrow x_{g-1} = q_{0} \longrightarrow \cdots \longrightarrow q_{j} = p_{m} \longrightarrow p_{m-1} \longrightarrow p_{0} = x_{g}$ is a cycle of length $< 2{\rm d}(x_{g}, x_{g+1}) + 2$ because $(j,m)\neq (1,0),(0,1)$. Note that we have ${\rm d}(x_{g}, x_{g+1}) \leq i+1$ because $L(x_{0}, \ldots, x_{g}, x_{g+1}, \ldots, x_{\ell - i}) = \ell$. Hence the obtained cycle has length $< 2i+4$. Since $x_{0}, \ldots, x_{g-1}$ are all singular points, we have $x_{g-1} = x_{0}$ or $x_{g} = x_{0}$ by lemma 3.4. Therefore this cycle contains $x$ as its vertex, it contradicts that $\operatorname {gir}_{x}(G) \geq 2i + 4$. Finally, we show that the obtained tuple $(x_{0}, \ldots, x_{g}, y, x_{g+1}, \ldots, x_{\ell - i})$ is unmatched by the matching $M_{f_{\ast }}$.

• • If ${\rm d}(x_{g}, x_{g+1}) \geq 4$, then we have ${\rm d}(y, x_{g+1}) \geq 3$, hence it satisfies (ii) of lemma 3.9.

• • If ${\rm d}(x_{g}, x_{g+1}) = 3$ and $g = 0$, then we have ${\rm d}(y, x_{1}) = 2$. Let $z$ be a vertex adjacent to both of $y$ and $x_{1}$. Then we must have ${\rm d}(x_{0}, z) = {\rm d}(x_{0}, y) + {\rm d}(y, z)$ because $x = x_{0}$ and there is no $3$-cycle containing $x$. Hence the tuple $(x_0,y,x_1,\ldots,x_{\ell -i})$ satisfies (iii) of lemma 3.9.

• • If ${\rm d}(x_{g}, x_{g+1}) = 3$ and $g \geq 1$, then we have ${\rm d}(y, x_{g+1}) = 2$ with $y = x_{g-1}$. Let $z$ be a vertex adjacent to both of $y$ and $x_{g+1}$. Then we must have ${\rm d}(x_{g}, z) = {\rm d}(x_{g}, y) + {\rm d}(y, z)$ because either of $x_{g}$ or $y = x_{g-1}$ coincides with $x$, and there are no $3$-cycles containing $x$. Hence the tuple $(x_{0}, \ldots, x_{g}, y, x_{g+1}, \ldots, x_{\ell - i})$ satisfies (iii) of lemma 3.9.

Now we consider the following truncated chain complex for $i \geq 1$:

\[ 0 \longrightarrow \mathring{\operatorname{MC}}^{x}_{\ell, \ell}(G) \longrightarrow \mathring{\operatorname{MC}}^{x}_{\ell -1, \ell}(G) \longrightarrow \cdots \longrightarrow \mathring{\operatorname{MC}}^{x}_{\ell - i - 1, \ell}(G) \longrightarrow 0. \]

We denote this chain complex by $D_{\ast }$ in the following. Let $U_{\ell - j}$ be the subset of generators of $\mathring {\operatorname {MC}}^{x}_{\ell - j, \ell }(G)$ which consists of all the tuples satisfying (ii) or (iii) in lemma 3.9 with smooth point $x_{g}$. We define maps $h_{\ell - j}\colon U_{\ell - j} \longrightarrow \mathring {\operatorname {MC}}^{x}_{\ell - j - 1, \ell }(G)$ for $1 \leq j \leq i$ by $h_{\ell - j}(x_{0}, \ldots, x_{g}, x_{g+1}, \ldots, x_{\ell - j}) = (x_{0}, \ldots, \hat {x}_{g}, x_{g+1}, \ldots, x_{\ell - j}),$ where $(x_{g}, x_{g+1})$ is the first gap. By lemma 3.12, the image of $h_{\ell - j}$ is disjoint from $U_{\ell - j - 1}$.

Lemma 3.15 Let $i\ge 1$. If $\operatorname {gir}_{x}(G) \geq 2i + 5$, then $h_{\ell -j}$ is injective for $1 \leq j \leq i$.

Proof. Suppose that $h_{\ell - j}(x_{0}, \ldots, x_{\ell -j}) = h_{\ell - j}(y_{0}, \ldots, y_{\ell -j})$. We can verify that the position of the first gaps of $(x_{0}, \ldots, x_{\ell -j})$ and $(y_{0}, \ldots, y_{\ell -j})$ are identical in the same manner as in lemma 3.5. Then we have $x_{k} = y_{k}$ except for $k = g$, where $(x_g,x_{g+1})$ and $(y_g,y_{g+1})$ are the first gaps. Since $x_{k}$ and $y_{k}$ are singular points of $(x_{0}, \ldots, x_{\ell -j})$ and $(y_{0}, \ldots, y_{\ell -j})$, respectively, for $0 \leq k \leq g-1$, we have $\{x_{0}, \ldots, x_{g}\} = \{x_{0}, x_{1}\}$ and $\{y_{0}, \ldots, y_{g}\} = \{y_{0}, y_{1}\}$ by lemma 3.4. Hence we obtain $x_{g} = y_{g}$ if $g \geq 2$. Suppose that $g = 1$ and $x_{1} \neq y_{1}$. Since $x_1$ and $y_{1}$ are smooth points of $(x_{0}, \ldots, x_{\ell -j})$ and $(y_{0}, \ldots, y_{\ell -j})$, respectively, there exist shortest paths $x=x_{0} \longrightarrow x_{1} \longrightarrow \cdots \longrightarrow x_{2} = y_{2}$ and $x=y_{0} \longrightarrow y_{1} \longrightarrow \cdots \longrightarrow x_{2} = y_{2}$ of length $1 + {\rm d}(x_{1}, x_{2})=1 + {\rm d}(y_{1}, y_{2}) \leq j + 2$. Then there exists a cycle of length $\leq 2(j+2) \leq 2i + 4$ containing $x$ as its vertex, which contradicts the assumption. Hence we obtain that $(x_{0}, \ldots, x_{\ell -j}) = (y_{0}, \ldots, y_{\ell -j})$.

By lemmas 3.12 and 3.15, we can define a matching $M_{h_{\ast }}$ of $D_{\ast }$ by injective maps $h_*=(h_{\ell - j})_{1\le j\le i}$.

Lemma 3.16 Let $i\ge 1$. If $\operatorname {gir}_{x}(G) \geq 2i + 5$, then the above matching $M_{h_{\ast }}$ is a Morse matching.

Proof. By lemma 3.11, any differentials corresponding to edges in $M_{h_{\ast }}$ are isomorphisms (cf. definition 3.1). Let $(x_{0}, \ldots, x_{g}, x_{g+1}, \ldots, x_{\ell -j}) \in \mathring {\operatorname {MC}}^{x}_{\ell - j, \ell }(G)$ with the first gap $(x_{g}, x_{g+1})$, $g\geq 0$. Let $(x_{0}, \ldots, x_{g}, x_{g+1}, \ldots, x_{\ell -j}) = a_{1} \longrightarrow b_{1} \longrightarrow a_{2} \longrightarrow b_{2} \longrightarrow \cdots$ be a path in $\Gamma ^{M_{h_{\ast }}}_{D_{\ast }}$ with $a_{p} \in \mathring {\operatorname {MC}}^{x}_{\ell - j, \ell }(G)$ and $b_{p} \in \mathring {\operatorname {MC}}^{x}_{\ell - j - 1, \ell }(G)$ for $p \in \mathbb {N}$. Here the directed edge $a_{p} \longrightarrow b_{p}$ corresponds to a directed edge in $\Gamma ^{M_{f_{\ast }}}_{C_{\ast }}$. Again by lemma 3.11, $b_1$ is obtained by deleting some smooth point of $a_1$. Hence $b_{1}$ must be of the form $(x_{0}, \ldots, x_{g}, x_{g+1}, \ldots, \hat {x}_{k}, \ldots, x_{\ell - j})$ with $g+1 \leq k \leq \ell - j - 1$, and $x_{g}$ must be its singular point to be in the image of $h_{\ell - j}$ by lemma 3.12. It follows that $a_{2}$ is of the form $(x_{0}, \ldots, x_{g}, y, x_{g+1}, \ldots, \hat {x}_{k}, \ldots, x_{\ell - j}),$ where $(y,x_{g+1})$ is the first gap. Inductively, we conclude that the first gap of $a_i$ moves backward as $i$ increases. Hence there cannot be any cycle in $\Gamma ^{M_{h_{\ast }}}_{D_{\ast }}$.

Proof of theorem 1.3. Proof of theorem 1.3

By theorem 3.2 and lemma 3.16, the chain complex $D_{\ast }$ is homotopy equivalent to the chain complex consisting of all the unmatched tuples by $M_{h_{\ast }}$. By lemma 3.13, any tuples satisfying the condition (iii) in lemma 3.9 are matched. By lemma 3.14, any tuples satisfying the condition (ii) or (iv) in lemma 3.9 are matched. Hence it turns out that the unmatched tuples by $M_{h_{\ast }}$ are only those satisfying the condition (i) of lemma 3.9 except for the tuples in $\operatorname {MC}^{x}_{\ell - i - 1, \ell }(G)$. Hence the statement follows.

3.4 A criterion for diagonality

We devote this subsection for proving theorem 1.5 which gives a criterion of the diagonality of graphs. First we recall the definition of the local girth of a graph at a fixed edge, as seen in the Introduction.

Definition 3.17 Let $G$ be a graph and $e \in E(G)$ be an edge. We define the local girth of $G$ at $e$ by

\[ \operatorname{gir}_e(G) := \inf\{i\ge3\mid\text{ there exists an}\ i\text{-cycle in}\ G\ \text{containing}\ e\ \text{as its edge}\}. \]

Proof of theorem 1.5. Proof of theorem 1.5

We first prove for the case that $k$ is odd. We put $k = 2K+1$. Let $1, 2, \ldots, 2K+1$ be vertices of a $(2K+1)$-cycle with $e = \{1, 2\}$. We suppose that each vertex $i$ is adjacent to the vertices $i-1$ and $i+1$, where we put $0 = 2K+1$ and $2K+2 = 1$. Note that the distance between each pair of vertices of this cycle in $G$ is identical to that of the cycle graph itself. If not, there will be cycles of length $< 2K+1$ containing $e$, which contradicts the assumption. In particular, we have ${\rm d}(1, K+2) = {\rm d}(2, K+2) = K$. We show that the homology cycle

\[ [(1, 2, K+2)] \in \operatorname{MH}^{1, K+2}_{2, K+1}(G) \]

is non-trivial.

Assume that we have $[(1, 2, K+2)] = 0$, that is, there exist not necessarily distinct tuples $\alpha _{1}, \ldots, \alpha _{n} \in \operatorname {MC}^{1, K+2}_{3, K+1}(G)$ and a vertex $a \in V(G)$ such that

\[ \partial \left( (1, 2,a, K+2) + ({-}1)^{s_1} \alpha_{1} + \cdots + ({-}1)^{s_{n}}\alpha_{n} \right) = (1, 2, K+2). \]

Here, $s_1,\ldots,s_n\in \{0,1\}$ and we set $s_0 = 0$. Note that any tuples of the form $(1, a, 2, K+2)$ do not appear in $\alpha _i$'s, because $L(1, a, 2, K+2) > K+1$. We put $\alpha _{0} = (1, 2, a, K+2)$ and $\alpha _{i} = (1, x_{i}, y_{i}, K+2)$ for $i\in \{1,\ldots,n\}$.

Now we construct a graph $A(G)$ with vertices $\{2, a, x_{1}, y_{1}, \ldots, x_{n}, y_{n}\}$. We span an edge between $v, w$ if $(1, v, w, K+2) = \alpha _{i}$ or $(1, w, v, K+2) = \alpha _{i}$ for some $i$. Then we have the following lemma. In the following, we denote by $\langle v_1, \ldots, v_n \rangle$ a path in a graph consisting of edges $\{v_1, v_2\}, \ldots,\{v_{n-1}, v_n\}$ in this order to make it easy to distinguish between the paths and tuples.

Lemma 3.18 Let $x$ be a vertex of $A(G)$ which is connected to the vertex $2$. Let $\langle 1, b_{1}, \ldots, x\rangle$ be a shortest path in $G$ connecting 1 and $x$. Then $b_{1} = 2$.

Proof. Let $\langle 2, a_{1}, a_{2}, \ldots, x = a_{N} \rangle$ be a path in $A(G)$ connecting 2 and $x$. Note that $a_{1}$ satisfies that ${\rm d}(1, 2) + {\rm d}(2, a_{1}) + {\rm d}(a_{1}, K+2) = K + 1$ because $(1, 2, a_{1}, K + 2) = \alpha _{m}$ for some $m$. Let $\langle 1, b^{i}_{1}, \ldots, a_{i}\rangle$ be a shortest path in $G$ connecting 1 and $a_i$. We show that $b^{i}_{1} = 2$ by induction on $i$. If $b^{1}_1 \neq 2$, then a closed path obtained by concatenating three paths, $\langle 1, b^{1}_1, \ldots, a_1 \rangle$, a shortest path connecting $a_1$ and 2, and the edge between 2 and 1 produces a cycle containing $e$. Note here that the shortest path from $2$ to $a_{1}$ does not pass through $1$. If it goes through $1$, then we have $K+1 = {\rm d}(1, 2) + {\rm d}(2, a_{1}) + {\rm d}(a_{1}, K+2) = 2 + {\rm d}(1, a_{1}) + {\rm d}(a_{1}, K +2) \geq 2 + {\rm d}(1, K+2) = K+2$. Because ${\rm d}(1, 2) + {\rm d}(2, a_1) \leq K$, the obtained cycle is of length $\leq 2K$, which contradicts the assumption. Hence we have $b^{1}_1 = 2$.

Suppose $b^{i}_{1} = 2$ and $b^{i+1}_{1} \neq 2$. If $(1, a_{i}, a_{i+1}, K+2) = \alpha _{m}$ for some $m$, then a closed path obtained by concatenating three paths, $\langle 1, b^{i}_1, \ldots, a_i\rangle$, a shortest path connecting $a_i$ and $a_{i+1}$, and $\langle a_{i+1}, \ldots, b^{i+1}_1, 1\rangle$ produces a cycle containing $e$. Note here that the shortest path from $a_i$ to $a_{i+1}$ does not pass through $1$ in the same manner as discussed above. Because ${\rm d}(1, a_{i}) + {\rm d}(a_{i}, a_{i+1}) \leq K$, the obtained cycle is of length $\leq 2K$, which contradicts the assumption. Similarly, if $(1, a_{i+1}, a_{i}, K+2) = \alpha _{m}$ for some $m$, then a closed path obtained by concatenating three paths, $\langle 1, b^{i}_1, \ldots, a_i\rangle$, a shortest path connecting $a_i$ and $a_{i+1}$, and $\langle a_{i+1}, \ldots, b^{i+1}_1, 1\rangle$ produces a cycle containing $e$. Because ${\rm d}(1, a_{i+1}) + {\rm d}(a_{i+1}, a_{i}) \leq K$, the obtained cycle is of length $\leq 2K$, which also contradicts the assumption. Hence we have $b^{i+1}_1 = 2$.

Now we divide the collection of tuples $\alpha _{0} = (1, 2, a, K+2), \alpha _{1}, \ldots, \alpha _{n}$ into subcollections $C_{0}, \ldots, C_{M}$ corresponding to the connected components of $A(G)$. Namely, two tuples $\alpha _{i}$ and $\alpha _{j}$ belong to the same subcollection if the corresponding edges in $A(G)$ are connected by some path. We suppose that $(1, 2, a, K+2) \in C_{0}.$ Then we have

\[ \partial \left( \sum_{i\geq 1}\sum_{\alpha_{j} \in C_{i}} ({-}1)^{s_{j}}\alpha_{j} \right) = 0. \]

If not, there exists a tuple $(1, x, K+2) \neq (1, 2, K+2)$ which appears in the left-hand side, and also in $\partial ( \sum _{\alpha _{j} \in C_{0}} (-1)^{s_{j}}\alpha _{j} )$ with the opposite sign, because the total sum is $(1, 2, K+2)$. Then it implies that the vertex $x$ in $A(G)$ belongs to two distinct connected components of $A(G)$, which is a contradiction. Hence we have

\[ \partial \left( \sum_{\alpha_{j} \in C_{0}} ({-}1)^{s_{j}}\alpha_{j} \right) = (1, 2, K+2), \]

which implies that there exists a tuple $\alpha _{m} = (1, x_{m}, y_{m}, K+2) \in C_{0}$ such that $L(1, x_{m}, K+2) = K$ or $L(1, y_{m}, K+2) = K$, because the right-hand side consists of odd terms. If $L(1, x_{m}, K+2) = K$, then a path in $G$ obtained by concatenating a shortest path connecting $1$ and $x_{m}$, and a shortest path connecting $x_{m}$ and $K+2$ is a shortest path connecting $1$ and $K+2$. Because a shortest path connecting $1$ and $x_{m}$ goes through $2$ by lemma 3.18, we have ${\rm d}(2, K+2)= {\rm d}(1, K+2) - {\rm d}(1, 2) = K-1$, which is not true. We also have a contradiction from the same argument for the case that $L(1, y_{m}, K+2) = K$. This completes a proof for the case that $k$ is odd.

Next we prove for the case that $k$ is even. We put $k = 2K$, and let $1, 2, \ldots, 2K$ be vertices of $2K$-cycle with $e = \{1, 2\}$ similarly to the odd case. Note that we have ${\rm d}(1, K+1) = K$. We show that the homology cycle $[(1, 2, K+1) - (1, 2K, K+1)] \in \operatorname {MH}^{1, K+1}_{2,K}(G)$ is non-trivial. Assume that we have $[(1, 2, K+1) - (1, 2K, K+1)] = 0$, that is, there exist tuples $\alpha _{1}, \dots, \alpha _{n} \in \operatorname {MC}^{1, K+1}_{3,K}(G)$ and vertices $a, b\in V(G)$ such that

\begin{align*} \partial & \left( (1, 2, a, K+1) + ({-}1)^{s_1}\alpha_{1} + \cdots + ({-}1)^{s_n}\alpha_{n} - (1, 2K, b, K+1) \right) \\ & = (1, 2, K+1) - (1, 2K, K+1). \end{align*}

Note that any tuples of the form $(1, a, 2, K+1)$ and $(1, b, 2K, K+1)$ do not appear in $\alpha _i$'s, because $L(1, a, 2, K+1), L(1, b, 2K, K+1) > K$. We put $\alpha _{0} = (1, 2, a, K+1)$, $\alpha _{n+1} = (1, 2K, b, K+1)$ and $\alpha _{i} = (1, x_{i}, y_{i}, K+2)$ for $i\in \{1,\ldots,n\}$. Similarly to the odd case, we construct a graph $A(G)$ with vertices $\{2, a, x_{1}, y_{1}, \ldots, x_{n}, y_{n}, 2K, b\}.$ Then the same statement in lemma 3.18 holds. It is proved in a similar way to lemma 3.18 as follows.

Proof of lemma 3.18 for k = 2K case. Proof of lemma 3.18 for k = 2K case

Let $\langle 2, a_{1}, a_{2}, \ldots, x = a_{N} \rangle$ be a path in $A(G)$ connecting 2 and $x$. Note that $a_{1}$ satisfies that ${\rm d}(1, 2) + {\rm d}(2, a_{1}) + {\rm d}(a_{1}, K+1) = K$ because $(1, 2, a_{1}, K + 1) = \alpha _{m}$ for some $m$. Let $\langle 1, b^{i}_{1}, \ldots, a_{i}\rangle$ be a shortest path in $G$ connecting 1 and $a_i$. We show that $b^{i}_{1} = 2$ by induction on $i$. If $b^{1}_1 \neq 2$, then a closed path obtained by concatenating three paths, $\langle 1, b^{1}_1, \ldots, a_1 \rangle$, a shortest path connecting $a_1$ and $2$, and the edge between $2$ and $1$ produces a cycle containing $e$. Note here that the shortest path from $2$ to $a_{1}$ does not pass through $1$. If it goes through $1$, then we have $K = {\rm d}(1, 2) + {\rm d}(2, a_{1}) + {\rm d}(a_{1}, K+1) = 2 + {\rm d}(1, a_{1}) + {\rm d}(a_{1}, K + 1) \geq 2 + {\rm d}(1, K+1) = K+2$. Because ${\rm d}(1, 2) + {\rm d}(2, a_1) \leq K-1$, the obtained cycle is of length $\leq 2K-2$, which contradicts the assumption. Hence we have $b^{1}_1 = 2$.

Suppose $b^{i}_{1} = 2$ and $b^{i+1}_{1} \neq 2$. If $(1, a_{i}, a_{i+1}, K+1) = \alpha _{m}$ for some $m$, then a closed path obtained by concatenating three paths, $\langle 1, b^{i}_1, \dots, a_i\rangle$, a shortest path connecting $a_i$ and $a_{i+1}$, and $\langle a_{i+1}, \dots, b^{i+1}_1, 1\rangle$ produces a cycle containing $e$. Note here that the shortest path from $a_i$ to $a_{i+1}$ does not pass through $1$ in the same manner as discussed above. Because ${\rm d}(1, a_{i}) + {\rm d}(a_{i}, a_{i+1}) \leq K-1$, the obtained cycle is of length $\leq 2K-2$, which contradicts the assumption. Similarly, if $(1, a_{i+1}, a_{i}, K+2) = \alpha _{m}$ for some $m$, then a closed path obtained by concatenating three paths, $\langle 1, b^{i}_1, \ldots, a_i \rangle$, a shortest path connecting $a_i$ and $a_{i+1}$, and $\langle a_{i+1}, \ldots, b^{i+1}_1, 1 \rangle$ produces a cycle containing $e$. Because ${\rm d}(1, a_{i+1}) + {\rm d}(a_{i+1}, a_{i}) \leq K-1$, the obtained cycle is of length $\leq 2K-2$, which also contradicts the assumption. Hence we have $b^{i+1}_1 = 2$.

Now we can show that the vertices $2$ and $b$ in $A(G)$ belong to the same connected component as follows. Divide the collection of tuples $(1, 2, a, K+1), \alpha _{1}, \ldots, \alpha _{n}, (1, 2K, b, K+1)$ into subcollections $C_{0}, \ldots, C_{M}$ corresponding to the connected components of $A(G)$. Suppose that $(1, 2, a, K+1) \in C_{0}$ and $(1, 2K, b, K+1) \in C_{1}$. By the same argument as that in the odd case, we have

\[ \partial \left( \sum_{i\geq 2}\sum_{\alpha_{j} \in C_{i}} ({-}1)^{s_{j}}\alpha_{j} \right) = 0. \]

Because ${\rm d}(1, K+1) = K$, every tuple $\alpha _{i}$ has no singular points other than the end points. Hence two chains $\partial ( \sum _{\alpha _{j} \in C_{0}} (-1)^{s_{j}}\alpha _{j} )$ and $\partial ( \sum _{\alpha _{j} \in C_{1}} (-1)^{s_{j}}\alpha _{j} )$ must have a common term up to sign. It contradicts the disconnectedness assumption for $C_{0}$ and $C_{1}$, hence the vertices $2$ and $b$ in $A(G)$ belong to the same connected component. Since the tuple $(1,2K,b,K+1)$ has no singular points, a path in $G$ obtained by concatenating the edge between $1$ and $2K$, and a shortest path connecting $2K$ and $b$ is a shortest path connecting $1$ and $b$. This is a contradiction because every shortest path in $G$ connecting $1$ and $b$ passes through $2$ at the first step by lemma 3.18 for $k=2K$ case.

4. Stochastic properties of the magnitude homology

In this section, we prove theorems 1.7, 1.8 and 1.9. The proofs follow from the results in § 3 together with standard arguments in the random graph theory.

4.1 Phase transition of diagonality

In this subsection, we provide the proof of theorem 1.7. We first prove theorem 1.7(1) which follows from the fact that a.a.s. $G_{n,p}$ has no cycles whenever $p=o(n^{-1})$. In what follows, for $i\ge 3$, we denote by $C_i$ the number of $i$-cycle graphs in $G_{n,p}$.

Proof of theorem 1.7(1). Proof of theorem 1.7(1)

For $i\ge 3$, a straightforward calculation yields $\mathbb {E} C_i \le \binom {n}{i}(i!/(2i))p^i \le (np)^i/(2i)$. Indeed, there are $\binom {n}{i}$ ways of selecting $i$ vertices of an $i$-cycle graph from $n$ vertices, and to each selection, there are $i!/(2i)$ ways of choosing the edges of the $i$-cycle graph. Lastly, the probability that the chosen $i$ edges are included in $G_{n,p}$ is $p^i$ because of the mutual independence of the edge appearance. As seen in example 2.7, all trees, or more generally forests, are diagonal. Therefore, we have

\[ \mathbb{P}(G_{n,p}\text{ is non-diagonal})\le\mathbb{P}\left(\sum_{i=3}^\infty C_i\ge1\right)\le\sum_{i=3}^\infty\mathbb{E} C_i\le\sum_{i=3}^\infty\frac{(np)^i}{2i}. \]

In the second inequality, we use Markov's inequality. The right-hand side converges to zero as $n\to \infty$, which completes the proof.

We now turn to proving theorem 1.7(2) (3). For their proofs, we divide the concerned regime of $p$ into two parts: (a) $p=cn^{-1}$ for some $0< c<1$; and (b) $\liminf _{n\to \infty }np>1$ and $p=o(n^{-3/4})$. We then discuss the asymptotic behaviour of $\mathbb {P}(G_{n,p}\text { is non-diagonal})$ in each part in different ways.

For the estimate of $\mathbb {P}(G_{n,p}\text { is non-diagonal})$ in part (a), we use the following lemma which states that almost all vertices belong to tree components and that there exist no components containing more than one cycle. Let $T(G_{n,p})$ denote the number of vertices in $G_{n,p}$ belonging to some tree component.

Lemma 4.1 (Theorem 5.7(ii) and corollary 5.8 in [2])

Let $p=cn^{-1}$ for some fixed $0< c<1$. Then, $\mathbb {E}[T(G_{n,p})]=n-O(1)$. In addition, every component is either tree or unicyclic a.a.s.

The following lemma is also useful.

Lemma 4.2 (Corollary 4.9 in [2])

Let $p=cn^{-1}$ for some fixed $c>0$. Then, for each $m\ge 3$, $(C_3,C_4,\ldots,C_m)$ converges to $(Z_3,Z_4,\ldots,Z_m)$ in distribution as $n\to \infty$. Here, $\{Z_i\}_{i=3}^m$ are mutually independent random variables, and each $Z_i$ follows the Poisson distribution with parameter $c^i/(2i)$. In other words, for each $m\ge 3$ and $(a_3,a_4,\ldots,a_m)\in \mathbb {Z}_{\ge 0}^{m-2}$,

\[ \lim_{n\to\infty}\mathbb{P}((C_3,C_4,\ldots,C_m)=(a_3,a_4,\ldots,a_m)) =\prod_{i=3}^m\frac{\{c^i/(2i)\}^{a_i}}{a_i!}\exp\left(-\frac{c^i}{2i}\right). \]

Combining lemmas 4.1 and 4.2, we obtain the estimate of $\mathbb {P}(G_{n,p}\text { is diagonal})$ in part (a) as follows.

Proposition 4.3 Let $p=cn^{-1}$ for some fixed $0< c<1$. Then,

\[ \lim_{n\to\infty}\mathbb{P}(G_{n,p}\text{ is diagonal})=\sqrt{1-c}\exp(c/2+c^2/4+c^3/6+c^4/8). \]

Proof. Let $F_1$ and $F_2$ denote the events that $G_{n,p}$ is diagonal and that $G_{n,p}$ does not contain any cycles of length at least $5$, respectively. We additionally define $E$ as the event that every component in $G_{n,p}$ is either tree or unicyclic. We can confirm that every unicyclic component that has a cycle of length at least $5$ is non-diagonal. This follows from the Mayer–Vietoris theorem for the magnitude homology [9, theorem 6.6] combining with the fact that any cycle graphs of length at least $5$ are non-diagonal (cf. [8, theorems 4.6 and 4.8]). Therefore, we have $E\cap F_1\subset E\cap F_2$. On the other hand, it holds that $E\cap F_1\supset E\cap F_2$ by using again the Mayer–Vietoris theorem with the fact that tree graphs and $3$- or $4$-cycle graphs are diagonal (cf. [9, examples 2.5 and 5.4]). Consequently, we obtain $E\cap F_1=E\cap F_2$. Thus, it reduces to prove that

(4.1)\begin{equation} \lim_{n\to\infty}\mathbb{P}(F_2) =\sqrt{1-c}\exp(c/2+c^2/4+c^3/6+c^4/8). \end{equation}

Indeed, $|\mathbb {P}(F_1)-\mathbb {P}(F_2)|=|\mathbb {P}(F_1\setminus E)-\mathbb {P}(F_2\setminus E)|\le \mathbb {P}(E^c)=o(1)$ from the second conclusion of lemma 4.1.

Now, let $m\ge 5$ be fixed, and let $D$ denote the event that every cyclic component has at most $m$ vertices. Then, we have

(4.2)\begin{align} \mathbb{P}(C_5=C_6=\cdots=C_m=0)\ge\mathbb{P}(F_2) & \ge\mathbb{P}(\{C_5=C_6=\cdots=C_m=0\}\cap D)\nonumber\\ & \ge\mathbb{P}(C_5=C_6=\cdots=C_m=0)-\mathbb{P}(D^c). \end{align}

From the first conclusion of lemma 4.1, we can take a constant $K$, depending only on $c$, such that $n-\mathbb {E}[T(G_{n,p})]\le K$ for all $n$. Since the number of cyclic components that have more than $m$ vertices is bounded above by $(n-T(G_{n,p}))/m$, we obtain $\mathbb {P}(D^c) \le (n-\mathbb {E}[T(G_{n,p})])/m\le K/m$ using Markov's inequality in the first inequality. Furthermore, lemma 4.2 yields

\[ \lim_{n\to\infty}\mathbb{P}(C_5=C_6=\cdots=C_m=0) =\prod_{i=5}^m\exp\left(-\frac{c^i}{2i}\right) =\exp\left(-\frac12\sum_{i=5}^m\frac{c^i}i\right). \]

Combining the above estimates with equation (4.2), we obtain

\[ \exp\left(-\frac12\sum_{i=5}^m\frac{c^i}i\right)\ge\limsup_{n\to\infty}\mathbb{P}(F_2)\ge\liminf_{n\to\infty}\mathbb{P}(F_2)\ge\exp\left(-\frac12\sum_{i=5}^m\frac{c^i}i\right)-\frac Km. \]

Equation (4.1) follows from the equation above by taking $m\to \infty$, noting that

\[ \exp\left(-\frac12\sum_{i=5}^\infty\frac{c^i}i\right) =\sqrt{1-c}\exp(c/2+c^2/4+c^3/6+c^4/8). \]

For the estimate of $\mathbb {P}(G_{n,p}\text { is non-diagonal})$ in part (b), we use the following lemma. For a graph $G$, let us denote the number of connected components of $G$ by $\xi (G)$.

Lemma 4.4 [6, § 6]

Let $p=cn^{-1}$ for some fixed constant $c>0$. Then, for any $\varepsilon >0$, it holds that $\lim _{n\to \infty }\mathbb {P}(|\xi (G_{n,p})/n-u(c)|>\varepsilon )=0,$ where $u(c)=(1/c)\sum _{i=1}^\infty i^{i-2}(c{\rm e}^{-c})^i/i!$.

For a graph $G$, the circuit rank $r(G)$ indicates the minimum number of edges that must be removed from $G$ to contain no cycles. As a well-known fact, it holds that $r(G)=\#E(G)-\#V(G)+\xi (G)$.

Lemma 4.5 Let $p=cn^{-1}$ for some fixed constant $c>1$. Then, there exists a constant $\delta >0$ such that $r(G_{n,p})\ge \delta n$ a.a.s.

Proof. We can verify that $u(c)>1-c/2$ whenever $c>1$ (see also figure 3). Therefore, lemma 4.4 implies that for $c>1$, there exists a constant $\delta >0$ such that $\xi (G_{n,p})\ge (1-c/2+2\delta )n$ a.a.s. Furthermore, since $\#E(G_{n,p})$ follows the binomial distribution with parameters $\binom {n}{2}$ and $cn^{-1}$, a direct computation yields $\lim _{n\to \infty }\mathbb {E}[\#E(G_{n,p})/n] =c/2$ and $\lim _{n\to \infty }\operatorname {Var}(\#E(G_{n,p})/n) =0$. Therefore, using the Minkowski inequality,

(4.3)\begin{align} & \mathbb{E}\left[\left(\frac{\#E(G_{n,p})}n-\frac c2\right)^2\right]^{1/2}\nonumber\\ & \quad\le\mathbb{E}\left[\left(\frac{\#E(G_{n,p})}n-\mathbb{E}\left[\frac{\#E(G_{n,p})}n\right]\right)^2\right]^{1/2}+ \left|\mathbb{E}\left[\frac{\#E(G_{n,p})}n\right]-\frac c2\right|\nonumber\\ & \quad=\sqrt{\operatorname{Var}\left(\frac{\#E(G_{n,p})}n\right)}+\left|\mathbb{E}\left[\frac{\#E(G_{n,p})}n\right]-\frac c2\right| \xrightarrow[n\to\infty]{}0. \end{align}

Thus, from Markov's inequality, we have $\#E(G_{n,p})\ge (c/2-\delta )n$ a.a.s. Combining these estimates above, we obtain a.a.s.

\[ r(G_{n,p})=\#E(G_{n,p})-n+\xi(G_{n,p})\ge(c/2-\delta)n-n+(1-c/2+2\delta)n=\delta n. \]

FIG. 3. Description of $u(c)$ in lemma 4.4.

We now provide the estimate of $\mathbb {P}(G_{n,p}\text { is non-diagonal})$ in part (b).

Proposition 4.6 Let $\liminf _{n\to \infty }np>1$ and $p=o(n^{-3/4})$. Then, $G_{n,p}$ is non-diagonal a.a.s.

Proof. Let $X$ denote the number of edges $e\in E(G_{n,p})$ such that $\operatorname {gir}_e(G_{n,p})\in [5,\infty )$. From theorem 1.5, it suffices to prove that $X\ge 1$ a.a.s. We define $Y$ as the number of edges that are contained in some cycle. Then, $Y\ge r(G_{n,p})$ because of the definition of the circuit rank. Thus, by applying lemma 4.5 with some fixed constant $1< c<\liminf _{n\to \infty }np$, there exists a constant $\delta >0$ such that $Y\ge r(G_{n,p})\ge \delta n$ a.a.s. For $i\ge 3$, we additionally define $Y_i$ as the number of edges that are contained in some $i$-cycle. Then,

\[ \mathbb{P}\left(Y_i>\frac\delta 3n\right)\le\frac3{\delta n}\mathbb{E} Y_i\le\frac{3i}{\delta n}\mathbb{E} C_i \le\frac{3i}{\delta n}\frac{(np)^i}{2i} =\frac3{2\delta}n^{i-1}p^i. \]

The first inequality follows from Markov's inequality. In the second inequality, we use a crude estimate $Y_i\le iC_i$. Since $p=o(n^{-3/4})$, for $i=3,4$, the right-hand side of the above equation converges to zero as $n\to \infty$. Therefore, $Y_3,Y_4\le \delta n/3$ a.a.s. Combining the estimates for $Y$, $Y_3$, and $Y_4$,

\[ \mathbb{P}\left(X\ge\frac\delta 3n\right)\ge\mathbb{P}\left(Y-Y_3-Y_4\ge\frac\delta 3n\right) \ge\mathbb{P}\left(Y\ge\delta n\text{ and }Y_3,Y_4\le\frac\delta 3n\right)\xrightarrow[n\to\infty]{}1, \]

which completes the proof.

Combining propositions 4.3 and 4.6, we obtain the conclusion of theorem 1.7.

Lastly, we prove theorem 1.8. The notion of pawful graphs, introduced by Gu [8], is a key for the proof. Recall from definition 2.9 that a pawful graph $G$ is a graph of diameter at most two satisfying the property that for any distinct vertices $x,y,z\in V(G)$ with ${\rm d}(x,y)={\rm d}(y,z)=2$ and ${\rm d}(z,x)=1$, they have a common neighbour. Since pawful graphs are diagonal, the conclusion of theorem 1.8 follows immediately from the following theorem.

Theorem 4.7 [10, theorem 3.2]

Let $m\in \mathbb {N}$ and $\varepsilon >0$. If $p\ge (({(m+\varepsilon )\log n})/n)^{1/m}$, then every $m$ vertices in $G_{n,p}$ have a common neighbour a.a.s.

4.2 Weak law of large numbers for the rank of the magnitude homology

In this subsection, we prove theorem 1.9 using theorem 1.3. We first give a general upper bound of the rank of the magnitude homology of a graph.

Lemma 4.8 Let $G$ be a graph, and let $x\in V(G)$ be fixed. Then, for any $k,\ell \in \mathbb {N}$, $\operatorname {rk}(\operatorname {MH}_{k,\ell }^x(G))\le \binom {\ell -1}{k-1}(\max _{y\in V(G)}\deg y)^\ell.$

Proof. Recall that the generator set of $\operatorname {MC}_{k,\ell }^x(G)$ is

\begin{align*} & \left\{(x_0,x_1,\ldots,x_k)\in V(G)^{k+1}\left| \begin{array}{@{}l@{}} x_0=x, L(x_0,\ldots,x_k)=\ell,\\ x_i\neq x_{i+1} \text{ for } 0\leq i \leq k-1 \end{array}\right.\right\}\\ & \quad=\bigsqcup_{\substack{(\ell_1,\ell_2,\ldots,\ell_k)\in\mathbb{N}^k\\ \ell_1+\ell_2+\cdots+\ell_k=\ell}}\{(x_0,\ldots,x_k)\in V(G)^{k+1}\mid x_0=x,{\rm d}(x_{i-1},x_i)\,{=}\,\ell_i\text{ for }1\le i\le k\}. \end{align*}

Noting that for any $u\in V(G)$ and $r\in \mathbb {N}$,

\[ \#\{v\in V(G)\mid {\rm d}(u,v)=r\}\le\left(\max_{y\in V(G)}\deg y\right)^r, \]

we have

\begin{align*} & \#\{(x_0,x_1,\ldots,x_k)\in V(G)^{k+1}\mid x_0=x,{\rm d}(x_{i-1},x_i)=\ell_i\text{ for }1\le i\le k\}\\ & \quad\le\prod_{i=1}^k\left(\max_{y\in V(G)}\deg y\right)^{\ell_i} =\left(\max_{y\in V(G)}\deg y\right)^\ell \end{align*}

for any $(\ell _1,\ell _2,\ldots,\ell _k)\in \mathbb {N}^k$ with $\ell _1+\ell _2+\cdots +\ell _k=\ell$. Furthermore, a simple combinatorial argument yields $\#\{(\ell _1,\ell _2,\ldots,\ell _k)\in \mathbb {N}^k \mid \ell _1+\ell _2+\cdots +\ell _k=\ell \}=\binom {\ell -1}{k-1}.$ Thus, we conclude that

\[ \operatorname{rk}(\operatorname{MH}_{k,\ell}^x(G))\le\operatorname{rk}(\operatorname{MC}_{k,\ell}^x(G))\le\binom {\ell-1}{k-1}\left(\max_{y\in V(G)}\deg y\right)^\ell. \]

The following lemma gives a useful upper bounds of the probability that a binomial distributed random variable is larger than expected.

Lemma 4.9 [13, lemma 1.1]

Suppose $N\in \mathbb {N}$, $p\in (0,1)$, and $0< k< N$. Let $X$ be a binomial random variable with parameters $N$ and $p$, and set $\mu := \mathbb {E} X=Np$. If $k\ge e^2\mu$, then $\mathbb {P}(X>k)\le \exp (-(k/2)\log (k/\mu ))$.

In what follows, let the Erdős–Rényi graph $G_{n,p}$ be constructed on an $n$-vertex set $V_n$, and let $o\in V_n$ be an arbitrarily fixed vertex.

Lemma 4.10 Let $k,\ell \in \mathbb {N}$ be fixed. Then, for sufficiently large $n$ and any $x\in V_n$, it holds that $\mathbb {E}[\operatorname {rk}(\operatorname {MH}_{k,\ell }^x(G_{n,p}))^2]\le \binom {\ell -1}{k-1}^2(\log n)^{2\ell }.$

Proof. Let $D$ be the event that the maximum degree of $G_{n,p}$ is at most $(\log n)/2$. Then, $\mathbb {P}(D^c)\le \sum _{y\in V_n}\mathbb {P}(\deg y>(\log n)/2) =n\mathbb {P}(\deg o>(\log n)/2).$ Note that $\deg o$ follows the binomial distribution with parameters $n-1$ and $cn^{-1}$, and set $\mu := \mathbb {E}[\deg o]=(n-1)cn^{-1}$. Applying lemma 4.9 with $N=n-1$, $p=cn^{-1}$, and $k=(\log n)/2$, we have

\begin{align*} \mathbb{P}\left(\deg o>\frac{\log n}2\right)& \le\exp\left(-\frac{\log n}4\log\left(\frac{\log n}{2\mu}\right)\right)\\& \le\exp\left(-\frac{\log n\log\log n}5\right)=n^{-(({\log\log n})/5)} \end{align*}

for sufficiently large $n$. Therefore, for sufficiently large $n$ and any $x\in V_n$, we obtain

\begin{align*} \mathbb{E}\left[\operatorname{rk}(\operatorname{MH}_{k,\ell}^x(G))^2\right] & \le\binom {\ell-1}{k-1}^2\mathbb{E}\left[\left(\max_{y\in V_n}\deg y\right)^{2\ell}\right]\\ & \le\binom {\ell-1}{k-1}^2\left\{\mathbb{E}\left[\left(\max_{y\in V_n}\deg y\right)^{2\ell};D\right]+n^{2\ell}\mathbb{P}(D^c)\right\}\\ & \le\binom {\ell-1}{k-1}^2\left\{\left(\frac{\log n}2\right)^{2\ell}+n^{2\ell+1-(({\log\log n})/5)}\right\}\\& \le\binom {\ell-1}{k-1}^2(\log n)^{2\ell}. \end{align*}

In the first inequality, we use lemma 4.8.

We now turn to proving theorem 1.9 using theorem 1.3.

Proof of theorem 1.9. Proof of theorem 1.9

Since $\operatorname {MH}_{k,\ell }(G_{n,p})=0$ if $\ell < k$, we assume that $\ell \ge k$. For $i\ge 3$, define $E_i^x$ as the event that $G_{n,p}$ has at least one $i$-cycle containing $x$, and set $E^x := \bigcup _{i=3}^{2(\ell -k)+4}E_i^x.$ Applying theorem 1.3, we have

\begin{align*} \frac{\operatorname{rk}(\operatorname{MH}_{k,\ell}(G_{n,p}))}n & =\frac1n\sum_{x\in V_n}\operatorname{rk}(\operatorname{MH}_{k,\ell}^x(G_{n,p}))\\ & \le\frac1n\sum_{x\in V_n}\left\{(\deg x)\delta_{k,\ell}+\operatorname{rk}(\operatorname{MH}_{k,\ell}^x(G_{n,p}))1_{E^x}\right\}\\ & =\frac{2\#E(G_{n,p})}n\delta_{k,\ell}+\frac1n\sum_{x\in V_n}\operatorname{rk}(\operatorname{MH}_{k,\ell}^x(G_{n,p}))1_{E^x}. \end{align*}

On the other hand, since $\operatorname {rk}(\operatorname {MH}_{\ell,\ell }(G_{n,p}))\ge 2\#E(G_{n,p})$, we have

\[ \frac{\operatorname{rk}(\operatorname{MH}_{k,\ell}(G_{n,p}))}n\ge\frac{2\#E(G_{n,p})}n\delta_{k,\ell}. \]

Combining these estimates, we obtain

\[ \left|\frac{\operatorname{rk}(\operatorname{MH}_{k,\ell}(G_{n,p}))}n-\frac{2\#E(G_{n,p})}n\delta_{k,\ell}\right|\le\frac1n\sum_{x\in V_n}\operatorname{rk}(\operatorname{MH}_{k,\ell}^x(G_{n,p}))1_{E^x}. \]

Therefore, using the triangle inequality,

(4.4)\begin{align} & \mathbb{E}\left|\frac{\operatorname{rk}(\operatorname{MH}_{k,\ell}(G_{n,p}))}n-c\delta_{k,\ell}\right|\nonumber\\ & \quad\le\mathbb{E}\left|\frac{\operatorname{rk}(\operatorname{MH}_{k,\ell}(G_{n,p}))}n-\frac{2\#E(G_{n,p})}n\delta_{k,\ell}\right|+\mathbb{E}\left|\frac{2\#E(G_{n,p})}n\delta_{k,\ell}-c\delta_{k,\ell}\right|\nonumber\\ & \quad\le\frac1n\sum_{x\in V_n}\mathbb{E}[\operatorname{rk}(\operatorname{MH}_{k,\ell}^x(G_{n,p}))1_{E^x}]+\mathbb{E}\left|\frac{2\#E(G_{n,p})}n-c\right|\delta_{k,\ell}\nonumber\\ & \quad\le\mathbb{E}[\operatorname{rk}(\operatorname{MH}_{k,\ell}^o(G_{n,p}))1_{E^o}]+\mathbb{E}\left|\frac{2\#E(G_{n,p})}n-c\right|\nonumber\\ & \quad\le\mathbb{E}\left[\operatorname{rk}(\operatorname{MH}_{k,\ell}^o(G_{n,p}))^2\right]^{1/2}\mathbb{P}\left(E^o\right)^{1/2}+\mathbb{E}\left[\left(\frac{2\#E(G_{n,p})}n-c\right)^2\right]^{1/2}. \end{align}

In the last line, we use the Cauchy–Schwarz inequality. The second term of equation (4.4) converges to zero as $n\to \infty$, as seen in equation (4.3). For the estimate of the first term in equation (4.4), we define $C_i^o$ as the number of $i$-cycle graphs containing $o$. We then have

\[ \mathbb{P}(E_i^o) =\mathbb{P}(C_i^o\ge1)\le\mathbb{E} C_i^o =\frac{(n-1)(n-2)\cdots(n-i+1)}{2i}\left(\frac cn\right)^i\le\frac{c^i}{2in} \]

from Markov's inequality, which implies that

\[ \mathbb{P}(E^o)\le\sum_{i=3}^{2(\ell-k)+4}\mathbb{P}(E_i^o)\le\frac1{2n}\sum_{i=3}^{2(\ell-k)+4}\frac{c^i}{i}. \]

From the estimate above and lemma 4.10, the first term of equation (4.4) converges to zero as $n\to \infty$. Consequently, we obtain

\[ \lim_{n\to\infty}\mathbb{E}\left|\frac{\operatorname{rk}(\operatorname{MH}_{k,\ell}(G_{n,p}))}n-c\delta_{k,\ell}\right|=0, \]

which implies the first conclusion. Again from Markov's inequality, the above equation also implies the second conclusion.