# Induced matching, ordered matching and Castelnuovo-Mumford regularity of
bipartite graphs

A. V. Jayanthan  Department of Mathematics, I.I.T. Madras, Chennai, INDIA -
600036<EMAIL_ADDRESS>,  Seyed Amin Seyed Fakhari  Departamento de
Matemáticas, Universidad de los Andes, Bogotá, Colombia.
<EMAIL_ADDRESS>,  Irena Swanson  and  Siamak Yassemi
Department of Mathematics, Purdue University, West Lafayette, IN, USA.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Let $G$ be a finite simple graph and let $\operatorname{ind-match}(G)$ and
$\operatorname{ord-match}(G)$ denote the induced matching number and the
ordered matching number of $G$, respectively. We characterize all bipartite
graphs $G$ with $\operatorname{ind-match}(G)=\operatorname{ord-match}(G)$. We
establish the Castelnuovo-Mumford regularity of powers of edge ideals and
depth of powers of cover ideals for such graphs. We also give formulas for the
count of connected non-isomorphic spanning subgraphs of $K_{m,n}$ for which
$\operatorname{ind-match}(G)=\operatorname{ord-match}(G)=2$, with an explicit
expression for the count when $m\in\\{2,3,4\\}$ and $m\leq n$.

###### Key words and phrases:

Induced matching, ordered matching, Castelnuovo-Mumford regularity, depth,
edge ideal, cover ideal

##  1\. Introduction

Let $G$ be a finite simple graph on the vertex set
$V(G)=\\{x_{1},\ldots,x_{d}\\}$ and edge set $E(G)$. We identify the vertices
to variables and consider the polynomial ring $S=K[x_{1},\ldots,x_{d}]$, where
$K$ is a field. The edge ideal of $G$ is defined as
$I(G)=\langle\\{x_{i}x_{j}~{}:~{}x_{i}x_{j}\in E(G)\\}\rangle\subset S$. Ever
since the introduction of the edge ideal by Villarreal in [23], researchers
have been trying to understand the interplay between the combinatorial
properties of graphs and the algebraic properties of the associated edge
ideals. One particular invariant, the Castelnuovo-Mumford regularity, has
received much of the attention, compared to other invariants and properties.
Several upper and lower bounds for the regularity of edge ideals were obtained
by several researchers, see [1] and references therein. Whenever there is an
upper and a lower bound for an invariant, it is natural to ask what are some
necessary conditions and sufficient conditions for these two bounds to
coincide, and structurally understand those objects for which these two bounds
are equal. In this article, we address this question for the upper bound of
ordered matching number and the lower bound of induced matching number.

Computing or bounding the Castelnuovo-Mumford regularity of the associated
edge ideal and its powers, in terms of combinatorial data associated with $G$,
has been a very active area of research for the past couple of decades. Bounds
using several matching numbers have been obtained for the regularity. For
graph $G$, let $\operatorname{ind-match}(G),\operatorname{ord-
match}(G),\operatorname{min-match}(G)$ and $\operatorname{match}(G)$ denote
induced matching number, ordered matching number, minimum matching number and
matching number, respectively (see Section 2 for the definitions).

It is known that

$\operatorname{ind-
match}(G)\leq\operatorname{reg}(S/I(G))\leq\\{\operatorname{ord-
match}(G),\operatorname{min-match}(G)\\}\leq\operatorname{match}(G),$

where the first inequality was proved by Katzman, [15], the second inequality
can be found in [24] (for $\operatorname{min-match}(G)$) and [5] (for
$\operatorname{ord-match}(G))$ and the third inequality follows from the
definition. A graph $G$ is said to be a Cameron-Walker graph if
$\operatorname{ind-match}(G)=\operatorname{match}(G)$. This is a class of
graphs which is well studied from both combinatorial and algebraic
perspectives, [4, 11, 13]. In [12], Hibi et al. studied graphs with
$\operatorname{ind-match}(G)=\operatorname{min-match}(G)$. They gave a
structural characterization of graphs satisfying $\operatorname{ind-
match}(G)=\operatorname{min-match}(G)$. In this article, we study graphs
satisfying $\operatorname{ind-match}(G)=\operatorname{ord-match}(G)$.

Besides the combinatorial reasons for understanding graphs $G$ with
$\operatorname{ind-match}(G)=\operatorname{ord-match}(G)$, there is also an
algebraic motivation to understand graphs with this property. It was proved by
Cutkosky, Herzog and Trung, [6], and independently by Kodiyalam, [16], that
for a homogeneous ideal $I$ in a polynomial ring, $\operatorname{reg}(I^{s})$
is a linear polynomial for $s\gg 0$. In the case of edge ideals, there have
been extensive research in understanding this function and the polynomial in
terms of combinatorial data associated with $G$, (see for example [1] and the
references within). It was shown in [2, Theorem 4.5] and [20, Theorem 3.9]
that for every integer $s\geq 1$,

$2s+\operatorname{ind-match}(G)-2\leq\operatorname{reg}(S/I(G)^{s})\leq
2s+\operatorname{ord-match}(G)-2.$

If $\operatorname{ind-match}(G)=\operatorname{ord-match}(G)$, then this gives
an explicit expression for the regularity of powers of the edge ideal.

Classifying all graphs $G$ with $\operatorname{ind-
match}(G)=\operatorname{ord-match}(G)$ would be an extremely hard problem in
general, and in this paper we concentrate on classifying bipartite graphs
satisfying this property. Another important reason for restricting our
attention to the bipartite case is the behavior of the depth function of the
cover ideal, see the end of Section 2.

For smaller values of induced and ordered matching, it is easier to handle the
corresponding bipartite graphs. First we give graph theoretic characterization
for graphs $G$ with $\operatorname{ind-match}(G)=\operatorname{ord-
match}(G)=1$ (Theorem 3.4). We then move on to understand the structure of
graphs in terms of the connectivity between the bipartitions. This gives us a
classification of all bipartite graphs $G$ with $\operatorname{ind-
match}(G)=\operatorname{ord-match}(G)$, (Theorem 3.8). To illustrate that this
class of graphs is very different from the class of graphs $G$ with
$\operatorname{ind-match}(G)=\operatorname{min-match}(G)$, we construct a
class of graphs, $G_{r,m}$, $2\leq r\leq m$, with
$\operatorname{reg}(S/I(G_{r,m}))=\operatorname{ind-
match}(G)=\operatorname{ord-match}(G)=r$ and $\operatorname{min-match}(G)=m$.

Our characterization of bipartite graphs with equal induced and ordered
matching numbers allows us to count the number of graphs $G$ satisfying
$\operatorname{ind-match}(G)=\operatorname{ord-match}(G)\leq 2$, see Theorem
3.4 and Theorem 5.4. The work for $\operatorname{ind-
match}(G)=\operatorname{ord-match}(G)=2$ leads us to some interesting
connections between the presence of edges and certain number of integer
sequences.

The paper is organized as follows. We collect some graph theory essentials in
Section 2. Characterizing the equality of induced and ordered matching numbers
is done in Section 3. In Section 4, we introduce some preliminaries to count
the bipartite graphs with $\operatorname{ind-match}(G)=2=\operatorname{ord-
match}(G)$, namely we set up the notation for certain integer sequences and
their counting. We count all graphs with $\operatorname{ind-
match}(G)=2=\operatorname{ord-match}(G)$ in Section 5. We provide the closed
forms for certain elementary summations to count these graphs in Section 6 as
an appendix.

##  2\. Preliminaries

In this section, we provide the definitions and basic facts which will be used
in the next sections.

Let $S=K[x_{1},\dots,x_{n}]$ be the polynomial ring over a field $K$ and let
$M$ be a finitely generated graded $S$-module. Suppose that the minimal graded
free resolution of $M$ is given by

$0\rightarrow\cdots\rightarrow\bigoplus_{j}S(-j)^{\beta_{1,j}(M)}\rightarrow\bigoplus_{j}S(-j)^{\beta_{0,j}(M)}\rightarrow
M\rightarrow 0.$

The Castelnuovo-Mumford regularity (or simply, regularity) of $M$, denoted by
${\rm reg}(M)$, is defined as

${\rm reg}(M)={\rm max}\\{j-i\mid\beta_{i,j}(M)\neq 0\\}.$

Also, the projective dimension of $M$ is defined to be

${\rm pd}(M)={\rm max}\\{i\mid\beta_{i,j}(M)\neq 0\ {\rm for\ some\ }j\\}.$

For a vertex $x_{i}\in V(G)$, the neighbor set of $x_{i}$ is defined to be the
set $N_{G}(x_{i})=\big{\\{}x_{j}\mid x_{i}x_{j}\in E(G)\big{\\}}$. Moreover,
the closed neighborhood of $x_{i}$ is
$N_{G}[x_{i}]=N_{G}(x_{i})\cup\\{x_{i}\\}$. The cardinality of $N_{G}(x_{i})$
is the degree of $x_{i}$ and is denoted by ${\rm deg}_{G}(x_{i})$. A vertex of
degree one is called a leaf of $G$. The graph $G$ is a forest if it does not
have any cycle. The distance between $x_{i}$ and $x_{j}$ in $G$ is defined to
be the length of the shortest path between $x_{i}$ and $x_{j}$ in $G$. For a
subset $W\subset V(G)$, $G\setminus W$ denotes the induced subgraph of $G$ on
the vertex set $V(G)\setminus W$. A subset $A$ of $V(G)$ is said to be an
independent subset of $G$ if there are no edges among the vertices of $A$. The
graph $G$ is called unmixed (or well-covered) if all maximal independent sets
of $G$ have the same cardinality.

A matching in a graph is a subgraph consisting of pairwise disjoint edges. The
cardinality of the largest matching in $G$ is the matching number of $G$ and
is denoted by $\operatorname{match}(G)$. A matching in $G$ is said to be a
maximal matching if it is not properly contained in any matching of $G$. The
minimum matching number of $G$, denoted by $\operatorname{min-match}(G)$, is
the minimum cardinality of a maximal matching in $G$. A matching is said to be
an induced matching if none the edges in the matching are joined by an edge in
$G$. The largest size of an induced matching in $G$ is called the induced
matching number of $G$, denoted by $\operatorname{ind-match}(G)$. A graph $G$
is called a Cameron-Walker graph if $\operatorname{ind-
match}(G)=\operatorname{match}(G)$.

