1. Introduction
The magnitude of finite metric spaces was introduced by Leinster [Reference Leinster12] 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 [Reference Asao and Izumihara1, Reference Bottinelli and Kaiser4, Reference Gu8, Reference Hepworth and Willerton9, Reference Leinster11]. 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 [Reference Hepworth and Willerton9] 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 [Reference Hepworth and Willerton9]. Their beautiful theory enables us to compute the magnitude and magnitude homology of graphs. For example, Gu [Reference Gu8] 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 [Reference Bottinelli and Kaiser4] 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 [Reference Hepworth and Willerton9], 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 [Reference Hepworth and Willerton9], 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 [Reference Hepworth and Willerton9] for complete graph, and in [Reference Gu8] 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 [Reference Erdős and Rényi5–Reference Gilbert7]. 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
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 [Reference Gu8, Reference Hepworth and Willerton9], respectively. In particular, corollary 1.4 is a generalization of the computation of the magnitude homology of trees in [Reference Hepworth and Willerton9, 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 [Reference Sazdanovic and Summers14, 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
Corollary 1.4 Let $\ell \geq 1$
and $i\ge 0$
. If $\operatorname {gir}(G)\geq 2i + 5$
, then
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
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).
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) If $p\ll n^{-1}$
, then $G_{n,p}$ is diagonal a.a.s.(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) 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 [Reference Bollobás and Thomason3]. 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,
where $\delta _{k,\ell }$
is the Kronecker delta function. Moreover, for any $\varepsilon >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 [Reference Hepworth and Willerton9] 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. [Reference Hepworth and Willerton9, theorem 2.8]):
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,
Moreover, for any $\varepsilon >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 [Reference Hepworth and Willerton9] 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
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
and
respectively. Then we have the following obvious decompositions by the start points and the end points of tuples:
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
for $(x_0,\ldots,x_k)\in \operatorname {MC}_{k,\ell }(G)$
(see [Reference Hepworth and Willerton9, 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 [Reference Hepworth and Willerton9, 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
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 [Reference Hepworth and Willerton9, corollary 6.8]
Let $T$
be a tree, and $x\in V(T)$
be fixed. Then we have
This is verified by using Mayer–Vietoris theorem in [Reference Hepworth and Willerton9, theorem 6.6] after checking that it is compatible with the decompositions (2.2). Moreover, equation (2.2) yields
Definition 2.8 [Reference Hepworth and Willerton9, definition 7.1]
A graph $G$
is called diagonal if $\operatorname {MH}_{k, \ell }(G) = 0$
for $k\neq \ell$
.
Definition 2.9 [Reference Gu8, 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 [Reference Hepworth and Willerton9, theorem 7.5]. Moreover, pawful graphs are diagonal [Reference Gu8, 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 [Reference Sköldberg15]. The matching that we construct in § 3.2 and3.3 is quite similar to that of Gu's [Reference Gu8]. While he constructs matchings for several specific graphs in [Reference Gu8], 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 [Reference Gu8], and see [Reference Sköldberg15] 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 [Reference Sköldberg15]
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
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
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
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
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
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$:$
(i) It has no gaps and no smooth points.
(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.(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})$.(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
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$
:
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
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
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
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
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
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
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
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
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 [Reference Bollobás2])
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 [Reference Bollobás2])
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}$
,
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,
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 [Reference Hepworth and Willerton9, theorem 6.6] combining with the fact that any cycle graphs of length at least $5$
are non-diagonal (cf. [Reference Gu8, 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. [Reference Hepworth and Willerton9, examples 2.5 and 5.4]). Consequently, we obtain $E\cap F_1=E\cap F_2$
. Thus, it reduces to prove that
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
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
Combining the above estimates with equation (4.2), we obtain
Equation (4.1) follows from the equation above by taking $m\to \infty$
, noting that
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 [Reference Erdős and Rényi6, § 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,
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.
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,
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$
,
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 [Reference Gu8], 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 [Reference Kahle10, 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
Noting that for any $u\in V(G)$
and $r\in \mathbb {N}$
,
we have
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
The following lemma gives a useful upper bounds of the probability that a binomial distributed random variable is larger than expected.
Lemma 4.9 [Reference Penrose13, 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
for sufficiently large $n$
. Therefore, for sufficiently large $n$
and any $x\in V_n$
, we obtain
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
On the other hand, since $\operatorname {rk}(\operatorname {MH}_{\ell,\ell }(G_{n,p}))\ge 2\#E(G_{n,p})$
, we have
Combining these estimates, we obtain
Therefore, using the triangle inequality,
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
from Markov's inequality, which implies that
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
which implies the first conclusion. Again from Markov's inequality, the above equation also implies the second conclusion.
Acknowledgements
The first author was supported by RIKEN Center for Advanced Intelligence Project (AIP). The second author was supported by JST CREST Mathematics (15656429), JSPS Grant-in-Aid for Scientific Research (A) (20221963) and JSPS Grant-in-Aid for Challenging Research (Exploratory) (19091210), and JSPS Grant-in-Aid for Transformative Research Areas (A) (22A201). The third author was supported by JSPS KAKENHI Grant Number 19J11237.
