\documentclass[ALCO, Unicode]{cedram} \usepackage{cleveref} \usepackage{xcolor} \usepackage{pgfplots} \pgfplotsset{compat=1.16} \usepackage{mathrsfs} \usetikzlibrary{arrows} \newcommand{\ordm}{\operatorname{ord-match}} \newcommand{\indm}{\operatorname{ind-match}} \newcommand{\reg}{\operatorname{reg}} \newcommand{\minm}{\operatorname{min-match}} \newcommand{\m}{\operatorname{match}} \newcommand{\depth}{\operatorname{depth}} \def\drlabel#1{\label{#1}} \title[Induced, ordered matchings, and regularity]{Induced matching, ordered matching and Castelnuovo-Mumford regularity of bipartite~graphs} \author[\initial{A.} \middlename{V.} Jayanthan]{\firstname{A.} \middlename{V.} \lastname{Jayanthan}} \address{Department of Mathematics, I.I.T. Madras, Chennai, Tamil Nadu 600036, India} \email{jayanav@iitm.ac.in} \author[\initial{S.} \middlename{Amin} Seyed Fakhari] {\firstname{Seyed} \middlename{Amin} \lastname{Seyed Fakhari}} \address{Departamento de Matem\'aticas, Universidad de los Andes, Bogot\'a, Colombia} \email{s.seyedfakhari@uniandes.edu.co} \author[\initial{I.} Swanson]{\firstname{Irena} \lastname{Swanson}} \address{Department of Mathematics, Purdue University, West Lafayette, IN 47907, USA} \email{irena@purdue.edu} \author[\initial{S.} Yassemi]{\firstname{Siamak} \lastname{Yassemi}} \address{Department of Mathematics, Purdue University, Indianapolis, IN 46202, USA} \email{syassemi@purdue.edu} \thanks{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. The authors are thankful to the anonymous referees who read the paper meticulously and made several corrections and suggestions that improved the exposition considerably.} \keywords{Induced matching, ordered matching, Castelnuovo-Mumford regularity, depth, edge ideal, cover ideal} \subjclass{10X99, 14A12, 11L05} \begin{document} \begin{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. \end{abstract} \maketitle \section{Introduction}\label{sec1} Let $G$ be a finite simple graph on the vertex set $V(G)= \{x_1,\ldots,x_d\}$ and edge set $E(G)$. Consider the polynomial ring $S=K[x_1,\ldots,x_d]$, where $K$ is a field. We identify the vertices of $G$ to the variables of $S$, and the edges of $G$ to the corresponding squarefree quadratic monomial of $S$. For example, the edge $\{x_1,x_2\}$ will be denoted by $x_1x_2$. The \textit{edge ideal} of $G$ is defined as $I(G) = \langle x_ix_j ~:~ x_ix_j \in E(G)\rangle \subset S$. Ever since the introduction of the edge ideal by Villarreal in~\cite{V90}, 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~\cite{BBH19} 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 \textit{matching numbers} have been obtained for the regularity. For a graph $G$, let $\indm(G), \ordm(G), \minm(G)$ and $\m(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 \[\indm(G) \leq \reg(S/I(G))\leq \{\ordm(G), \minm(G)\} \leq \m(G),\] where the first inequality was proved by Katzman~\cite{K06}, the second inequality can be found in~\cite{W14} (for $\minm(G)$) and~\cite{CV11} (for $\ordm(G))$ and the third inequality follows from the definition. A graph $G$ is said to be a {\it Cameron-Walker graph} if $\indm(G) = \m(G)$. This is a class of graphs which is well studied from both combinatorial and algebraic perspectives~\cite{CW05,HHKO15,HKMT21}. In~\cite{HHKT16}, Hibi et al. studied graphs with $\indm(G) = \minm(G)$. They gave a structural characterization of graphs satisfying $\indm(G) = \minm(G)$. In this article, we study graphs satisfying $\indm(G) = \ordm(G)$. Besides the combinatorial reasons for understanding graphs $G$ with $\indm(G) = \ordm(G)$, there is also an algebraic motivation to understand graphs with this property. It was proved by Cutkosky, Herzog and Trung~\cite{CHT}, and independently by Kodiyalam~\cite{vijay}, that for a homogeneous ideal $I$ in a polynomial ring, $\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~\cite{BBH19} and the references within). It was shown in~\cite[Theorem 4.5]{selviha} and~\cite[Theorem 3.9]{SY23} that for every integer $s\geq 1$,$$2s+\indm(G)-2\leq \reg(S/I(G)^s)\leq 2s+\ordm(G)-2.$$ If $\indm(G)=\ordm(G)$, then this gives an explicit expression for the regularity of powers of the edge ideal. Classifying all graphs $G$ with $\indm(G) = \ordm(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 \Cref{sec:prelim}. 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 $\indm(G)=\ordm(G)=1$ (Theorem~\ref{thmindred1}). 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 $\indm(G)=\ordm(G)$ (Theorem~\ref{thmordindclass}). To illustrate that this class of graphs is very different from the class of graphs $G$ with $\indm(G) = \minm(G)$, we construct a class of graphs, $G_{r,m}$, $2\leq r \leq m$, with $\reg(S/I(G_{r,m})) = \indm(G) = \ordm(G) = r$ and $\minm(G) = m$. The paper is organized as follows. We collect some graph theory essentials in \Cref{sec:prelim}. Characterizing the equality of induced and ordered matching numbers is done in \Cref{sec:indordeq}. \section{Preliminaries}\label{sec:prelim} 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_d]$ 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 {\it 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 {\it neighbor set} of $x_i$ is $N_G(x_i)=\big\{x_j\mid x_ix_j\in E(G)\big\}$. Moreover, the {\it 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 {\it degree} of $x_i$ and is denoted by ${\rm deg}_G(x_i)$. A vertex of degree one is called a {\it leaf} of $G$. The graph $G$ is a {\it forest} if it does not have any cycle. The {\it 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 {\it independent subset} of~$G$ if there are no edges among the vertices of $A$. The graph $G$ is called {\it unmixed} (or {\it well-covered}) if all maximal independent sets of $G$ have the same cardinality. A \textit{matching} in a graph is a subgraph consisting of pairwise disjoint edges. The cardinality of the largest matching in $G$ is the \textit{matching number} of $G$ and is denoted by $\m(G)$. A matching in $G$ is said to be a \textit{maximal matching} if it is not properly contained in any matching of $G$. The \textit{minimum matching number} of $G$, denoted by $\minm(G)$, is the minimum cardinality of a maximal matching in $G$. A matching is said to be an \textit{induced matching} if none of the edges in the matching are joined by an edge in $G$. The largest size of an induced matching in $G$ is called the \textit{induced matching number} of $G$, denoted by $\indm(G)$. A graph $G$ is called a \textit{Cameron-Walker} graph if $\indm(G) = \m(G)$. A set $A = \{x_{i1} x_{i2} \in E(G) \mid 1 \leq i \leq r\}$ is said to be an \textit{ordered matching}~\cite{CV11}, if \begin{enumerate} \item $A$ is a matching in $G$, \item $\{x_{i1} \mid 1 \leq i \leq r \}$ is an independent set, \item if $x_{i1} x_{j2} \in E(G)$, then $i \leq j$. \end{enumerate} The \textit{ordered matching number} of $G$, denoted by $\ordm(G)$, is defined to be \[\ordm(G):= \max\{|A| :~ A \text{ is an ordered matching of } G\}.\] As already written in the introduction, \[\indm(G) \leq \reg(S/I(G))\leq \{\ordm(G), \minm(G)\} \leq \m(G),\] There are several examples with inequality $\minm(G)\leq\ordm(G)$ and other examples with inequality $\ordm(G)\leq\minm(G)$. A graph $G$ is said to be {\it Cohen-Macaulay} (resp. {\it sequentially Cohen-Macaulay}) if~$S/I(G)$ is Cohen-Macaulay (resp. sequentially Cohen-Macaulay). A {\it 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 \textit{bipartite complement}, is the bipartite graph with $V(G^{bc}) = V(G)=X \sqcup Y$ and for $x\in X$ and~$y\in Y$, we have $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 \textit{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$. It was proved by Brodmann~\cite{Brod79} that for any homogeneous ideal $I$ in a graded ring~$R$, $\depth(R/I^k)$ is a constant for $k\gg 0$. One consequence of the equality of induced matching number and ordered matching number is that the depth function of powers of the {\it cover ideal} $J(G) = \bigcap_{x_ix_j \in E(G)} (x_i,x_j)$ of $G$ is constant from the start, as we prove next. \begin{theorem}\label{thmcover} Assume that $G$ is a bipartite graph with $\indm(G)=\ordm(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-\indm(G)-1.$$ \end{theorem} \begin{proof} Since ${\rm reg}(I(G))=\indm(G)+1$ by inequalities in the Introduction, it follows from~\cite[Proposition 8.1.10]{hh2010} that the projective dimension of $S/J(G)$ is equal to $\indm(G)+1$. Thus, Auslander-Buchsbaum formula implies that ${\rm depth}(S/J(G))=d-\indm(G)-1$. On the other hand, it follows from~\cite[Theorem 3.2]{HKTT17} that$$d-\indm(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~\cite[Theorem 3.4]{HKTT17} (see also~\cite[Theorem 3.1]{FAKHARI17}) that ${\rm depth}(S/J(G)^k)=d-\ordm(G)-1$ for any $k\gg 0$. Since $\ordm(G)=\indm(G)$, the assertion follows from the above inequalities. \end{proof} \section{Equality of induced and ordered matching numbers}\label{sec:indordeq} In this section, we characterize all bipartite graphs $G$ without isolated vertices and with $\ordm(G)=\indm(G)$. Before proving our general characterization (Theorem~\ref{thmordindclass}), 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~\cite{FH, adam, VV08}, 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 $\ordm(G)=\m(G)$ holds. As a consequence of this equality, we are able to characterize sequentially Cohen-Macaulay bipartite graphs $G$ with $\ordm(G)=\indm(G)$. \begin{theorem}\label{thmseqCM} Let $G$ be a bipartite graph. If $G$ is sequentially Cohen-Macaulay, then $\ordm(G)={\rm match}(G)$. In particular, for a sequentially Cohen-Macaulay bipartite graph $G$, we have $\indm(G)=\ordm(G)$ if and only if $G$ is a Cameron-Walker graph. \end{theorem} \begin{proof} We prove the equality $\ordm(G)={\rm match}(G)$ by induction on $|V(G)|$. If $|V(G)|=2$, then $\ordm(G)=\m(G)$. Assume by induction that if $H$ is a sequentially Cohen-Macaulay bipartite graph with $|V(H)| < |V(G)|$, then $\ordm(H)=\m(H)$. By~\cite[Corollary 3.11]{VV08}, there is a leaf $x\in V(G)$ such that $G\setminus N_G[x]$ is sequentially Cohen-Macaulay. Using~\cite[Lemma 2.1]{SF16} and the induction hypothesis we have$$\ordm(G)\geq \ordm(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, $\ordm(G)={\rm match}(G)$. The second assertion follows by observing that $G$ is Cameron-Walker if and only if $\indm(G)=\m(G)$. \end{proof} 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)=\ordm(G)=k$. \begin{example}\label{exmatchsell} 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 $\ordm(G_k)={\rm match}(G_k)=k$. It is easy to see that $\ordm(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~\cite[Corollary~3.11]{VV08}, the graph $G_3$ is not sequentially Cohen-Macaulay. Now, suppose that~$k\geq 4$. Let $z$ 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~\cite[Lemma~2.1]{SF16} and the induction hypothesis, we have $$\ordm(G_k)\geq \ordm(G_{k-1})+1=k.$$Thus, $\ordm(G_k)=k$. \end{example} In Example~\ref{exmatchsell}, we showed that for each integer $k\geq 3$, there is a non-sequentially Cohen-Macaulay bipartite graph $G$ with ${\rm match}(G)=\ordm(G)=k$. The following proposition shows that we cannot expect such an example when $k\leq 2$. \begin{proposition}\label{propseqCM} Let $G$ be a bipartite graph with ${\rm match}(G)=\ordm(G)\leq 2$. Then $G$ is a sequentially Cohen-Macaulay graph. \end{proposition} \begin{proof} Suppose that $G$ is not sequentially Cohen-Macaulay. It is known that any forest is sequentially Cohen-Macaulay (see for instance~\cite[Theorem 1.3]{VV08}). 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 $\ordm(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)$ cannot 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 $\ordm(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~\cite[Theorem 1.3]{VV08}, the graphs $G\setminus N_G[w]$ and~$G\setminus N_G[s]$ are sequentially Cohen-Macaulay. Hence~\cite[Corollary 3.11]{VV08} implies that~$G$ is a sequentially Cohen-Macaulay graph, which is a contradiction. \end{proof} In the following result, we give a characterization of bipartite graphs without isolated vertices and with $\ordm(G)=\indm(G)=1$. A classification of bipartite graphs with ordered matching number and induced matching number being equal to an arbitrary positive integer strictly bigger than 1 is in Theorem~\ref{thmordindclass}. \begin{theorem}\label{thmindred1} Let $G$ be a bipartite graph with no isolated vertices. Then we have that $\ordm(G)=\indm(G)=1$ if and only if $G$ is a complete bipartite graph. \end{theorem} \begin{proof} Let $\{x_1,\ldots, x_m\}\sqcup \{y_1,\ldots,y_n\}$ be the bipartition for $V(G)$ for some $m,n\geq 1$. If $G = K_{m,n}$, then clearly $\indm(G)=1=\ordm(G)$. Conversely, suppose that $G$ is not complete bipartite. Since $G$ has no isolated vertices, necessarily $m, n \ge 2$, and by permuting the vertices we may assume that $x_1 y_1 \notin E(G)$, $x_1 y_2, x_2 y_1 \in E(G)$. Then $\{x_2y_1, x_1y_2\}$ is an ordered matching in $G$. Hence $\ordm(G) > 1$. \end{proof} \begin{definition}\label{defcI} Let $G$ be a bipartite graph with bipartition $V(G)=X\sqcup Y$. 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|$. \end{definition} 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 $C_I$. If $I$ contains an isolated vertex of $X$, then $C_I = \emptyset$. If $Y$ does not have isolated vertices, then $C_\emptyset = \emptyset$. In order to characterize bipartite graphs $G$ with $\indm(G)=\ordm(G)$, we need the following two propositions. \begin{proposition}\label{propinduced} Let $G$ be a bipartite graph with bipartition $V(G)=X\sqcup Y$ 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$. \end{proposition} \begin{proof} Suppose that $\indm(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_1b_1, a_2b_2, \ldots, a_rb_r$ is an induced matching. For each $i \in [r] = \{1, 2, \ldots, r\}$, let $J_i$ be the set of all $x \in X$ with an edge to $b_i$. Then $a_i \in J_i$, $a_j \not \in J_i$ for all $j \not = i$, and $b_i \in C_{J_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_1b_1, a_2b_2, \ldots, a_rb_r$ is an induced matching, so that $\indm(G)$ is at least $r$. \end{proof} \begin{proposition}\label{propinducedordered} Let $G$ be a bipartite graph with bipartition $V(G)=X\sqcup Y$ and let~$r$ be a positive integer. Then the following are equivalent: \begin{enumerate} \item $\ordm(G) \geq r$. \item 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]$, $J_i$ is not contained in $J_1 \cup \cdots \cup J_{i-1}$. \end{enumerate} If the union of $J_1, \ldots, J_r$ equals the set of non-isolated vertices in~$X$ for all $J_1, \ldots, J_r$ with the properties as in (2), then $\ordm(G) \leq r$. Moreover, if $\ordm(G) \leq r$, then for all possible sets $J_1, \ldots, J_r$ with the properties as in (2), their union equals the set of non-isolated vertices in~$X$. \end{proposition} \begin{proof} (1) $\Rightarrow$ (2): Suppose that $\ordm(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_1b_1, a_2b_2, \ldots, a_rb_r$ is an ordered matching. For each $i \in [r]$, let $J_i$ be the set of all $x \in X$ with an edge to $b_i$. Then $a_i \in J_i$, $a_{i+1}, \ldots, a_r \not \in J_i$, and $b_i \in C_{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$ as in (2). 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_1b_1, a_2b_2, \ldots, a_rb_r$ is an ordered matching. This proves (1). Observe that the sets $J_i$ cannot contain any isolated vertices. If $\ordm(G)$ is at least $r+1$, then by the equivalence of (1) and (2), for some $J_1, \ldots, J_r$, their union cannot be the set of non-isolated vertices of $X$. Now let $\ordm(G) \le r$. Let $J_1, \ldots, J_r$ be as in (2) and let $a_1, \ldots, a_r$ and $b_1, \ldots, b_r$ be the vertices defined in the proof of (2) $\Rightarrow$~(1). If there exists a non-isolated vertex $a \in X \setminus J_1 \cup \cdots \cup J_r$, then there is a vertex $b \in Y$ that is adjacent to $a$. By definition of the sets $C_{J_i}$, there is no edge between $a$ and $b_1, \ldots, b_r$. Thus $a_1b_1, a_2b_2, \ldots, a_rb_r, ab$ is an ordered matching, contradicting that $\ordm(G) \le r$. Thus $J_1 \cup \cdots \cup J_r$ is the set of all non-isolated vertices of~$X$. \end{proof} Using Propositions~\ref{propinduced} and~\ref{propinducedordered}, we can classify all bipartite graphs for which ordered matching number and induced matching number are equal. \begin{theorem}\label{thmordindclass} (Classification) Let $G$ be a bipartite graph with bipartition $V(G)=X\sqcup Y$ 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 $\indm(G)=\ordm(G)=r$ if and only if the following conditions are satisfied: \begin{enumerate} \item $z \ge r$. \item 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}$. \item For any distinct $j_1, \ldots, j_r \in [z]$ such that for all $i \in [r]$, $J_{j_i}$ is not contained in $J_{j_1} \cup \cdots \cup J_{j_{i-1}}$, the union $J_{j_1} \cup \cdots \cup J_{j_r}$ equals the set of all non-isolated vertices of $X$. \end{enumerate} \end{theorem} \begin{proof} Observe that the existence of $J_{j_1}, \ldots, J_{j_r}$ in (2) implies that for all $i \in [r]$, $J_{j_i}$ is not contained in $J_{j_1} \cup \cdots \cup J_{j_{i-1}}$. First suppose that $\indm(G)$ and $\ordm(G)$ equal~$r$. Proposition~\ref{propinduced} implies (1) and (2) and Proposition~\ref{propinducedordered} implies (3). Now suppose that the three conditions are satisfied. Then by Proposition~\ref{propinduced}, induced matching number of $G$ is at least $r$, and by Proposition~\ref{propinducedordered}, $\ordm(G)$ is at most $r$. But $\ordm(G)$ is greater than or equal to $\indm(G)$. So, $\indm(G)$ and $\ordm(G)$ are both equal to $r$. \end{proof} We can say more in case $\ordm(G)$ and $\indm(G)$ are both equal to~2, and for simplicity we state it only for graphs with no isolated vertices: \begin{theorem}\label{thmordindclasstwo} (Classification for r = 2) Let $G$ be a bipartite graph with bipartition $V(G)=X\sqcup Y$ and with no isolated vertices. Let $J_1, \ldots, J_z$ be all the subsets $I$ of $X$ for which $c_I$ is positive. Then $\indm(G)=\ordm(G)=2$ if and only if the following conditions are satisfied: \begin{enumerate} \item $z \ge 2$. \item There exist distinct $i, j \in [z]$ such that neither $J_i$ nor $J_j$ is contained in the other. \item For any two distinct $i, j \in [z]$, $J_i \cup J_j = X$. \end{enumerate} Furthermore, if some $J_i$ and $J_j$ are disjoint, then $z$ equals $2$ or $3$; the latter exactly when the graph is connected and in this case $c_X > 0$. \end{theorem} \begin{proof} Suppose that $\indm(G) = \ordm(G) = 2$. Then Theorem~\ref{thmordindclass} implies conditions (1) and (2). For distinct $i, j \in [z]$, the sets $J_i$ and $J_j$ are distinct, so one of $J_i$ and $J_j$ is not contained in the other, whence Theorem~\ref{thmordindclass} implies condition (3) since $V(G)$ has no isolated vertices. This proves that $\indm(G) = \ordm(G) = 2$ implies the three conditions. The converse follows from Theorem~\ref{thmordindclass}. Now suppose that $J_i \cap J_j = \emptyset$. Let $k \in [z] \setminus \{i,j\}$. By condition~(3), $J_k$ contains the complements of $J_i$ and of $J_j$, so that $J_k$ contains $X$ and hence equals~$X$. Thus either $z = 3$ and $G$ is connected, or else $z = 2$ and $G$ is not connected. \end{proof} As a consequence of the above theorem, we obtain an explicit graph theoretic characterization of bipartite graphs $G$ with $\indm (G) =\ordm(G)=2$. \begin{corollary}\label{corindred2} Let $G$ be a bipartite graph with no isolated vertices. Then $\indm (G) =\ordm(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. \end{corollary} \begin{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'\in C_{J_j}$, the equality $N_{G^{bc}}(y)\cap N_{G^{bc}}(y')=\emptyset$ holds. Thus, Condition (3) of Theorem~\ref{thmordindclasstwo} (and in fact, by Proposition~\ref{propinducedordered}, the inequality $\ordm(G)\leq 2$) is equivalent to say that $G^{bc}$ is the disjoint union of complete bipartite graphs. Moreover, note that $\indm (G)\geq 2$ if and only if $\indm (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. \end{proof} 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))=\indm(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}))=\indm(G_{r,m})=\ordm(G_{r,m})=r$ and $\minm(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~\ref{thmregordmatch} shows that the family of graphs $G$ with $\indm(G)=\ordm(G)$ is far from the class of graphs considered in~\cite{HHKT16}. \begin{theorem}\label{thmregordmatch} Let $2\leq r\leq m$ be positive integers. Then there is a connected bipartite graph $G_{r,m}$ such that: \begin{enumerate} \item ${\rm reg}(S/I(G_{r,m}))=\indm(G_{r,m})=\ordm(G_{r,m})=r$; \item $\minm(G_{r,m})=m$; \item $G_{r,m}$ does not have any leaf (and hence $G_{r,m}$ is not a sequentially Cohen-Macaulay graph); \item $G_{r,m}$ is not an unmixed graph. \end{enumerate} \end{theorem} \begin{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 bipartitioned vertex set $V(G_{r,m})=X\sqcup Y$ and edge set \begin{align*} E(G_{r,m})=\bigcup_{1\leq j\leq r-1}\{x_1y_j, x_{j+1}y_j\}& \cup\bigcup_{r\leq j\leq m}(\{x_1y_j\}\cup \{x_iy_j\mid r+1\leq i\leq m+1\})\\ &\cup\{x_iy_{m+1}\mid 1\leq i\leq m+1\}. \end{align*} For the convenience of the reader, we illustrate the graph $G_{r,m}$ with a sample picture below: \begin{figure}[h] \centering \begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1.0cm,y=1.0cm] \draw (1.,3.)-- (1.,1.); \draw (1.,3.)-- (3.,1.); \draw (1.,3.)-- (5.,1.); \draw (1.,3.)-- (7.,1.); \draw (1.,3.)-- (9.,1.); \draw (3.,3.)-- (9.,1.); \draw (5.,3.)-- (9.,1.); \draw (7.,3.)-- (9.,1.); \draw (9.,3.)-- (9.,1.); \draw (3.,3.)-- (1.,1.); \draw (5.,3.)-- (3.,1.); \draw (5.,3.)-- (5.,1.); \draw (5.,3.)-- (7.,1.); \draw (7.,3.)-- (3.,1.); \draw (7.,3.)-- (5.,1.); \draw (7.,3.)-- (7.,1.); \draw (9.,3.)-- (3.,1.); \draw (9.,3.)-- (5.,1.); \draw (9.,3.)-- (7.,1.); \begin{scriptsize} \draw [fill=black] (1.,3.) circle (1.5pt); \draw[color=black] (1,3.2) node {$x_1$}; \draw [fill=black] (3.,3.) circle (1.5pt); \draw[color=black] (3.,3.2) node {$x_2$}; \draw [fill=black] (5.,3.) circle (1.5pt); \draw[color=black] (5.,3.2) node {$x_3$}; \draw [fill=black] (7.,3.) circle (1.5pt); \draw[color=black] (7.,3.2) node {$x_4$}; \draw [fill=black] (9.,3.) circle (1.5pt); \draw[color=black] (9.,3.2) node {$x_5$}; \draw [fill=black] (1.,1.) circle (1.5pt); \draw[color=black] (1.,0.8) node {$y_1$}; \draw [fill=black] (3.,1.) circle (1.5pt); \draw[color=black] (3.,0.8) node {$y_2$}; \draw [fill=black] (5.,1.) circle (1.5pt); \draw[color=black] (5.,0.8) node {$y_3$}; \draw [fill=black] (7.,1.) circle (1.5pt); \draw[color=black] (7.,0.8) node {$y_4$}; \draw [fill=black] (9.,1.) circle (1.5pt); \draw[color=black] (9.,0.8) node {$y_5$}; \end{scriptsize} \end{tikzpicture} \caption{$G_{2,4}$} \label{fig:g24} \end{figure} It follows directly from the definition that \begin{equation*} 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. \end{equation*} Clearly, $G_{r,m}$ is a connected bipartite graph that does not have any leaf. Therefore using~\cite[Corollary 2.10]{VV08}, 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 conditions (1) and (2) of the statement of the theorem. Set $$J_1=N_{G_{r,m}}(y_1), J_2=N_{G_{r,m}}(y_2), \ldots, 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~\ref{thmordindclass} that $${\rm reg}(S/I(G_{r,m}))=\indm(G_{r,m})=\ordm(G_{r,m})=r.$$ Now, we compute $\minm(G_{r,m})$. It is obvious that $$\{y_2x_3, y_3x_4,\ldots, y_{m-1}x_m, y_mx_1, y_{m+1}x_2\}$$ is a maximal matching in $G_{r,m}$ of size $m$. Hence, $\minm(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