A set $A=\\{x_{i1}x_{i2}\in E(G)\mid 1\leq i\leq r\\}$ is said to be an
ordered matching, [5], if

  1. (1)

$A$ is a matching in $G$,

  2. (2)

$\\{x_{i1}\mid 1\leq i\leq r\\}$ is an independent set,

  3. (3)

if $x_{i1},x_{j2}\in E(G)$, then $i\leq j$.

The ordered matching number of $G$, denoted by $\operatorname{ord-match}(G)$,
is defined to be

$\operatorname{ord-match}(G):=\max\\{|A|:~{}A\text{ is an ordered matching of
}G\\}.$

As already written in the introduction,

$\operatorname{ind-
match}(G)\leq\operatorname{reg}(S/I(G))\leq\\{\operatorname{ord-
match}(G),\operatorname{min-match}(G)\\}\leq\operatorname{match}(G),$

There are several examples with inequality $\operatorname{min-
match}(G)\leq\operatorname{ord-match}(G)$ and other examples with inequality
$\operatorname{ord-match}(G)\leq\operatorname{min-match}(G)$.

A graph $G$ is said to be Cohen-Macaulay (resp. sequentially Cohen-Macaulay)
if $S/I(G)$ is Cohen-Macaulay (resp. sequentially Cohen-Macaulay).

A bipartite graph $G$ is a graph with $V(G)=X\sqcup Y$ and $E(G)\subset
X\times Y$. If $|X|=m$ and $|Y|=n$ and $E(G)=X\times Y$, then we say that $G$
is a complete bipartite graph, and we denote $G$ by $K_{m,n}$. If $G$ is a
bipartite graph, then $G^{bc}$, called the bipartite complement, is the
bipartite graph with $V(G^{bc})=V(G)=X\sqcup Y$ and $xy\in E(G^{bc})$ if and
only if $xy\notin E(G)$. A subgraph $H$ of a graph $G$ is said to be a
spanning subgraph if $V(H)=V(G).$ If $G=K_{m,n}$, then the set of connected
spanning subgraphs of $G$ is precisely the set of all connected bipartite
graphs on $X\sqcup Y$, where $|X|=m$ and $|Y|=n$.

For the rest of the article, $G$ always denotes a bipartite graph, without
isolated vertices, on the finite vertex set $V(G)=X\sqcup Y$.

It was proved by Brodmann [3] that for any homogeneous ideal $I$ in a graded
ring $R$, $0pt(R/I^{k})$ is a constant for $k\gg 0$. One consequence of ind-
match and ord-match being equal is the constancy from the start of the depth
function of powers of the cover ideal $J(G)=\bigcap_{x_{i}x_{j}\in
E(G)}(x_{i},x_{j})$ of $G$, as we prove next.

######  Theorem 2.1.

Assume that $G$ is a bipartite graph with $\operatorname{ind-
match}(G)=\operatorname{ord-match}(G)$ and suppose $d=|V(G)|$. Let $J(G)$
denote the cover ideal of $G$. Then for every integer $k\geq 1$, we have

${\rm depth}(S/J(G)^{k})=d-\operatorname{ind-match}(G)-1.$

###### Proof.

Since ${\rm reg}(I(G))=\operatorname{ind-match}(G)+1$ by inequalities in the
Introduction, it follows from Terai’s theorem [10, Proposition 8.1.10] that
the projective dimension of $S/J(G)$ is equal to $\operatorname{ind-
match}(G)+1$. Thus, Auslander-Buchsbaum formula implies that ${\rm
depth}(S/J(G))=d-\operatorname{ind-match}(G)-1$. On the other hand, it follows
from [8, Corollary 2.6] and [14, Theorem 3.2] that

$d-\operatorname{ind-match}(G)-1={\rm depth}(S/J(G))\geq{\rm
depth}(S/J(G)^{2})\geq{\rm depth}(S/J(G)^{3})\geq\cdots.$

Moreover, we know from [14, Theorem 3.4] (see also [19, Theorem 3.1]) that
${\rm depth}(S/J(G)^{k})=d-\operatorname{ord-match}(G)-1$ for any $k\gg 0$.
Since $\operatorname{ord-match}(G)=\operatorname{ind-match}(G)$, the assertion
follows from the above inequalities.

##  3\. Equality of induced and ordered matching numbers

In this section, we characterize all bipartite graphs $G$ with
$\operatorname{ord-match}(G)=\operatorname{ind-match}(G)$. Before proving our
general characterization (Theorem 3.8), we restrict ourselves to a special
family of bipartite graphs for which the characterization has simpler
formulation comparing with the general case. More precisely, we consider the
class of sequentially Cohen-Macaulay bipartite graphs $G$. In [7, 21, 22], the
authors studied the sequential Cohen-Macaulayness of $S/I(G)$ in terms of the
combinatorial properties of $G$. Here, we study it in terms of the matching
numbers. In the following theorem, we show that for a bipartite sequentially
Cohen-Macaulay graph $G$, the equality $\operatorname{ord-
match}(G)=\operatorname{match}(G)$ holds. As a consequence of this equality,
we are able to characterize sequentially Cohen-Macaulay bipartite graphs $G$
with $\operatorname{ord-match}(G)=\operatorname{ind-match}(G)$.

######  Theorem 3.1.

Let $G$ be a bipartite graph. If $G$ is sequentially Cohen-Macaulay, then
$\operatorname{ord-match}(G)={\rm match}(G)$. In particular, for a
sequentially Cohen-Macaulay bipartite graph $G$, we have $\operatorname{ind-
match}(G)=\operatorname{ord-match}(G)$ if and only if $G$ is a Cameron-Walker
graph.

###### Proof.

We prove the equality $\operatorname{ord-match}(G)={\rm match}(G)$ by
induction on $|V(G)|$. If $|V(G)|=2$, then $\operatorname{ord-
match}(G)=\operatorname{match}(G)=1$. Assume by induction that if $H$ is a
sequentially Cohen-Macaulay bipartite graph with $|V(H)|<|V(G)|$, then
$\operatorname{ord-match}(H)=\operatorname{match}(H)$. By [22, Corollary
3.11], there is a leaf $x\in V(G)$ such that $G\setminus N_{G}[x]$ is
sequentially Cohen-Macaulay. Using [18, Lemma 2.1] and the induction
hypothesis we have

$\operatorname{ord-match}(G)\geq\operatorname{ord-match}(G\setminus
N_{G}[x])+1={\rm match}(G\setminus N_{G}[x])+1={\rm match}(G)$

where the last equality follows from the fact that $x$ is a leaf of $G$. Thus,
$\operatorname{ord-match}(G)={\rm match}(G)$. The second assertion follows by
observing that $G$ is Cameron-Walker if and only if $\operatorname{ind-
match}(G)=\operatorname{match}(G)$.

The converse of the above Theorem does not hold. In fact, the following
example shows that for each integer $k\geq 3$, there is a non-sequentially
Cohen-Macaulay bipartite graph $G$ with ${\rm match}(G)=\operatorname{ord-
match}(G)=k$.

######  Example 3.2.

For any integer $k\geq 3$, let $G_{k}$ be the graph obtained from a $4$-cycle
graph by attaching a path of length $2k-3$ to exactly one of its vertices.
Using induction on $k$, We show that $G_{k}$ is not sequentially Cohen-
Macaulay and $\operatorname{ord-match}(G_{k})={\rm match}(G_{k})=k$. It is
easy to see that $\operatorname{ord-match}(G_{3})={\rm match}(G_{3})=3$.
Moreover, let $x$ be the unique leaf of $G_{3}$ and let $y$ be the unique
neighbor of $x$. Then $G_{3}\setminus N_{G_{3}}[y]$ is the $4$-cycle graph
that is not sequentially Cohen-Macaulay. Hence, by [22, Corollary 3.11], the
graph $G_{3}$ is not sequentially Cohen-Macaulay. Now, suppose that $k\geq 4$.
Let $z$ be the be the unique leaf of $G_{k}$. Then $G_{k}\setminus
N_{G_{k}}[z]$ is isomorphic to $G_{k-1}$ that is not sequentially Cohen-
Macaulay by induction hypothesis. Moreover, since $z$ is a leaf of $G_{k}$, we
have ${\rm match}(G_{k})={\rm match}(G_{k_{1}})+1=k$. On the other hand, using
[18, Lemma 2.1] and the induction hypothesis, we have

$\operatorname{ord-match}(G_{k})\geq\operatorname{ord-match}(G_{k-1})+1=k.$

Thus, $\operatorname{ord-match}(G_{k})=k$.

In Example 3.2, we showed that for each integer $k\geq 3$, there is a non-
sequentially Cohen-Macaulay bipartite graph $G$ with ${\rm
match}(G)=\operatorname{ord-match}(G)=k$. The following proposition shows that
we cannot expect such an example when $k\leq 2$.

######  Proposition 3.3.

Let $G$ be a bipartite graph with ${\rm match}(G)=\operatorname{ord-
match}(G)\leq 2$. Then $G$ is a sequentially Cohen-Macaulay graph.

###### Proof.

By contradiction, suppose $G$ is not sequentially Cohen-Macaulay. It is known
that any forest is sequentially Cohen-Macaulay (see for instance, [22, Theorem
1.3]). As a consequence, $G$ is not a forest and therefore, has a cycle $C$.
Since ${\rm match}(G)\leq 2$, the length of $C$ is equal to four. Suppose
$V(C)=\\{w,x,y,z\\}$ and $E(C)=\\{wx,xy,yz,wz\\}$. Since ${\rm match}(C)=2$
and $\operatorname{ord-match}(C)=1$, we conclude that $G\neq C$. This implies
that there is an edge say $wv$ connected to $C$, where $v$ is a vertex in
$V(G)\setminus V(C)$. As $G$ is a bipartite graph, $v$ is not adjacent to the
vertices $x$ and $z$. If there is a vertex $u\in V(G)\setminus V(C)$ such that
$ux\in E(G)$ or $uz\in E(G)$, then the matching number of $G$ would be at
least three, which is a contradiction. Thus, $\deg_{G}(x)=\deg_{G}(z)=2$. If
$G$ has a vertex $t\in V(G)\setminus V(C)$ whose distance from $w$ or $y$ is
at least two, then again, the matching number of $G$ would be at least three,
which is a contradiction. Hence, $V(G)=N_{G}[w]\cup N_{G}[y]$. Since $G$ is a
bipartite graph two distinct vertices belonging to $N_{G}(w)\cup N_{G}(y)$ can
not be adjacent. Hence, $V(G)=\\{w,y\\}\sqcup(V(G)\setminus\\{w,y\\})$ is the
bipartition for the vertex set of $G$. Consequently, $G$ is a subgraph of
$K_{2,m}$, for some integer $m\geq 3$. If $G=K_{2,m}$, then
$\operatorname{ord-match}(G)=1$, which is a contradiction. Thus, $G\neq
K_{2,m}$. So, $G$ has a leaf, say $s$. Then the unique neighbor of $s$ is
either $w$ or $y$. Without loss of generality, we may assume that $ws\in
E(G)$. Then the graphs $G\setminus N_{G}[w]$ and $G\setminus N_{G}[s]$ are
forests (as they do not contain the vertex $w$ and so, the cycle $C$).
Therefore, using [22, Theorem 1.3], the graphs $G\setminus N_{G}[w]$ and
$G\setminus N_{G}[s]$ are sequentially Cohen-Macaulay. Hence, [22, Corollary
3.11] implies that $G$ is a sequentially Cohen-Macaulay graph, which is a
contradiction.

In the following result, we give a characterization of bipartite graphs with
$\operatorname{ord-match}(G)=\operatorname{ind-match}(G)=1$. A classification
of bipartite graphs with ord-match and ind-match being equal to an arbitrary
positive integer strictly bigger than 1 is in Theorem 3.8.

######  Theorem 3.4.

Let $G$ be a bipartite graph. Then $\operatorname{ord-
match}(G)=\operatorname{ind-match}(G)=1$ if and only if $G$ is a complete
bipartite graph.

###### Proof.

If $G=K_{m,n}$ for some $m,n\geq 1$, then clearly $\operatorname{ind-
match}(G)=1=\operatorname{ord-match}(G)$. Conversely suppose $G$ is not a
complete bipartite graph. Write
$V(G)=\\{x_{1},\ldots,x_{m}\\}\sqcup\\{y_{1},\ldots,y_{n}\\}$. Since $G$ is
not complete bipartite, there exist $i,j$ such that $x_{i}y_{j}\notin E(G)$.
By permuting the vertices, we may assume that $x_{j}y_{j}\in E(G)$. Choose an
$r$ such that $x_{i}y_{r}\in E(G)$. Then $\\{x_{j}y_{j},x_{i},y_{r}\\}$ is an
ordered matching in $G$. Hence $\operatorname{ord-match}(G)>1$.

######  Definition 3.5.

For every subset $I$ of $X$, let $C_{I}$ be the set of all vertices in $Y$
that have an edge to all the vertices in $I$ and to none in $X\setminus I$.
Set $c_{I}=|C_{I}|$.

Sometimes we shorten the notation and write in the subscripts not the set but
its elements, without commas. For example, we abbreviate $c_{\\{i,j\\}}$ to
$c_{ij}$. If $I,J$ are distinct subsets of $X$, then $C_{I}$ and $C_{J}$ are
disjoint. In fact, each $y\in Y$ belongs to exactly one of $C_{I}$. Since $G$
does not have isolated vertices, we have $C_{\emptyset}=\emptyset$.

In order to characterize bipartite graphs $G$ with $\operatorname{ind-
match}(G)=\operatorname{ord-match}(G)$, we need the following two
propositions.

######  Proposition 3.6.

Let $G$ be a bipartite graph and let $r$ be a positive integer. Then the
induced matching number of $G$ is at least $r$ if and only if there exist
subsets $J_{1},J_{2},\ldots,J_{r}$ of $X$ such that none of the $J_{i}$ is
contained in the union of the others and such that $c_{J_{1}}c_{J_{2}}\cdots
c_{J_{r}}>0$.

###### Proof.

Suppose that $\operatorname{ind-match}(G)$ is at least $r$. Then there exist
$a_{1},\ldots,a_{r}\in X$ and $b_{1},\ldots,b_{r}\in Y$ such that
$a_{1}b_{1},a_{2}b_{2},\ldots,a_{r}b_{r}$ is an induced matching. For each
$i\in[r]$, let $K_{i}$ be the subset of $Y$ consisting of all vertices with an
edge to $a_{i}$ and with no edge to any of the other $a_{j}$ with $j\not=i$.
So $b_{i}\in K_{i}$ and $K_{i}$ is not empty. Let $J_{i}$ be the set of all
vertices in $X$ with an edge to all elements of $K_{i}$. Then $a_{i}\in J_{i}$
and $a_{j}\not\in J_{i}$ for all $j\not=i$. The conclusion follows for these
$J_{1},\ldots,J_{r}$.

Conversely, suppose that there exist subsets $J_{1},J_{2},\ldots,J_{r}$ of $X$
such that none is contained in the union of the others and such that
$c_{J_{1}}c_{J_{2}}\cdots c_{J_{r}}>0$. For each $i\in r$, let $a_{i}\in
J_{i}$ that is not in the union of the other $J_{j}$. Since $c_{J_{i}}>0$,
there exists $b_{i}\in C_{J_{i}}$. Then by the definition of these sets,
$a_{1}b_{1},a_{2}b_{2},\ldots,a_{r}b_{r}$ is an induced matching, so that
$\operatorname{ind-match}(G)$ is at least $r$.

######  Proposition 3.7.

Let $G$ be a bipartite graph and let $r$ be a positive integer. Then the
following are equivalent:

  1. (1)

$\operatorname{ord-match}(G)\geq r$.

  2. (2)

There exist subsets $J_{1},J_{2},\ldots,J_{r}$ of $X$ such that
$c_{J_{1}}c_{J_{2}}\cdots c_{J_{r}}>0$ and for all $i\in[r-1]$, $J_{i}$ is not
contained in $J_{1}\cup\cdots\cup J_{i-1}$.

Moreover, $\operatorname{ord-match}(G)\leq r$ if and only if for all possible
sets $J_{1},\ldots,J_{r}$ with the properties as in (2), their union equals
$X$.

###### Proof.

(1) $\Rightarrow$ (2): Suppose that $\operatorname{ord-match}(G)$ is at least
$r$. Then there exist $a_{1},\ldots,a_{r}\in X$ and $b_{1},\ldots,b_{r}\in Y$
such that $a_{1}b_{1},a_{2}b_{2},\ldots,a_{r}b_{r}$ is an ordered matching.
For each $i\in[r]$, let $K_{i}$ be the subset of $Y$ consisting of all the
vertices with an edge to $a_{i}$ and with no edge to any of the $a_{j}$ with
$j>i$. So $b_{i}\in K_{i}$ and $K_{i}$ is not empty. Let $J_{i}$ be the set of
all the vertices in $X$ with an edge to all the elements of $K_{i}$. Then
$a_{i}\in J_{i}$ and $a_{j}\not\in J_{i}$ for all $j>i$. Thus (2) follows for
these $J_{1},\ldots,J_{r}$.

(2) $\Rightarrow$ (1): This is trivial for $r=1$, so we may assume that $r>1$.
Let $J_{1},J_{2},\ldots,J_{r}$ be subsets of $X$ such that for all
$i\in[r-1]$, $J_{i}$ is not contained in $J_{1}\cup\cdots\cup J_{i-1}$ and
such that $c_{J_{1}}c_{J_{2}}\cdots c_{J_{r}}>0$. For each $i\in r$, let
$a_{i}\in J_{i}\setminus J_{1}\cup\cdots\cup J_{i-1}$. Since $c_{J_{i}}>0$,
there exists $b_{i}\in C_{J_{i}}$. By definition of these sets,
$a_{1}b_{1},a_{2}b_{2},\ldots,a_{r}b_{r}$ is an ordered matching.

If there exists $a\in X\setminus J_{1}\cup\cdots\cup J_{r}$, then since $a$ is
not an isolated vertex, there is a vertex $b\in Y$ which is adjacent to $a$.
By definition of the sets $C_{I}$, there is no edge between $a$ and
$b_{1},\ldots,b_{r}$. Thus $a_{1}b_{1},a_{2}b_{2},\ldots,a_{r}b_{r},ab$ is an
ordered matching. Thus $\operatorname{ord-match}(G)$ is strictly bigger than
$r$.

If $\operatorname{ord-match}(G)$ is at least $r+1$, then by the equivalence of
(1) and (2) the union of $J_{1},\ldots,J_{r}$ cannot be $X$. This proves the
last part.

Using Propositions 3.6 and 3.7, we can classify all bipartite graphs for which
ord-match and ind-match are equal.

######  Theorem 3.8.

(Classification) Let $G$ be a bipartite graph and let $r>1$ be a positive
integer. Let $J_{1},\ldots,J_{z}$ be all the subsets $I$ of $X$ for which
$c_{I}$ is positive. Then $G$ has ind-match and ord-match equal to $r$ if and
only if the following conditions are satisfied:

  1. (1)

$z\geq r$.

  2. (2)

There exist distinct $j_{1},\ldots,j_{r}\in[z]$ such that none of the
$J_{j_{i}}$ is contained in the union of the remaining $J_{j_{k}}$.

  3. (3)

For all $j_{1},\ldots,j_{r}\in[z]$, if for each $i\in[r-1]$, $J_{j_{i}}$ is
not contained in $J_{j_{1}}\cup\cdots\cup J_{j_{i-1}}$, then
$J_{j_{1}}\cup\cdots\cup J_{j_{r}}=X$.

###### Proof.

First suppose that $\operatorname{ind-match}(G)$ and $\operatorname{ord-
match}(G)$ equal $r$. Then by Proposition 3.6, (1) and (2) hold. Proposition
3.7 implies (3).

Now suppose that the three conditions are satisfied. Then by Proposition 3.6,
induced matching number of $G$ is at least $r$ and $\operatorname{ord-
match}(G)$ is at most $r$. But $\operatorname{ord-match}(G)$ is greater than
or equal to $\operatorname{ind-match}(G)$. So, $\operatorname{ind-match}(G)$
and $\operatorname{ord-match}(G)$ are both equal to $r$.

We can say more in case $\operatorname{ord-match}(G)$ and $\operatorname{ind-
match}(G)$ are both equal to 2:

######  Theorem 3.9.

(Classification for r = 2) Let $G$ be a bipartite graph. Let
$J_{1},\ldots,J_{z}$ be all the subsets $I$ of $X$ for which $c_{I}$ is
positive. Then $G$ has ind-match and ord-match equal to $2$ if and only if the
following conditions are satisfied:

  1. (1)

$z\geq 2$.

  2. (2)

There exist distinct $i,j\in[z]$ such that neither $J_{i}$ nor $J_{j}$ is
contained in the other.

  3. (3)

For any two distinct $i,j\in[z]$, $J_{i}\cup J_{j}=X$.

Furthermore, if some $J_{i}$ and $J_{j}$ are disjoint, then $z$ equals $2$ or
$3$; the later exactly when the graph is connected and in this case $c_{X}>0$.

###### Proof.

Equivalence follows from Theorem 3.8. Note that part (3) here is equivalent to
part (3) in Theorem 3.8 because $J_{i}$ and $J_{j}$ are distinct sets.

Let $k\in[z]\setminus\\{i,j\\}$. Then by condition (3), $J_{k}$ contains the
complement of $J_{i}$ and $J_{j}$, so that if $J_{i}$ and $J_{j}$ are
disjoint, then $J_{k}$ contains $X$. This means that $J_{k}$ has to equal $X$.
Thus either $z=3$ and $G$ is connected, or else $z=2$ and $G$ is not
connected.  As a consequence of the above theorem, we obtain an explicit graph
theoretic characterization of bipartite graphs $G$ with $\operatorname{ind-
match}(G)=\operatorname{ord-match}(G)=2$.

######  Corollary 3.10.

Let $G$ be a bipartite graph. Then $\operatorname{ind-
match}(G)=\operatorname{ord-match}(G)=2$ if and only if the bipartite
complement $G^{bc}$ of $G$ is the disjoint union of complete bipartite graphs
$H_{1},\ldots,H_{s}$ with $s\geq 2$ such that at least two of the $H_{i}$ are
not isolated vertices.

###### Proof.

Let $J_{1},\ldots,J_{z}$ be all the subsets $I$ of $X$ for which $c_{I}$ is
positive. Then for any pair of distinct integers $i,j\in[z]$, we have
$J_{i}\cup J_{j}=X$ if and only if for any choice of vertices $y\in C_{J_{i}}$
and $y^{\prime}\in C_{J_{j}}$, the equality $N_{G^{bc}}(y)\cap
N_{G^{bc}}(y^{\prime})=\emptyset$ holds. Thus, Condition (3) of Theorem 3.9
(and in fact, by Proposition 3.7, the inequality $\operatorname{ord-
match}(G)\leq 2$) is equivalent to say that $G^{bc}$ is the disjoint union of
complete bipartite graphs. Moreover, note that $\operatorname{ind-
match}(G)\geq 2$ if and only if $\operatorname{ind-match}(G^{bc})\geq 2$.
Since $G^{bc}$ is the disjoint union of complete bipartite graphs, we deduce
at least two of these components are not isolated vertices.

Let $G$ be a bipartite graph. It is known that if $G$ is either unmixed or
sequentially Cohen-Macaulay, then ${\rm reg}(S/I(G))=\operatorname{ind-
match}(G)$. In the following theorem, for every pair of integers $r,m$ with
$2\leq r\leq m$, we construct a bipartite graph $G_{r,m}$ which is neither
sequentially Cohen-Macaulay nor unmixed, moreover, ${\rm
reg}(S/I(G_{r,m}))=\operatorname{ind-match}(G_{r,m})=\operatorname{ord-
match}(G_{r,m})=r$ and $\operatorname{min-match}(G_{r,m})=m$. Hence, the class
of graphs we study in this paper is not contained in two general classes of
bipartite graphs for which the regularity of edge ideals is known.
Furthermore, Theorem 3.11 shows that the family of graphs $G$ with
$\operatorname{ind-match}(G)=\operatorname{ord-match}(G)$ is far from the
class of graphs considered in [12].

######  Theorem 3.11.

Let $2\leq r\leq m$ be positive integers. Then there is a connected bipartite
graph $G_{r,m}$ such that

  1. (1)

${\rm reg}(S/I(G_{r,m}))=\operatorname{ind-match}(G_{r,m})=\operatorname{ord-
match}(G_{r,m})=r$ and $\operatorname{min-match}(G_{r,m})=m$.

  2. (2)

$G_{r,m}$ does not have any leaf (and hence $G_{r,m}$ is not a sequentially
Cohen-Macaulay graph).

  3. (3)

$G_{r,m}$ is not an unmixed graph.

###### Proof.

Set $X=\\{x_{1},\ldots,x_{m+1}\\}$ and $Y=\\{y_{1},\ldots,y_{m+1}\\}$. Let
$G_{r,m}$ be the bipartite graph with vertex set $V(G_{r,m})=X\sqcup Y$ and
edge set

$E(G_{r,m})=\bigcup_{1\leq j\leq
r-1}\\{x_{1}y_{j},x_{j+1}y_{j}\\}\cup\bigcup_{r\leq j\leq
m}\\{x_{1}y_{j},x_{i}y_{j}\mid r+1\leq i\leq m+1\\}\cup\\{x_{i}y_{m+1}\mid
1\leq i\leq m+1\\}.$

For the convenience of the reader, we illustrate the graph $G_{r,m}$ with a
sample picture below:

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$y_{5}$ Figure
1. $G_{2,4}$

It follows directly from the definition that

$N_{G_{r,m}}(y_{j})=\left\\{\begin{array}[]{ll}\\{x_{1},x_{j+1}\\},&\quad
1\leq j\leq r-1;\\\ \\{x_{r+1},\ldots,x_{m+1}\\}\cup\\{x_{1}\\},&\quad r\leq
j\leq m;\\\ X,&\quad j=m+1.\end{array}\right.$

Clearly, $G_{r,m}$ is a connected bipartite graph that does not have any leaf.
Therefore using [22, Corollary 2.10], it is not a sequentially Cohen-Macaulay
graph. Moreover, it is easy to check that the set
$\\{x_{2},\ldots,x_{r},y_{r},\ldots,y_{m}\\}$ is a maximal independent set of
$G_{r,m}$ with cardinality $m<|X|$. Thus, $G_{r,m}$ is not an unmixed graph.
Hence, we only need to verify condition (i).

Set

$J_{1}=N_{G_{r,m}}(y_{1}),J_{2}=N_{G_{r,m}}(y_{2}),\cdots,J_{r}=N_{G_{r,m}}(y_{r}),J_{r+1}=X.$

Note that for a subset $J\subseteq X$, we have $c_{J}>0$ if and only if
$J\in\\{J_{1},\ldots,J_{r+1}\\}$. Then it follows from Theorem 3.8 that

${\rm reg}(S/I(G_{r,m}))=\operatorname{ind-match}(G_{r,m})=\operatorname{ord-
match}(G_{r,m})=r.$

Now, we compute $\operatorname{min-match}(G_{r,m})$. It is obvious that

$\\{y_{2}x_{3},y_{3}x_{4},\ldots,y_{m-1}x_{m},y_{m}x_{1},y_{m+1}x_{2}\\}$

is a maximal matching in $G_{r,m}$ of size $m$. Hence, $\operatorname{min-
match}(G_{r,m})\leq m$. Suppose $M$ is a maximal matching in $G_{r,m}$ with
$|M|\leq m-1$. Thus, there are two distinct vertices $y_{i},y_{j}\in
Y\setminus V(M)$. Without loss of generality, we may assume that $i<j$. We
consider the following cases.

Case 1. Suppose $i,j\leq r-1$, then at least one of the vertices $x_{i+1}$ and
$x_{j+1}$ does not belong to $V(M)$, as otherwise the edges $y_{m+1}x_{i+1}$
and $y_{m+1}x_{j+1}$ belong to $M$, which contradicts the definition of a
matching. For example, suppose $x_{i+1}\notin V(M)$. Then
$M\cup\\{y_{i}x_{i+1}\\}$ is a matching in $G_{r,m}$. Thus, $M$ is not a
maximal matching.

Case 2. Suppose $1\leq i\leq r-1$ and $r\leq j\leq m$. Since $M$ is a maximal
matching in $G_{r,m}$, we deduce that $N_{G_{r,m}}(y_{i})\cup
N_{G_{r,m}}(y_{j})\subseteq V(M)$. This implies that

$\\{x_{1},x_{i+1},x_{r+1},\ldots,x_{m+1}\\}\subseteq V(M).$

Since $x_{i+1}\in V(M)$ and $y_{i}\notin V(M)$, the edge $y_{m+1}x_{i+1}$ must
belong to $M$. Then since $x_{r+1},\ldots,x_{m+1}\in V(M)$, we conclude that
$y_{r},\ldots,y_{m}\in V(M)$. Moreover, according to Case 1, we may assume
that $\\{y_{1},\ldots,y_{r-1}\\}\setminus\\{y_{i}\\}\subseteq V(M)$.
Therefore, $Y\setminus\\{y_{i}\\}\subseteq V(M)$. So, $|M|\geq m$, which is a
contradiction.

Case 3. Suppose $r\leq i,j\leq m$. Since $M$ is a maximal matching, we must
have $N_{G_{r,m}}(y_{i})\cup N_{G_{r,m}}(y_{j})\subseteq V(M)$. In particular,
$\\{x_{r+1},\ldots,x_{m+1}\\}\subseteq V(M)$. So, in $G_{r,m}$, there are at
least $m-r+1$ vertices other that $y_{i}$ and $y_{j}$, which are adjacent to
at least one of the vertices $x_{r+1},\ldots,x_{m+1}$. But this is not the
case according to the construction of $G_{r,m}$.

Case 4. Suppose $j=m+1$. Since $M$ is a maximal matching,
$N_{G_{r,m}}(y_{j})\subseteq V(M)$. Therefore, $X\subseteq V(M)$. This implies
that $|M|\geq m+1$, which is a contradiction.

##  4\. Set-up of $k$-sequences and $J$-sets

The notation in this section sets the stage for the counting of graphs in the
next section.

######  Definition 4.1.

A $\bf k$-sequence is a strictly decreasing sequence of integers
$\\{k_{0},k_{1},\ldots,k_{z}$} with $z\geq 2$, $k_{z}=0$, and for all
$l=2,3,\ldots,z$, $k_{l+1}\geq 2k_{l}-k_{l-1}$.

Observe that if a $k$-sequence has at least four terms, then the truncation of
the sequence by removing the first term is also a $k$-sequence. A truncated
$k$-sequence is a truncation of infinitely many $k$-sequences.

######  Examples 4.2.

When $k_{0}=2$, the only possible $k$-sequence is $\\{2,1,0\\}$.

The only possible $k$-sequences with $k_{0}=3$ are $\\{3,2,1,0\\}$ and
$\\{3,1,0\\}$.

When $k_{0}=4$, there are four $k$-sequences: $\\{4,3,2,1,0\\}$;
$\\{4,2,1,0\\}$; $\\{4,2,0\\}$ and $\\{4,1,0\\}$.

When $k_{0}=5$, there are six $k$-sequences: $\\{5,4,3,2,1,0\\}$;
$\\{5,3,2,1,0\\}$; $\\{5,3,1,0\\}$; $\\{5,2,1,0\\}$; $\\{5,2,0\\}$ and
$\\{5,1,0$}.

######  Definition 4.3.

For any non-negative integer $n$ and any $k$-sequence
$\\{k_{0},k_{1},\ldots,k_{z}\\}$ with $z\geq 3$, set

$D(n;\\{k_{0},\ldots,k_{z}\\})=\begin{cases}\displaystyle\sum_{i=1}^{n-1}\sum_{j=1}^{n-i}C(n-i,j;k_{1},\ldots,k_{z}),&\hbox{if
$k_{2}>2k_{1}-k_{0}$};\\\
\displaystyle\sum_{i=1}^{n-1}\sum_{j=1}^{\min\\{n-i,i\\}}C(n-i,j;k_{1},\ldots,k_{z}),&\hbox{if
$k_{2}=2k_{1}-k_{0}$},\\\ \end{cases}$

where $C$ is defined recursively as follows:

$C(n,i;k_{1},\ldots,k_{z})=\begin{cases}n-i+1,&\hbox{if $z=3$ and
$k_{3}>2k_{2}-k_{1}$};\\\ \min\\{n-i,i\\}+1,&\hbox{if $z=3$ and
$k_{3}=2k_{2}-k_{1}$};\\\
\displaystyle\sum_{j=0}^{n-i}C(n-i,j;k_{1},\ldots,k_{z}),&\hbox{if $z>3$ and
$k_{3}>2k_{2}-k_{1}$};\\\
\displaystyle\sum_{j=0}^{\min\\{n-i,i\\}}C(n-i,j;k_{1},\ldots,k_{z}),&\hbox{if
$z>3$ and $k_{3}=2k_{2}-k_{1}$}.\\\ \end{cases}$

Here is a full expansion of $D$:

$D(n;\\{k_{0},\ldots,k_{z}\\})=\sum_{i_{1}=1}^{n-1}\sum_{i_{2}=1}^{u_{2}}\sum_{i_{3}=0}^{u_{3}}\sum_{i_{4}=0}^{u_{4}}\ldots\sum_{i_{z}=0}^{u_{z}}1,$

where the upper bounds $u_{l}$ equal either $n-i_{1}-\cdots-i_{l-1}$ or
$\min\\{n-i_{1}-\cdots-i_{l-1},i_{l-1}\\}$, depending on whether strict
inequality or equality hold in $k_{l+1}\geq 2k_{l}-k_{l-1}$. The sum does not
depend on the specific values in the $k$-sequence, but only on whether
$k_{l+1}$ is strictly greater than or equal to $2k_{l}-k_{l-1}$. Note that the
counters $i_{1}$ and $i_{2}$ start with $1$, but all other counters $i_{l}$
start with $0$.

######  Definition 4.4.

Let $K$ be a finite set of $k$-sequences, each $k$-sequence in $K$ having at
least four terms (so $z\geq 3$ for each sequence in $K$). Let $W$ be the
ordered set from largest to smallest of all non-negative integers that appear
in all sequences in $K$. So $0\in W$. For any positive integer $l\leq|W|$ and
any $\underline{k}\in K$, let $o(l,\underline{k})$ be the subscript index of
the $l$th element of $W$ in $\underline{k}$. For any integer $n\geq 2$ we
define $D_{K}(n)$ to be $0$ if the first three terms in the sequences in $K$
are not the same, and otherwise $D_{K}(n)$ is the sum of the common summands
in the $D$-sums (from Definition 4.3) coming from the $W$-terms for all
sequences in $K$. Explicitly,

$D_{K}(n)=\sum_{i_{1}=1}^{n-1}\sum_{i_{2}=1}^{v_{2}}\sum_{i_{3}=0}^{v_{3}}\sum_{i_{4}=0}^{v_{4}}\ldots\sum_{i_{|W|}=0}^{v_{|W|}}1,$

where for $l=2,\ldots,|W|$, $v_{l}$ is the minimum of all the upper bounds in
$D(n;\underline{k})$ in the $o(l,\underline{k})$th summation as
$\underline{k}$ varies over all sequences in $K$. These upper bounds depend
also on the summation indices not appearing in $W$, and those hidden indices
are all set to their common hidden value $0$.

For example, $D_{K}(n)=0$ for the set $K$ consisting of two $k$-sequences
$\\{6,3,2,1,0\\}$ and $\\{6,3,1,0\\}$ because their third terms are not the
same.

For a more interesting example, let $K$ consist of
$\underline{k}=\\{6,4,2,1,0\\}$ and $\underline{l}=\\{6,4,2,0\\}$. Then
$W=\\{6,4,2,0\\}$, $o(6,\underline{k})=o(6,\underline{l})=0$,
$o(4,\underline{k})=o(4,\underline{l})=1$,
$o(2,\underline{k})=o(2,\underline{l})=2$, $o(0,\underline{k})=4$,
$o(0,\underline{l})=3$. We write out explicitly

$D(n;\\{6,4,2,1,0\\})=\sum_{i_{1}=1}^{n-1}\sum_{i_{2}=1}^{\min\\{n-i_{1},i_{1}\\}}\sum_{i_{3}=0}^{n-i_{1}-i_{2}}\sum_{i_{4}=0}^{\min\\{n-i_{1}-i_{2}-i_{3},i_{3}\\}}1$

and

$D(n;\\{6,4,2,0\\})=\sum_{i_{1}=1}^{n-1}\sum_{i_{2}=1}^{\min\\{n-i_{1},i_{1}\\}}\sum_{i_{3}=0}^{\min\\{n-i_{1}-i_{2},i_{2}\\}}1=\sum_{i_{1}=1}^{n-1}\sum_{i_{2}=1}^{\min\\{n-i_{1},i_{1}\\}}\sum_{i_{3}=0}^{0}\sum_{i_{4}=0}^{\min\\{n-i_{1}-i_{2},i_{2}\\}}1,$

where in the last line we inserted the trivial summation $\sum_{i_{3}=0}^{0}$
to correspond to the entry $1$ in $\underline{k}$ that does not exist in
$\underline{l}$, and we correspondingly renamed the old $i_{3}$ as new
$i_{4}$. From these common rewritings of the two summations we read off

$D_{K}(n)=\sum_{i_{1}=1}^{n-1}\sum_{i_{2}=1}^{\min\\{n-i_{1},i_{1}\\}}\sum_{i_{3}=0}^{0}\sum_{i_{4}=0}^{\min\\{n-i_{1}-i_{2}-i_{3},i_{3}\\}}1=\sum_{i_{1}=1}^{n-1}\sum_{i_{2}=1}^{\min\\{n-i_{1},i_{1}\\}}1.$

Incidentally, this sum simplifies to $\frac{1}{2}\lceil n/2\rceil(\lceil
n/2\rceil-1)+\frac{1}{2}\lfloor n/2\rfloor(\lfloor n/2\rfloor+1)$.

The non-trivial part of the last simplification involves exactly two non-
trivial summations, and that is due to the two sequences having exactly two
$J$-sets in common; $J$-sets are introduced next.

We will use $J$-sets in the counting of connected bipartite graphs with ind-
match and ord-match both equal to $2$.

######  Definition 4.5.

Let $z\geq 2$ and let $J_{1},J_{2},\ldots,J_{z}$ be distinct non-empty proper
subsets of $X$ with $|J_{1}|\leq|J_{2}|\leq\cdots\leq|J_{z}|<|X|=m$ such that
$J_{i}\cup J_{j}=X$ for all distinct $i,j\in[z]$. (Unlike in Theorem 3.8 and
Theorem 3.9, here the sets are proper.) All proper subsets $I$ of $X$ for
which $c_{I}>0$ for a given connected bipartite graph on $X\sqcup Y$ appear on
this list (see Definition 3.5), but this list of subsets may contain also some
special subsets $I$ for which $c_{I}=0$. By possibly reindexing, we assume
that $c_{J_{1}}c_{J_{2}}>0$, that $J_{1}$ has the smallest cardinality among
the $J_{i}$ and that $J_{2}$ has the smallest possible cardinality among the
remaining $J_{i}$.

When $J_{1}$ and $J_{2}$ are disjoint, then by Theorem 3.9, $z=2$ and $c_{X}$
is positive, and otherwise $c_{X}$ is only potentially positive.

For $l=0,\ldots,z$ we set $K_{l}=J_{1}\cap\cdots\cap J_{l}$ and
$k_{l}=|K_{l}|$. So $k_{0}=m$. Without loss of generality
$J_{1}=\\{1,2,\ldots,k_{1}\\}$. Since $J_{2}$ contains exactly $k_{2}$
elements of $J_{1}$ and all elements of $X\setminus J_{1}$, without loss of
generality $J_{2}=\\{1,2,\ldots,k_{2}\\}\cup\\{k_{1}+1,k_{1}+2,\ldots,m\\}$.
Since $J_{2}$ does not contain $J_{1}$, necessarily $k_{2}<k_{1}$. If $z\geq
3$, then $J_{3}$ must contain $\\{k_{2}+1,k_{2}+2,\ldots,m\\}$ and also
exactly $k_{3}$ of the elements of $J_{1}\cap J_{2}=\\{1,2,\ldots,k_{2}\\}$.
So without loss of generality
$J_{3}=\\{1,2,\ldots,k_{3}\\}\cup\\{k_{2}+1,k_{2}+2,\ldots,m\\}$. Since
$J_{3}$ is a proper subset, necessarily $k_{3}<k_{2}$. Similarly, for all
$l\in[z]$,
$J_{l}=\\{1,2,\ldots,k_{l}\\}\cup\\{k_{l-1}+1,k_{l-1}+2,\ldots,m\\}$ and
$k_{l}<k_{l-1}$. With this it is clear now that
$k_{0}=m>k_{1}>k_{2}>\cdots>k_{l}$. If $k_{z}>0$, we can add to the sets also
the one set $\\{k_{z}+1,k_{z}+2,\ldots,m\\}$, and then by increasing $z$ by 1,
we may assume that $k_{z}=0$. With this we give our final requirement for the
$J$-sets: we require $J_{1}\cap\cdots\cap J_{z}=~{}\emptyset$.

Note that $|J_{l}|=m-k_{l-1}+k_{l}$. So the condition
$|J_{1}|\leq|J_{2}|\leq\cdots\leq|J_{z}|<|X|=m$ is equivalent to the condition
$k_{l+1}\geq 2k_{l}-k_{l-1}$ for all $l=1,2,\ldots,z-1$. Thus
$k_{0},\ldots,k_{z}=0$ is a $k$-sequence (see Definition 4.1). In addition,
for any $l$, $|J_{l}|<|J_{l+1}|$ is equivalent to $k_{l+1}<2k_{l}-k_{l-1}$.

Thus the possible unlabeled subsets $J_{1},\ldots,J_{z}$ of $X$ with
$J_{1}\cap\cdots\cap J_{z}=\emptyset$ determine the $k$-sequence
$\\{k_{0},\ldots,k_{z}=0\\}$, and vice versa, a $k$-sequence defines up to
relabeling the $J$-sets (with $J_{1}\cap\cdots\cap J_{z}=\emptyset$).

The sets $J_{1}$ and $J_{2}$ in the definition contribute edges to $G$ that
will make ind-match and ord-match equal to $2$, and the remaining
$J_{3},\ldots,J_{z}$ may only potentially contribute an edge.

######  Examples 4.6.

The $k$-sequence $\\{2,1,0\\}$ corresponds to the sets $J_{1}=\\{1\\}$,
$J_{2}=\\{2\\}$.

The $k$-sequence $\\{3,2,1,0\\}$ corresponds to the sets $J_{1}=\\{1,2\\}$,
$J_{2}=\\{1,3\\}$, $J_{3}=\\{2,3\\}$. The $k$-sequence $\\{3,1,0\\}$
corresponds to the sets $J_{1}=\\{1\\}$, $J_{2}=\\{2,3\\}$.

The $k$-sequence $\\{4,3,2,1,0\\}$ corresponds to the sets
$J_{1}=\\{1,2,3\\}$, $J_{2}=\\{1,2,4\\}$, $J_{3}=\\{1,3,4\\}$,
$J_{4}=\\{2,3,4\\}$; the $k$-sequence $\\{4,2,1,0\\}$ corresponds to the sets
$J_{1}=\\{1,2\\}$, $J_{2}=\\{1,3,4\\}$, $J_{3}=\\{2,3,4\\}$; the $k$-sequence
$\\{4,2,0\\}$ corresponds to the sets $J_{1}=\\{1,2\\}$, $J_{2}=\\{3,4\\}$;
and the $k$-sequence $\\{4,1,0\\}$ corresponds to the sets $J_{1}=\\{1\\}$,
$J_{2}=\\{2,3,4\\}$.

The $k$-sequence $\\{6,4,2,1,0\\}$, corresponds to the sets
$J_{1}=\\{1,2,3,4\\}$, $J_{2}=\\{1,2,5,6\\}$, $J_{3}=\\{1,3,4,5,6\\}$ and
$J_{4}=\\{2,3,4,5,6\\}$, and the $k$-sequence $\\{6,4,2,0\\}$, corresponds to
$J_{1}=\\{1,2,3,4\\}$, $J_{2}=\\{1,2,5,6\\}$, $J_{3}=\\{3,4,5,6\\}$. So these
two $k$-sequences have exactly two $J$-sets in common, which explains why
$D_{K}$ computed earlier has only two summations, all other indices varying
trivially.

##  5\. Bipartite graphs with induced and ordered matching $2$

The aim of this section is to count the number of connected bipartite graphs
$G$ whose ord-match and ind-match are equal to $2$. For the rest of the
section, let $G$ be denote a connected bipartite graph. Suppose $X\sqcup Y$ is
the bipartition for the vertex set of $G$. Set $m:=|X|$ and $n:=|Y|$. So $G$
is a connected spanning subgraph of $K_{m,n}$. Without loss of generality we
assume that $m\leq n$. Moreover, suppose that $\operatorname{ind-
match}(G)=\operatorname{ord-match}(G)=2$. As the main result of this section,
in Theorem 5.4, we provide an inclusion-exclusion type formula for the number
of such graphs. As a consequence, in Corollary 5.5, we obtain a closed formula
for the number of these graphs when $m\leq 4$.

We first count a special type of connected bipartite graphs whose ind-match
and ord-match are equal to $2$.

######  Proposition 5.1.

Assume that $I$ is a proper subset of $X$ and that $n=|Y|\geq 3$. The number
of connected spanning subgraphs of $K_{m,n}$ with $\operatorname{ind-
match}(G)=\operatorname{ord-match}(G)=2$ for which $c_{I}c_{X\setminus I}>0$
equals $\binom{n-1}{2}$ if $|I|\not=n/2$ and
$\left\lfloor\frac{n}{2}\right\rfloor\left(\left\lceil\frac{n}{2}\right\rceil-1\right)$
otherwise.

###### Proof.

By Theorem 3.9, $I$, $X\setminus I$ and $X$ are the only subsets $K$ of $X$
for which $c_{K}$ is positive.

When $|I|\not=|X\setminus I|$, then the number of such graphs equals

$\sum_{c_{I}=1}^{n-2}\sum_{c_{X\setminus
I}=1}^{n-c_{I}-1}1=\sum_{i=1}^{n-2}\sum_{j=1}^{n-i-1}1=\sum_{i=1}^{n-2}(n-i-1)=\binom{n-1}{2},$

and if $|I|=|X\setminus I|$, then to not count unlabeled graphs twice, the
number of such graphs equals

$\sum_{c_{I}=1}^{n-2}\sum_{c_{X\setminus
I}=1}^{\min\\{c_{I},n-c_{I}-1\\}}1=\sum_{i=1}^{n-2}\sum_{j=1}^{\min\\{i,n-i-1\\}}1,$

which by Proposition 6.1 equals
$\left\lfloor\frac{n}{2}\right\rfloor\left(\left\lceil\frac{n}{2}\right\rceil-1\right)$.

The next proposition shows that the number of connected bipartite graphs $G$
with $\operatorname{ind-match}(G)=\operatorname{ord-match}(G)=2$ is closely
related to the notion of $k$-sequences defined in Section 4.

######  Proposition 5.2.

Let $z\geq 3$ and $k_{0}=m,k_{1},\ldots,k_{z}=0$ a $k$-sequence with
corresponding sets $J_{1},\ldots,J_{z}\subsetneq X=\\{1,\ldots,m\\}$ as in
Definition 4.5. Then $D(n;\\{m,k_{1},\ldots,k_{z}\\})$ equals the number of
connected bipartite graphs with edges from vertices in $X$ to vertices in the
set with $n$ elements for which ord-match and ind-match are both equal to 2,
and for which $c_{J_{1}}c_{J_{2}}>0$ and $c_{I}=0$ for all proper subsets $I$
of $X$ different from $J_{1},\ldots,J_{z}$.

###### Proof.

The count is of unlabelled sets of vertices. With the set-up as in Definition
4.5, we are counting the number of $(z+1)$-tuples
$(c_{J_{1}},\ldots,c_{J_{z}},c_{X})$ for which $c_{J_{1}},c_{J_{2}}>0$,
$(\sum_{l=1}^{z}c_{J_{l}})+c_{X}=|Y|=n$, and $c_{I}=0$ for all proper subsets
$I$ of $X$ other than $J_{1},\ldots,J_{z}$. In order to not count identical
unlabeled graphs twice, we need a further restriction: whenever
$J_{l},J_{l+1},\ldots,J_{l+k}$ have the same number of elements, then we may
assume that $c_{J_{l}}\geq c_{J_{l}+1}\geq\cdots\geq c_{l_{k}}$. If $J_{l}$
and $J_{l+1}$ have a different number of elements, then there is no
restriction on the comparison of sizes of $c_{J_{l}}$ and $c_{J_{l+1}}$. Thus
the count equals precisely $D(n;\\{m,k_{1},\ldots,k_{z}\\})$ from Definition
4.3.

In order to count all connected bipartite graphs with ord-match and ind-match
both being equal to $2$, we thus need a list of all $k$-sequences (or
equivalently, of corresponding $J$-sets for one of the two sets of vertices),
count the graphs for each of the $k$-sequences, and then use inclusion-
exclusion to remove multiple counts of some of the graphs. This will be done
in the next theorem.

We set some notation needed for the next theorem.

######  Notation 5.3.

For $m\leq n$, define

$N(m,n)=\left\lfloor{\frac{m-1}{2}}\right\rfloor{n-1\choose
2}+(\delta_{m,\hbox{\tiny
even}})\left\lfloor\frac{n}{2}\right\rfloor\left(\left\lceil\frac{n}{2}\right\rceil-1\right)+\sum_{K}(-1)^{|K|-1}D_{K}(n),$

where $K$ varies over all non-empty subsets of the set of all $k$-sequences
starting with $k_{0}=m$ and with at least $4$ terms, where $D_{K}$ is from
Definition 4.4, and $\delta_{m,\hbox{\tiny even}}$ is $1$ if $m$ is even and
$0$ otherwise.

######  Theorem 5.4.

If $m<n$, then $N(m,n)$ equals the number of connected non-isomorphic spanning
subgraphs of $K_{m,n}$ with both ord-match and ind-match being equal to $2$.

When $m=n$, then $N(m,n)$ counts the graphs as before with vertices unlabeled
but treating the two sets of vertices as labeled.

###### Proof.

Every graph under discussion corresponds to a unique collection of proper
subsets $J_{1},J_{2},\ldots,J_{z}$ with non-decreasing cardinalities and their
corresponding $k$-sequence $m=k_{0},k_{1},\ldots,k_{z}=0$.

When $z=2$, then $J_{1}$ and $J_{2}$ are disjoint, in which case Proposition
5.1 applies. Since $|J_{1}|\leq|J_{2}|$, necessarily $|J_{1}|\leq m/2$. The
$\left\lfloor{m-1\over 2}\right\rfloor$ cases in which $|J_{1}|<|J_{2}|$ each
give ${n-1\choose 2}$ graphs, and when $m$ is even, the case $|J_{1}|=|J_{2}|$
gives $E$ graphs.

The cases without disjoint $J$-subsets are covered in Proposition 5.2.

In the following corollary, we obtain a closed formula for the number of
connected bipartite graphs with $\operatorname{ind-
match}(G)=\operatorname{ord-match}(G)=2$ when $\min\\{|X|,|Y|\\}\leq 4$.

######  Corollary 5.5.

For $2\leq m\leq 4$, the number $N(m,n)$ of connected non-isomorphic spanning
subgraphs of $K_{m,n}$ with ind-match and ord-match both equal to 2 is:

$\begin{cases}E,&\hbox{if $m=2$ and necessarily $n\geq 3$};\\\ 3,&\hbox{if
$m=n=3$};\\\ {n-1\choose 2}+T,&\hbox{if $m=3<n$};\\\ 14,&\hbox{if $m=n=4$};\\\
{n-1\choose 2}+E+U+V,&\hbox{if $m=4<n$},\\\ \end{cases}$

where

$\displaystyle E$ $\displaystyle=\left\lfloor n\over
2\right\rfloor\left(\left\lceil n\over 2\right\rceil-1\right),$ $\displaystyle
T$ $\displaystyle=-{25\over 144}-{n\over 12}+{7n^{2}\over 24}+{n^{3}\over
36}+{(-1)^{n}\over 16}+{3+\sqrt{3}i\over 54}\left({-1-\sqrt{3}i\over
2}\right)^{n}+{3-\sqrt{3}i\over 54}\left({-1+\sqrt{3}i\over 2}\right)^{n},$
$\displaystyle U$ $\displaystyle={-1\over 16}+{5\over 12}n+{5\over
8}n^{2}+{1\over 12}n^{3}+{1\over 16}(-1)^{n},$ $\displaystyle V$
$\displaystyle={-641-486n+996n^{2}+132n^{3}+6n^{4}\over
3456}+{(11+2n)(-1)^{n}\over 128}+{(1-i)i^{n}+(1+i)(-i)^{n}\over 32}$
$\displaystyle\hskip 50.00008pt+{1+\sqrt{3}i\over 54}\left({-1-\sqrt{3}i\over
2}\right)^{n}+{1-\sqrt{3}i\over 54}\left({-1+\sqrt{3}i\over 2}\right)^{n}.$

###### Proof.

The justification for $m=2$ is that there is only one $k$-sequence with $z=2$,
and Proposition 5.1 applies.

The cases $m=n=3$ and $m=n=4$ are special because the two vertex sets can be
switched, and the general formula does not accommodate such switching. These
cases can be verified manually and we do not show the work here.

For $m=3<n$, the $k$-sequence $3,1,0$ is where then $J_{1}$ and $J_{2}$ are
disjoint and Proposition 5.1 applies; and for the $k$-sequence $3,2,1,0$, the
number of graphs equals the sum

$\sum_{i=1}^{n-1}\sum_{j=1}^{\min\\{n-i,i\\}}\sum_{k=0}^{\min\\{n-i-j,j\\}}1,$

which by Proposition 6.2 equals $T$.

For $m=4<n$, the $k$-sequence $4,1,0$ contributes ${n-1\choose 2}$ graphs and
the $k$-sequence $4,2,0$ contributes $E$ graphs by Proposition 5.1. The
contribution of the $k$-sequence $4,2,1,0$ is

$\sum_{i=1}^{n-1}\sum_{j=1}^{n-i}\sum_{k=0}^{\min\\{n-i-j,j\\}}1,$

which by Proposition 6.3 equals $U$. Finally, the $k$-sequence $4,3,2,1,0$
contributes

$\sum_{i=1}^{n-1}\sum_{j=1}^{\min\\{n-i,i\\}}\sum_{k=0}^{\min\\{n-i-j,j\\}}\sum_{l=0}^{\min\\{n-i-
j-k,k\\}}1,$

which by Proposition 6.4 equals $V$.

##  6\. Appendix: Some explicit summations

The closed forms of the sums in this appendix are used in the previous
section.

######  Proposition 6.1.

For any integer $n\geq 3$,

$\sum_{i=1}^{n-2}\sum_{j=1}^{\min\\{i,n-i-1\\}}1=\left\lfloor\frac{n}{2}\right\rfloor\left(\left\lceil\frac{n}{2}\right\rceil-1\right).$

###### Proof.

Inequality $i\leq n-i-1$ holds if and only if $i\leq\lfloor{n-1\over
2}\rfloor$, so the count simplifies to:

$\displaystyle\sum_{i=1}^{n-2}\sum_{j=1}^{\min\\{i,n-i-1\\}}1$
$\displaystyle=\sum_{i=1}^{\lfloor{n-1\over
2}\rfloor}\sum_{j=1}^{i}1+\sum_{i=\lfloor{n-1\over
2}\rfloor+1}^{n-2}\sum_{j=1}^{n-i-1}1$
$\displaystyle=\sum_{i=1}^{\lfloor{n-1\over
2}\rfloor}i+(n-1)\left(n-2-\left\lfloor{n-1\over
2}\right\rfloor\right)-\sum_{i=\lfloor{n-1\over 2}\rfloor+1}^{n-2}i$
$\displaystyle=\left\lfloor{n-1\over
2}\right\rfloor\left(\left\lfloor{n-1\over
2}\right\rfloor+1\right)+(n-1)\left({n\over 2}-\left\lfloor{n-1\over
2}\right\rfloor-1\right)$
$\displaystyle=\left\\{\begin{array}[]{ll}k^{2}-k,&\text{ if }n=2k;\\\
k^{2},&\text{ if }n=2k+1,\end{array}\right.$ $\displaystyle=\left\lfloor
n\over 2\right\rfloor^{2}+\left\lfloor n\over 2\right\rfloor\left(\left\lceil
n\over 2\right\rceil-\left\lfloor n\over 2\right\rfloor-1\right)$
$\displaystyle=\left\lfloor n\over 2\right\rfloor\left(\left\lceil n\over
2\right\rceil-1\right).$

######  Proposition 6.2.

For any non-negative integer $n$,

$\displaystyle\sum_{i=1}^{n-1}$
$\displaystyle\sum_{j=1}^{\min\\{n-i,i\\}}\sum_{k=0}^{\min\\{n-i-j,j\\}}1$
$\displaystyle=-{25\over 144}-{n\over 12}+{7n^{2}\over 24}+{n^{3}\over
36}+{(-1)^{n}\over 16}+{3+\sqrt{3}i\over 54}\left({-1-\sqrt{3}i\over
2}\right)^{n}+{3-\sqrt{3}i\over 54}\left({-1+\sqrt{3}i\over 2}\right)^{n}.$

###### Proof.

The summation on the left is the number $a_{n}$ of quadruples of non-negative
integers $i,j,k,l$ that add to $n$ with further restrictions that $i\geq j\geq
1$ and $j\geq k$. Set $u=i-j$, $v=j-k$. So we are looking for the number
$b_{n}$ of non-negative integer solutions $u,v,k,l$ such that $u+2v+3k+l=n$
minus the number $c_{n}$ of integer solutions $i\geq 0,j=0=k,l$ with $i+l=n$.

Let $A$ be the set of non-negative integer solutions of
$3x_{1}+2x_{2}+x_{3}+x_{4}=n$. For each $i=1,2,3,4$, let $A_{i}$ be the set of
non-negative integer solutions of $3x_{1}+2x_{2}+x_{3}+x_{4}=n$ with
$x_{i}\geq 1$. Then

$A=A_{1}\cup A_{2}\cup A_{3}\cup A_{3}.$

Using inclusion-exclusion formula

$|A|=\sum_{i=1}^{4}|A_{i}|-\sum_{i<j}|A_{i}\cap A_{j}|+\sum_{i<j<k}|A_{i}\cap
A_{j}\cap A_{k}|-|A_{1}\cap A_{2}\cap A_{3}\cap A_{4}|.$

To compute the cardinality of $A_{1}$, set $y_{1}=x_{1}-1$. Since for any
solution in $A_{1}$, we have $x_{1}\geq 1$, hence, for any such a solution,
$y_{1}\geq 0$. Moreover, it follows from $3x_{1}+2x_{2}+x_{3}+x_{4}=n$ that
$3y_{1}+2x_{2}+x_{3}+x_{4}=n-3$. Using induction hypothesis the number of
solution of this equation is $b_{n-3}$. Therefore, $|A_{1}|=b_{n-3}.$
Similarly, one an compute the cardinality of other $A_{i}$ and their
intersections. Hence,

$b_{n}=2b_{n-1}-b_{n-3}-b_{n-4}+2b_{n-6}-b_{n-7}.$

A similar argument shows that

$c_{n}=2c_{n-1}-c_{n-2}.$

This yields that

$\displaystyle c_{n}$ $\displaystyle=2c_{n-1}-c_{n-2}$
$\displaystyle=2c_{n-1}-2c_{n-3}+c_{n-4}$
$\displaystyle=2c_{n-1}-c_{n-3}-c_{n-3}+c_{n-4}$
$\displaystyle=2c_{n-1}-c_{n-3}-2c_{n-4}+c_{n-5}+c_{n-4}$
$\displaystyle=2c_{n-1}-c_{n-3}-c_{n-4}+c_{n-5}$
$\displaystyle=2c_{n-1}-c_{n-3}-c_{n-4}+2c_{n-6}-c_{n-7}.$

Therefore, $c_{n}$ satisfies the same recursive formula as $b_{n}$. Hence,
their subtraction $a_{n}=b_{n}-c_{n}$ also satisfies the same formula
$a_{n}=2a_{n-1}-a_{n-3}-a_{n-4}+2a_{n-6}-a_{n-7}$.

The roots of the corresponding characteristic polynomial
$x^{7}-2x^{6}+x^{4}+x^{3}-2x+1$ are $1,1,1,1,-1,-1/2+\sqrt{3}i/2$ and
$-1/2-\sqrt{3}i/2$. Thus by standard theory of linear recursive sequences with
constant coefficients (see for example Theorem 6.21 and Remark 6.23 in [17]),
the closed form for $a_{n}$ equals

$a_{n}=c_{0}+c_{1}n+c_{2}n^{2}+c_{3}n^{3}+c_{4}(-1)^{n}+c_{5}\left((-1+\sqrt{3}\,i)/2\right)^{n}+c_{6}\left((-1-\sqrt{3}\,i)/2\right)^{n}$

for some coefficients $c_{0}$ through $c_{6}$. With that we can set up a
system of linear equations with manually computed $a_{0}=0$, $a_{1}=0$,
$a_{2}=1$, $a_{3}=3$, $a_{4}=6$, $a_{5}=10$, $a_{6}=16$, and with the help of
Macaulay2 [9] we computed the corresponding closed form for $a_{n}$ to be

$-{25\over 144}-{n\over 12}+{7n^{2}\over 24}+{n^{3}\over 36}+{(-1)^{n}\over
16}+{3+\sqrt{3}i\over 54}\left({-1-\sqrt{3}i\over
2}\right)^{n}+{3-\sqrt{3}i\over 54}\left({-1+\sqrt{3}i\over 2}\right)^{n}.$

######  Proposition 6.3.

For any non-negative integer $n$,

$\sum_{i=1}^{n-1}\sum_{j=1}^{n-i}\sum_{k=0}^{\min\\{n-i-j,j\\}}1={-1\over
16}+{5\over 12}n+{5\over 8}n^{2}+{1\over 12}n^{3}+{1\over 16}(-1)^{n}.$

###### Proof.

With methods as in the proof of Proposition 6.2, we get the recursive formula
$a_{n}=3a_{n-1}-2a_{n-2}-2a_{n-3}+3a_{n-4}-a_{n-5}$. The corresponding
polynomial is $x^{5}-3x^{4}+2x^{3}+2x^{2}-3x+1$, whose roots are $1,1,1,1,-1$.
The initial conditions can easily be computed to be $a_{1}=0$, $a_{2}=1$,
$a_{3}=4$, $a_{4}=9$, $a_{5}=17$, from which with linear algebra (or via
https://oeis.org/A005744) we get the expression

$a_{n}={-1\over 16}+{5\over 12}n+{5\over 8}n^{2}+{1\over 12}n^{3}+{1\over
16}(-1)^{n}.$

######  Proposition 6.4.

For any non-negative integer $n$,

$\displaystyle\sum_{i=1}^{n-1}$
$\displaystyle\sum_{j=1}^{\min\\{n-i,i\\}}\sum_{k=0}^{\min\\{n-i-j,j\\}}\sum_{l=0}^{\min\\{n-i-
j-k,k\\}}={-641-486n+996n^{2}+132n^{3}+6n^{4}\over 3456}$ $\displaystyle\hskip
50.00008pt+{(11+2n)(-1)^{n}\over 128}+{(1-i)i^{n}+(1+i)(-i)^{n}\over 32}$
$\displaystyle\hskip 50.00008pt-{1\over 27}\left({-1-\sqrt{3}i\over
2}\right)^{n+1}-{1\over 27}\left({-1+\sqrt{3}i\over 2}\right)^{n+1}.$

###### Proof.

With the methods as in the proof of Proposition 6.2 we get the recursive
formula

$a_{n}=2a_{n-1}-a_{n-3}-2a_{n-5}+2a_{n-6}+a_{n-8}-2a_{n-10}+a_{n-11}.$

The roots of the corresponding polynomial
$x^{11}-2x^{10}+x^{8}+2x^{6}-2x^{5}-x^{3}+2x-1$ are
$1,1,1,1,1,-1,-1,i,-i,(-1+\sqrt{3}\,i)/2,(-1-\sqrt{3}\,i)/2$. The manually
computed initial conditions are $a_{1}=0$, $a_{2}=1$, $a_{3}=3$, $a_{4}=7$,
$a_{5}=12$, $a_{6}=20$, $a_{7}=30$, $a_{8}=44$, $a_{9}=61$, $a_{10}=83$,
$a_{11}=109$. Thus with linear algebra we get the closed form

$\displaystyle a_{n}$ $\displaystyle={-641-486n+996n^{2}+132n^{3}+6n^{4}\over
3456}+{(11+2n)(-1)^{n}\over 128}+{(1-i)i^{n}+(1+i)(-i)^{n}\over 32}$
$\displaystyle\hskip 50.00008pt+{1+\sqrt{3}i\over 54}\left({-1-\sqrt{3}i\over
2}\right)^{n}+{1-\sqrt{3}i\over 54}\left({-1+\sqrt{3}i\over 2}\right)^{n}.$

Part of the work was done when the first author was visiting Purdue
University. He would like to thank the Department for funding the visit and
for a great hospitality. The research of the second author is supported by a
FAPA grant from the Universidad de los Andes.

## References

  * [1] Arindam Banerjee, Selvi Kara Beyarslan, and Hà Huy Tài. Regularity of edge ideals and their powers. In Advances in Algebra, Volume 277 of Springer Proc. Math. Stat., pages 17–52. Springer, Cham, 2019.
  * [2] Selvi Beyarslan, Huy Tài Hà, and Trân Nam Trung. Regularity of powers of forests and cycles. J. Algebraic Combin. 42 (4) (2015), 1077–1095.
  * [3] Markus Brodmann. The asymptotic nature of the analytic spread. Math. Proc. Cambridge Philos. Soc. 86 (1) (1979), 35–39.
  * [4] Kathie Cameron and Tracy Walker. The graphs with maximum induced matching and maximum matching the same size. Discrete Math. 299 (1-3) (2005), 49–55.
  * [5] Alexandru Constantinescu and Matteo Varbaro. Koszulness, Krull dimension, and other properties of graph-related algebras. J. Algebraic Combin. 34 (3) (2011), 375–400.
  * [6] S. Dale Cutkosky, Jürgen Herzog, and Ngô Viêt Trung. Asymptotic behaviour of the Castelnuovo-Mumford regularity. Compositio Math. 118 (3) (1999), 243–261.
  * [7] Christopher A. Francisco and Huy Tài Hà. Whiskers and sequentially Cohen-Macaulay graphs. J. Combin. Theory Ser. A 115 (2) (2008), 304–316.
  * [8] Isidoro Gitler, Enrique Reyes, and Rafael H. Villarreal. Blowup algebras of ideals of vertex covers of bipartite graphs. Contemp. Math. 376 (2005), 273–279.
  * [9] Daniel Grayson and Michael Stillman, Macaulay2, a software system for research in algebraic geometry, available at http://www.math.uiuc.edu/Macaulay2.
  * [10] Jürgen Herzog and Takayuki Hibi. Monomial Ideals. Graduate Texts in Mathematics. Springer-Verlag, New York, 2010.
  * [11] Takayuki Hibi, Akihiro Higashitani, Kyouko Kimura, and Augustine B. O’Keefe. Algebraic study on Cameron-Walker graphs. J. Algebra 422 (2015), 257–269.
  * [12] Takayuki Hibi, Akihiro Higashitani, Kyouko Kimura, and Akiyoshi Tsuchiya. Dominating induced matchings of finite graphs and regularity of edge ideals. J. Algebraic Combin. 43 (1) (2016), 173–198.
  * [13] Takayuki Hibi, Kyouko Kimura, Kazunori Matsuda, and Akiyoshi Tsuchiya. Regularity and a-invariant of Cameron–Walker graphs. J. Algebra 584 (2021), 215–242.
  * [14] Le Tuan Hoa, Kyouko Kimura, Naoki Terai, and Tran Nam Trung. Stability of depths of symbolic powers of Stanley–Reisner ideals. J. Algebra 473 (2017), 307–323.
  * [15] Mordechai Katzman. Characteristic-independence of Betti numbers of graph ideals. J. Combin. Theory Ser. A 113 (3) (2006), 435–454.
  * [16] Vijay Kodiyalam, Asymptotic behaviour of Castelnuovo-Mumford regularity. Proc. Amer. Math. Soc. 128 (2000), 407–411.
  * [17] Rudolf Lidl and Harald Niederreiter. Introduction to finite fields and their applications. Cambridge University Press, 1986.
  * [18] Seyed Amin Seyed Fakhari, Depth, Stanley depth, and regularity of ideals associated to graphs, Arch. Math. (Basel) 107 (2016), 461–471.
  * [19] Seyed Amin Seyed Fakhari. Depth and stanley depth of symbolic powers of cover ideals of graphs. J. Algebra 492 (2017), 402–413.
  * [20] Seyed Amin Seyed Fakhari and Siamak Yassemi. Improved bounds for the regularity of powers of edge ideals of graphs. J. Commut. Algebra 15 (1) (2023), 85–98.
  * [21] Adam Van Tuyl. Sequentially Cohen-Macaulay bipartite graphs: vertex decomposability and regularity. Arch. Math. (Basel) 93 (5) (2009), 451–459.
  * [22] Adam Van Tuyl and Rafael Villarreal, Shellable graphs and sequentially Cohen-Macaulay bipartite graphs, J. Combin. Theory, Ser. A 115 (2008), 799–814.
  * [23] Rafael H. Villarreal. Cohen-Macaulay graphs. Manuscripta Math. 66 (3) (1990), 277–293.
  * [24] Russ Woodroofe. Matchings, coverings, and Castelnuovo-Mumford regularity. J. Commut. Algebra 6 (2) (2014), 287–304.