# Down-left graphs and a connection to toric ideals of graphs

Jennifer Biermann  Department of Mathematics and Computer Science, Hobart and
William Smith Colleges
Geneva, NY 14456<EMAIL_ADDRESS>,  Beth Anne Castellano  Department of
Mathematics, Dartmouth College, Hanover, NH 03755
<EMAIL_ADDRESS>,  Marcella Manivel  Department of
Mathematics, University of Minnesota, Minneapolis, MN 55455<EMAIL_ADDRESS>,  Eden Petruccelli  Department of Mathematics and Statistics
McMaster University, Hamilton, ON, L8S 4L8 31 Lower Horning Rd, Hamilton, ON
L8S 3E9<EMAIL_ADDRESS>and  Adam Van Tuyl  Department of
Mathematics and Statistics
McMaster University, Hamilton, ON, L8S 4L8<EMAIL_ADDRESS>
###### Abstract.

We introduce a family of graphs, which we call down-left graphs, and study
their combinatorial and algebraic properties. We show that members of this
family are well-covered, $C_{5}$-free, and vertex decomposable. By applying a
result of Khosh-Ahang and Moradi, the (Castelnuovo-Mumford) regularity of the
associated edge ideals is the induced matching number of the graph. As an
application, we give a combinatorial interpretation for the regularity of the
toric ideals of chordal bipartite graphs that are $(K_{3,3}\setminus e)$-free.

###### Key words and phrases:

edge ideals, regularity, vertex decomposable, toric ideals of graphs

###### 2000 Mathematics Subject Classification:

Primary: 13F55 Secondary: 13D02, 13H02, 14M25

##  1\. Introduction

Let $G=(V,E)$ be a finite simple graph with vertex set
$V=\\{x_{1},\ldots,x_{n}\\}$ and edge set $E=\\{e_{1},\ldots,e_{d}\\}$ ($G$ is
simple if it has no loops or multiple edges). Starting with work of Villarreal
[18], there has been much interest in studying graphs through the lens of
commutative algebra. The bridge between the two fields is via the edge ideal
construction, that is, given such a graph $G$, the edge ideal is the square-
free monomial ideal $I(G)=\langle x_{i}x_{j}~{}|~{}\\{x_{i},x_{j}\\}\in
E\rangle$ in the polynomial ring $R=k[x_{1},\ldots,x_{n}]$ with $k$ a field.
An active research program in combinatorial commutative algebra is to
understand the interaction between the two subjects; see, for example, [6, 10,
17, 20].

The purpose of this paper is to introduce and to study a family of graphs
which we call down-left graphs. This family was inspired by a construction in
the paper of Biermann, O’Keefe, and Van Tuyl [3] of graphs whose edge ideals
arise as the initial ideals of particular toric ideals. While the formal
definition (and generalization) will be given in Definition 3.1, we provide an
illustrative example that explains the name. Let $1\leq m\leq n$ be integers,
and let our vertex set be $V=\\{x_{i,j}~{}|~{}1\leq i\leq m,1\leq j\leq n\\}$.
Arrange our $mn$ vertices into an $m\times n$ grid, with vertex $x_{i,j}$ in
row $i$ and column $j$ (similar to matrix notation). We then attach vertex
$x_{i,j}$ to all vertices below and to the left of vertex $x_{i,j}$ in the
grid. The graph with $m=3$ and $n=4$, which is denoted $G(3,4)$ in our
notation, is shown in Figure 1.

$x_{3,1}$$x_{2,1}$$x_{1,1}$$x_{3,2}$$x_{2,2}$$x_{1,2}$$x_{3,3}$$x_{2,3}$$x_{1,3}$$x_{3,4}$$x_{2,4}$$x_{1,4}$
Figure 1. The down-left graph $G(3,4)$

We will consider a more general family of graphs, denoted
$G(m,n,\vec{a},\vec{b})$, where one is allowed to remove vertices of the grid
from the lower-left and upper-right corners, as described by the vectors
$\vec{a}$ and $\vec{b}$ (see Definition 3.2).

We prove that down-left graphs $G(m,n,\vec{a},\vec{b})$ satisfy a number of
nice combinatorial proprieties, which we now describe. A graph is well-covered
if all of its minimal vertex covers have the same cardinality. A graph is
$C_{5}$-free if it contains no induced subgraph isomorphic to a five cycle.
Finally, a graph is vertex decomposable if it is the graph of isolated
vertices, or if it can be constructed recursively from other vertex
decomposable graphs (see Definition 2.1). By combining our Theorems 3.8, 3.9,
and 3.10 we prove:

######  Theorem 1.1.

Let $G=G(m,n,\vec{a},\vec{b})$ be a down-left graph. Then the graph $G$ is
well-covered, $C_{5}$-free, and vertex decomposable.

Note that when $G$ is a vertex decomposable graph, the ring $R/I(G)$ is Cohen-
Macaulay, e.g., see [5, 21]. While we do not define the Cohen-Macaulay
property here, Theorem 1.1 can be seen as part of the larger program of
identifying graphs with the property that $R/I(G)$ is Cohen-Macaulay (for more
see the survey [11]).

The results of Theorem 1.1 allow us to apply a result of Khosh-Ahang and
Moradi [8] to compute the (Castelnuovo-Mumford) regularity of the associated
edge ideals of down-left graphs in terms of the invariant ${\rm im}(G)$, the
induced matching number of $G$.

######  Theorem 1.2 (Theorem 3.11).

If $G=G(m,n,\vec{a},\vec{b})$ is a down-left graph, then

${\rm reg}(R/I(G))={\rm im}(G).$

As mentioned above, the original inspiration for down-left graphs came from
the work of Biermann, O’Keefe, and Van Tuyl [3] on the regularity of toric
ideals of chordal bipartite graphs, that is, bipartite graphs with no induced
cycles of length six or larger. As an application of Theorem 1.2, we are able
to compute the regularity of toric ideas of chordal bipartite graphs that are
$(K_{3,3}\setminus e)$-free (see Theorem 4.9). For this family of graphs, this
improves upon results of [1, 3, 7] which only give upper bounds for the
regularity of toric ideals of (chordal) bipartite graphs. Note that when $G$
is a bipartite graph, then computing ${\rm reg}(R/I_{G})$, where $I_{G}$ is
the toric ideal of $G$, is equivalent to computing the $a$-invariant of
$R/I_{G}$ (e.g., see [2, Remark 2.12]). While we omit this definition, the
references [16] and [20, Section 11.5] can also be reinterpreted as results
about the regularity of toric ideals of bipartite graphs.

This paper uses the following outline. In Section 2 we recall the relevant
graph theory and commutative algebra. In Section 3 we derive our main results
about down-left graphs. In our final section, we apply our results to the
toric ideals of chordal bipartite graphs.

Acknowledgements. This project started as a Senior Research Project of
Petruccelli at McMaster University under the supervision of Van Tuyl. The
results of the project were later expanded upon by Castellano and Manivel
under the supervision of Biermann as part of an REU supported by the National
Science Foundation under grant no. DMS 1757616. Some of our results were
inspired by computer calculations using Macaulay2 [9]. Van Tuyl’s research is
supported by NSERC Discovery Grant 2019-05412.

##  2\. Preliminaries

In this section, we recall the necessary background from graph theory and
commutative algebra. Throughout this paper, $k$ denotes a field of
characteristic zero.

###  2.1. Graph theory background

Let $G=(V,E)$ denote a finite simple graph. We will write $V(G)=V$,
respectively $E(G)=E$, if we need to highlight that we are referring to the
vertices, respectively edges, of $G$.

Given a subset $W\subseteq V$, the induced graph of $G$ on $W$, denoted
$G_{W}$, is the graph $(W,E(G_{W}))$ where $E(G_{W})=\\{e\in
E(G)~{}|~{}e\subseteq W\\}$. We say that $G$ is $H$-free if there is no
induced subgraph of $G$ isomorphic to $H$. Given any edge $e\in E$ of $G$, the
graph with the edge $e$ removed is denoted $G\setminus e$. Similarly, if $x\in
V$ is a vertex, we write $G\setminus x$ to mean the graph with the vertex $x$
and all edges containing $x$ removed from $G$. Given a vertex $x\in V$, the
neighborhood of $x$ is $N(x)=\\{y~{}|~{}\\{x,y\\}\in E\\}$. The closed
neighborhood of $x$ is $N[x]=N(x)\cup\\{x\\}$. If a graph $G$ has isolated
vertices, then we write $G^{\circ}$ for the graph formed by removing all the
isolated vertices of $G$.

We require the following graphs. The $n$-cycle is the graph
$C_{n}=(\\{x_{1},\ldots,x_{n}\\},E(C_{n}))$ where
$E(C_{n})=\\{\\{x_{i},x_{i+1}\\}~{}|~{}i\in\\{1,\ldots,n-1\\}\\}\cup\\{x_{n},x_{1}\\}\\}$.
A graph $G$ is a bipartite graph if the vertex set can be partitioned as
$V=V_{1}\cup V_{2}$ such that every $e\in E$ has the property that $e\cap
V_{i}\neq\emptyset$ for $i=1,2$. The complete bipartite graph $K_{m,n}$ has
vertex set $\\{x_{1},\ldots,x_{m},y_{1},\ldots,y_{n}\\}$ and edge set
$\\{\\{x_{i},y_{j}\\}~{}|~{}1\leq i\leq m,~{}1\leq j\leq n\\}$. A chordal
bipartite graph is a bipartite graph with no induced cycles of length $\geq
6$. In Figure 2 we have drawn $C_{5}$ and $K_{3,3}\setminus e$ (where $e$
denotes any edge of $K_{3,3}$).

Figure 2. The graphs $C_{5}$ and $K_{3,3}\setminus e$

A subset of vertices $W\subseteq V$ is a vertex cover if $e\cap
W\neq\emptyset$ for all $e\in E$. If $W$ is a vertex cover, the set complement
$V\setminus W$ is a called an independent set. It has the property that
$e\not\subset(V\setminus W)$ for all $e\in E$. A vertex cover $W$ is a minimal
vertex cover if no proper subset of $W$ is a vertex cover of $G$. The
complement of a minimal vertex cover is called a maximal independent set. A
graph $G$ is well-covered if all of its minimal vertex covers (equivalently,
maximal independent sets) have the same cardinality.

A collection of edges $\\{e_{i_{1}},\ldots,e_{i_{k}}\\}$ is a matching in $G$
if the edges are pairwise disjoint. If
$e_{i_{j}}=\\{x_{i_{j},1},x_{i_{j},2}\\}$, then a matching is an induced
matching of $G$ if the induced graph on
$\\{x_{i_{1},1},x_{i_{1},2},\ldots,x_{i_{k},1},x_{i_{k},2}\\}$ is the graph
consisting only of the edges in the matching. The induced matching number of
$G$, denoted ${\rm im}(G)$, is the number of edges in the largest induced
matching of $G$.

We shall also need the notion of a vertex decomposable graph.

######  Definition 2.1.

A finite simple graph $G$ is a vertex decomposable graph if $G$ is well-
covered and either $G$ consists only of isolated vertices, or there exists a
vertex $x$ of $G$ such that $G\setminus x$ and $G\setminus N[x]$ are vertex
decomposable.

######  Remark 2.2.

The notion of vertex decomposability is originally due to Provan and Billera
[15], but was defined in terms of simplicial complexes. The independence
complex of $G$ is a simplicial complex whose faces correspond to the
independent sets of $G$. When we say a graph $G$ is vertex decomposable, we
are really saying that the independence complex of $G$ is a vertex
decomposable simplicial complex with respect to the definition of Provan and
Billera. Instead of defining the independence complex, we have defined vertex
decomposability directly in terms of the graph. The justification for this
alternate formulation can be found in Dochtermann and Engström [5] and
Woodroofe [21].

To check if a graph is vertex decomposable, it is enough to show that all the
connected components of $G$ have this property.

######  Lemma 2.3 ([21, Lemma 20]).

Suppose that the graph $G=G_{1}\sqcup G_{2}$ is the disjoint union of the
graphs $G_{1}$ and $G_{2}$. If $G_{1}$ and $G_{2}$ are vertex decomposable,
then $G$ is vertex decomposable.

###  2.2. Commutative algebra background

We now turn to the needed results from commutative algebra. If $I$ is a
homogeneous ideal of the polynomial ring $R=k[x_{1},\ldots,x_{n}]$, then there
is a minimal graded free resolution associated with $R/I$. That is, there
exists a long exact sequence of the form

$0\rightarrow\bigoplus_{j\in\mathbb{N}}R(-j)^{\beta_{p,j}(R/I)}\rightarrow\cdots\rightarrow\bigoplus_{j\in\mathbb{N}}R(-j)^{\beta_{1,j}(R/I)}\rightarrow
R\rightarrow R/I\rightarrow 0$

that is minimal with respect to the exponents on the free modules, where
$R(-j)$ is the graded $R$-module obtained by shifting the degrees of $R$ by
$j$ and where $p\leq n$. The number $\beta_{i,j}(R/I)$ is the $(i,j)$th graded
Betti number of $R/I$. For a detailed treatment see [14].

The edge ideal $I(G)$ of the graph $G$, as defined in the introduction, and
the toric ideal $I_{G}$ of a graph $G$, to be defined in Section 4, are both
homogeneous ideals. Consequently, they have a minimal graded free resolution,
and one is interested in how the graph theoretical invariants are encoded into
the graded Betti numbers. Of particular interest is the following invariant,
which is a rough measure of the complexity of $R/I$.

######  Definition 2.4.

For any homogeneous ideal $I$ of $R$, the Castelnuovo-Mumford regularity (or
regularity) of $R/I$ is

${\rm reg}(R/I)=\max\\{j-i~{}|~{}\beta_{i,j}(R/I)\neq 0\\}.$

When computing regularity of edge ideals, we can restrict to connected
components.

######  Theorem 2.5 ([11, Proposition 3.4]).

Suppose that the graph $G=G_{1}\sqcup G_{2}$ is the disjoint union of the
graphs $G_{1}$ and $G_{2}$. Then ${\rm reg}(R/I(G))={\rm reg}(R/I(G_{1}))+{\rm
reg}(R/I(G_{2})).$

The following result of Khosh-Ahang and Moradi links some of the concepts
introduced in this section. In particular, the regularity of the edge ideals
of a class of vertex decomposable graphs can be related to the induced
matching number.

######  Theorem 2.6 ([8, Theorem 2.4]).

Let $G$ be a $C_{5}$-free vertex decomposable graph. Then ${\rm
reg}(R/I(G))={\rm im}(G)$.

In Section 4, we also require the following result of Conca and Varbaro. If
$>$ is an monomial order on $R=k[x_{1},\ldots,x_{n}]$, then the initial ideal
of an ideal $I$ is the monomial ideal ${\rm in}_{>}(I)=\langle
LM_{<}(f)~{}|~{}f\in I\rangle$, where $LM_{<}(f)$ denotes the leading monomial
of $f$.

######  Theorem 2.7 ([4, Corollary 2.6]).

Let $I$ be a homogeneous ideal in $R$. Suppose there is a monomial order $>$
such that $J={\rm in}_{>}(I)$ is a square-free monomial ideal. Then ${\rm
reg}(R/I)={\rm reg}(R/J)$.

##  3\. Down-left graphs and their properties

We introduce our main object of study, down-left graphs, and study some of
their properties. In Section 4, the edge ideals of these graphs arise as the
initial ideals of toric ideals in certain cases. The properties established
here will allow us to compute the regularity of these edge ideals and hence,
of the more complicated toric ideals.

All down-left graphs will be constructed as induced subgraphs of the following
family.

######  Definition 3.1.

The graph $G(m,n)$ is the graph on vertex set $V=\\{x_{i,j}\mid 1\leq i\leq
m,1,\leq j\leq n\\}$ with edge set $E=\\{\\{x_{i,j},x_{k,\ell}\\}\mid
i<k,j>\ell\\}$.

Figure 1 shows the graph $G(3,4)$. We now define down-left graphs, which are
formed by (possibly) removing vertices in the bottom-left corner or upper-
right corner of $G(m,n)$.

######  Definition 3.2.

Let $\vec{a}=(a_{1},a_{2},\dots,a_{m})$ and
$\vec{b}=(b_{1},b_{2},\dots,b_{m})$ be vectors in $\mathbb{Z}_{\geq 0}^{m}$
such that $0=a_{1}\leq a_{2}\leq a_{3}\leq\dots\leq a_{m}<n$, $1<b_{1}\leq
b_{2}\leq\dots\leq b_{m-1}\leq b_{m}=n+1$ and $a_{i}<b_{i}$ for all $2\leq
i\leq m-1$. These sequences correspond to sets of vertices in the graph
$G(m,n)$ as follows

$\displaystyle W$
$\displaystyle=\\{x_{2,1},x_{2,2},\dots,x_{2,a_{2}},x_{3,1},x_{3,2},\dots,x_{3,a_{3}},\dots,x_{m,1},x_{m,2},\dots,x_{m,a_{m}}\\}$
$\displaystyle Z$
$\displaystyle=\\{x_{1,b_{1}},x_{1,b_{1}+1},\dots,x_{1,n},x_{2,b_{2}},x_{2,b_{2}+1}\dots,x_{2,n},\dots,x_{m-1,b_{m-1}},x_{m-1,b_{m-1}+1}\dots,x_{m-1,n}\\}.$

Note that if $a_{i}=0$, respectively $b_{j}=n+1$, the vertex $x_{i,a_{i}}$,
respectively $x_{j,b_{j}}$ is not included in $W$, respectively $Z$. The graph
$G(m,n,\vec{a},\vec{b})$ is the induced subgraph of $G(m,n)$ on the vertex set
$V(G(m,n))\setminus(W\cup Z)$. We call this class of graphs _down-left
graphs_. Note that $G(m,n)=G(m,n,\vec{0},(n+1,\ldots,n+1))$ since
$Z=W=\emptyset$.

######  Observation 3.3.

If $a_{i}+1=b_{i}$, then $Z\cup W$ contains all the vertices

$\\{x_{i,1},\ldots,x_{i,a_{i}},x_{i,a_{i}+1},\ldots,x_{i,n}\\}.$

That is, none of the vertices in the $i$-th row appear. Consequently,

$G(m,n,\vec{a},\vec{b})=G(m-1,n,(a_{1},\ldots,\hat{a}_{i},\ldots,a_{n}),(b_{1},\ldots,\hat{b}_{i},\ldots,b_{n})).$

By removing any such “empty” rows, we can assume that $a_{i}+1<b_{i}$ for all
$i$.

Similarly, if $b_{i-1}\leq a_{i}+1$, then $G$ is the disjoint union of two
down-left graphs, namely

$G(i-1,b_{i-1}-1,(a_{1},\ldots,a_{i-1}),(b_{1},\ldots,b_{i-1}))$

and

$G(m-i+1,n-a_{i},(a_{i}-a_{i},\ldots,a_{m}-a_{i}),(b_{i}-a_{i},\ldots,b_{n}-a_{i}))$

Consequently, it is enough to only consider the down-left graphs with
$b_{i-1}>a_{i}+1$.

Informally, the graph $G(m,n,\vec{a},\vec{b})$ is the graph $G(n,m)$ with
staircases of vertices (and all adjacent edges) removed from the bottom-left
and top-right portions of the graph. We include an example to illustrate this
family.

######  Example 3.4.

The graph $G(5,6,\vec{a},\vec{b})$ with $\vec{a}=(0,0,1,2,2)$ and
$\vec{b}=(5,5,6,6,7)$ is given in Figure 3. Following Definition 3.2, the sets
$W$ and $Z$ are

$W=\\{x_{2,0},x_{3,1},x_{4,1},x_{4,2},x_{5,1},x_{5,2}\\}~{}\mbox{and}~{}Z=\\{x_{1,5},x_{1,6},x_{2,5},x_{2,6},x_{3,6},x_{4,6},x_{5,7}\\}.$

We omit the vertex $x_{2,0}$ from $W$ and $x_{5,7}$ from $Z$. We then consider
the induced subgraph of $G=G(5,6)$ on the vertex set $V(G)\setminus(W\cup Z)$.
Note that we have supressed the labelling of the vertices. However, we are
assuming that vertex $x_{i,j}$ appears in the $i$th row and $j$th column of
the grid (using the convention of matrix notation). For reference, all of the
vertices of $G(5,6)$ are included; the graph $G(5,6,\vec{a},\vec{b})$ does not
include the vertices that are also in $W\cup Z$, which are denoted by the
solid black vertices. The graph $G(5,6,\vec{a},\vec{b})^{\circ}$ is the graph
we obtain by removing all the isolated vertices in Figure 3.

Figure 3. The graph $G(5,6,\vec{a},\vec{b})$ with $\vec{a}=(0,0,1,2,2)$ and
$\vec{b}=(5,5,6,6,7)$. The black vertices belong to $G(5,6)$, but not
$G(5,6,\vec{a},\vec{b})$. The graph $G(5,6,\vec{a},\vec{b})^{\circ}$ is
obtained by removing all the isolated vertices.

Informally, the vector $\vec{a}$ is describes how many vertices we remove from
each row starting from the the left, i.e., 0 vertices from row 1, 0 vertices
from row 2, 1 vertex from row 3, 2 vertices from row 4,and 2 vertices from row
5. The vector $\vec{b}$ describes where to remove vertices from the righthand
side, i.e., starting with the fifth vertex of row 1, remove all the remaining
vertices from that row, in the second row, remove the fifth vertex and all
remaining vertices in that row, and so on.

######  Remark 3.5.

We have defined a down-left graph in such a way that it always contains
isolated vertices. Indeed, the vertices $x_{1,1}$ and $x_{m,n}$ are always
isolated and there may be more isolated vertices, as seen in the previous
example.

We now prove that all down-left graphs are well-covered. We start with some
lemmas.

######  Lemma 3.6.

Let $G=G(m,n,\vec{a},\vec{b})$. Suppose that $W$ is a maximal independent set
of $G$. If $x_{i,j},x_{i,k}\in W$, then $x_{i,\ell}\in W$ for all $j<\ell<k$.
Similarly, if $x_{i,j},x_{k,j}\in W$, then $x_{\ell,j}\in W$ for all
$i<\ell<k$.

###### Proof.

Suppose $x_{i,j},x_{i,k}\in W$, and suppose that there is an integer $\ell$
such tht $j<\ell<k$. We wish to show that $x_{i,\ell}$ is also in $W$. Suppose
$x_{i,\ell}\not\in W$. Because $W$ is a maximal independent set, this would
mean that $x_{i,\ell}$ is adjacent to some vertex, say $z$, in $W$.

Now $x_{i,\ell}$ is adjacent to all the vertices below row $i$ and to the left
of column $\ell$, and to all the vertices above row $i$ and to the right of
column $\ell$. If the vertex $z$ is below row $i$ and to the left of column
$\ell<k$, then it is also adjacent to $x_{i,k}$. Since $x_{i,k}\in W$, $z$
cannot have this property. On the other hand, if $z$ is above row $i$ and to
the right of column $j<\ell$, then $z$ is also adjacent to $x_{i,j}$. But this
would mean $z$ and $x_{i,j}$ are adjacent in an independent set, which is a
contradiction. So, no such $z$ exists. Thus $x_{i,\ell}\in W$, as desired.

The second statement is proved similarly. ∎

######  Lemma 3.7.

Let $G=G(m,n,\vec{a},\vec{b})$ with $a_{i}+1<b_{i-1}$ for all $i$. Suppose
that $W$ is a maximal independent set of $G$. If $x_{i,j}\in W$ with
$(i,j)\neq(m,n)$, then exactly one of $x_{i+1,j}$ or $x_{i,j+1}$ is also in
$W$.

###### Proof.

Let $W$ be a maximal independent set of $G$ with $x_{i,j}\in W$.

We first claim that at least one of $x_{i+1,j}$ and $x_{i,j+1}$ also belong to
$V(G)$. (We need to first check this claim since these vertices may have been
removed when constructing $G$). Note that if $i=m$, then since $x_{m,n}\in
V(G)$, we must have $x_{i,j},x_{i,j+1},\ldots,x_{i,n}=x_{m,n}\in V(G)$, by the
construction of $G$. Since $(i,j)\neq(m,n)$, this means that $x_{i,j+1}\in
V(G)$. Now suppose $i<m$ and suppose neither $x_{i+1,j}$ nor $x_{i,j+1}$ are
in $V(G)$. By Observation 3.3, because $a_{i+1}+1<b_{i}\leq b_{i+1}$, there
are some vertices in the $(i+1)$-th row. If $x_{i+1,j}$ is not in $V(G)$
either $j\leq a_{i+1}$ or $j\geq b_{i+1}$. However we know that since
$x_{i,j}\in V(G)$, $j<b_{i}\leq b_{i+1}$ and thus we must have $j\leq
a_{i+1}$. On the other hand, if $x_{i,j+1}$ is not in $V(G)$, either $j+1\leq
a_{i}$ or $b_{i}\leq j+1$. Again since $x_{i,j}\in V(G)$ we know $j>a_{i}$ and
thus $j+1>a_{i}$. But then $b_{i}\leq j+1\leq a_{i+1}+1<b_{i}$, which is a
contradiction. So, at least one of $x_{i+1,j}$ and $x_{i,j+1}$ is in $V(G)$.

Note that if both of the vertices $x_{i+1,j}$ and $x_{i,j+1}$ are vertices in
$G$, then they are adjacent, since $x_{i+1,j}$ is both below and to the left
of $x_{i,j+1}$. So, at most one of these two vertices can belong to $W$.

So, suppose that neither of these two vertices belong to $W$. Since $W$ is a
maximal independent set, if we add either vertex to $W$, the set is no longer
independent, i.e., the vertex that we add is adjacent to a vertex in $W$.
Suppose we add $x_{i+1,j}$, and it is adjacent to $z\in W$. Now $z$ cannot be
below and to the left of $x_{i+1,j}$. If it was, then it is also down and left
of $x_{i,j}$, and so it would be adjacent to $z$, contradicting our assumption
that $W$ is an independent set. So, $z$ must be above and to the right of
$x_{i+1,j}$, i.e., $z=x_{r,s}$ with $r<i+1$ and $s>j$. If $r<i$, then $z$ is
above and to the right of $x_{i,j}$, so the two vertices are adjacent,
contradicting our assumption that $W$ is independent. So $z=x_{i,s}$ with
$s>j$. But then by Lemma 3.6, we must also have $x_{i,j+1}\in W$, which
contradicts our assumption that $W$ does not contain either of these two
vertices.

We derive a similar conclusion if $W$ is a maximal independent set and if we
add $x_{i,j+1}$. ∎

######  Theorem 3.8.

Every down-left graph $G=G(m,n,\vec{a},\vec{b})$ is a well-covered graph.

###### Proof.

A graph $G$ is well-covered if and only if all its connected components are
well-covered. Thus, by Observation 3.3, it is enough to show that $G$ is well-
covered when $a_{i}+1<b_{i-1}\leq b_{i}$ for all $i$. Let $W$ be a maximal
independent set of $G$. Since the vertex $x_{1,1}$ is isolated in $G$,
$x_{1,1}$ belongs to $W$. By Lemma 3.7, either $x_{2,1}$ or $x_{1,2}$ is in
$W$. If $x_{2,1}$ is in $W$, then either $x_{3,1}$ or $x_{2,2}$ is in $W$;
similarly, if $x_{1,2}\in W$, we have exactly one of $x_{2,2}$ or $x_{1,3}$ in
$W$. The process repeats until the vertex $x_{m,n}$ is shown to be part of
$W$.

In other words, each maximal independent set $W$ describes a lattice path from
the vertex $x_{1,1}$ to $x_{m,n}$, moving either right one column or down one
row at a time. No path will stop before getting to $x_{m,n}$ as shown by Lemma
3.7. The length of any such path is $m+n-1$. So, all the maximal independent
sets have the same size, i.e., the graph is well-covered. ∎

Next we will show that down-left graphs are vertex decomposable.

######  Theorem 3.9.

Every down-left graph $G(m,n,\vec{a},\vec{b})$ is vertex decomposable.

###### Proof.

Let $G=G(m,n,\vec{a},\vec{b})$ be a down-left graph. By repeatedly applying
Observation 3.3, the graph $G$ can be written as the disjoint union of smaller
down-left graphs, all with the property that that $a_{i}+1<b_{i}$ for all $i$
and $a_{i}+1<b_{i-1}$ for $i=2,\ldots,m$. By Lemma 2.3, it thus suffices to
show that a down-left graph $G$ is vertex decomposable under these extra
assumptions on $\vec{a}$ and $\vec{b}$. By Theorem 3.8, the graph $G$ is well-
covered.

We proceed by induction on the number of vertices $d$ in $G$. The base case
$d=1$, when $G$ has a single vertex, is vertex decomposable by definition.

Suppose that $G$ has $d\geq 2$ vertices and that any down-left graph with
fewer than $d$ vertices is a vertex decomposable graph. Let $i$ be the largest
index such that $a_{i}=0$ (recall that by definition, $a_{1}=0$). Let
$x=x_{i,1}$.

If $i=1$, then $x_{1,1}$ is a vertex of $G$, but $x_{2,1},\ldots,x_{m,1}$ are
not vertices of $G$ (since $1\leq a_{j}$ for $2\leq j\leq m$.). In this case
$x$ has no neighbors and so $G\setminus x$ and $G\setminus N[x]$ are both the
graph $G(m,n-1,(0,a_{2}-1,\ldots,a_{n}-1),(b_{1}-1,b_{2}-1,\dots,b_{n}-1))$.
Informally, in this case we are removing all the vertices in the first column.
By induction, this graph is vertex decomposable, so $G$ is vertex
decomposable.

Now assume that $i>1$. First consider $G\setminus x$. The graph $G\setminus x$
is of the form $G(m,n,\vec{a^{\prime}},\vec{b})$ where $\vec{a^{\prime}}$ only
differs from $\vec{a}$ in that $a^{\prime}_{i}=1$. Note that the way we chose
$x$ ensures that $a_{i}<a_{i+1}$, so $a^{\prime}_{i}\leq
a_{i+1}=a^{\prime}_{i+1}$ and thus $\vec{a^{\prime}}$ is still a non-
decreasing sequence. Further, since $i>1$, $a_{1}^{\prime}=a_{1}=0$ and since
$x_{i,1}$ is a vertex of $G$, $b_{i}\geq 2$ which means $a_{i}^{\prime}\leq
b_{i}$. This ensures that $G\setminus x=G(m,n,\vec{a^{\prime}},\vec{b})$ is a
down-left graph on $d-1$ vertices. (Note that it is possible the new down-left
graph must be first broken down into smaller down-left graphs using
Observation 3.3 to ensure the correct conditions on $\vec{a^{\prime}}$ and
$\vec{b}$; however, by induction, the smaller subgraphs are vertex
decomposable, so by Lemma 2.3, $G(m,n,\vec{a^{\prime}},\vec{b})$ is vertex
decomposable). Therefore, by induction $G\setminus x$ is vertex decomposable.

Next consider $G\setminus N[x]$. Since $x_{i,1}$ is adjacent to all vertices
to the right and above $x_{i,1}$, removing $N[x]$ is equivalent to changing
$a_{i}=0$ in $\vec{a}$ to $a_{i}=1$ and $b_{1},\ldots,b_{i-1}$ in $\vec{b}$ to
$b_{1}=\cdots=b_{i-1}=2$ in $\vec{b}$. Let $\vec{a^{\prime}}$ and
$\vec{b^{\prime}}$ denote these new new vectors. Note that $\vec{a^{\prime}}$
is still non-decreasing with $a_{1}=0$ and $\vec{b^{\prime}}$ is still non-
decreasing with $b_{m}=n+1$. Thus $G\setminus N[x]$ is the down-left graph
$G(n,m,\vec{a^{\prime}},\vec{b^{\prime}})$. By induction, this smaller down-
left graph is vertex decomposable (again, one might first need to use
Observation 3.3 to decompose this down-left graph into smaller down-left
graphs).

Consequently, $G$ is vertex decomposable, as desired. ∎

Down-left graphs also do not contain the 5-cycle as an induced subgraph.

######  Theorem 3.10.

Every down-left graph $G(m,n,\vec{a},\vec{b})$ is $C_{5}$-free.

###### Proof.

Let $G=G(n,m,\vec{a},\vec{b})$. Assume that there is an induced subgraph of
$G$ that is isomorphic to a 5-cycle. Then there is a set of five vertices
$H=\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\}\subset V(G)$ where each vertex $v_{i}$
is adjacent to exactly two others in $H$. We will denote the column of a
vertex $v_{i}$ as $n(v_{i})$ and its row as $m(v_{i})$. Without loss of
generality, let $v_{2}$ be the rightmost vertex of $H$ and the upper one in
the case more than one are in the same column.

This vertex $v_{2}$ is adjacent to two other vertices, say $v_{1}$ and
$v_{3}$, that must be down and to the left of $v_{2}$ but not adjacent to each
other (i.e., neither $v_{1}$ nor $v_{3}$ is down and to the left of the
other). Without loss of generality let $v_{1}$ be the further left and/or
upper of the two. There are three possible positions for $v_{3}$: in the same
column as $v_{1}$, in the same row as $v_{1}$, or below and to the right of
$v_{1}$, as shown in the Figure 4.

Figure 4. Three possible ways to place three vertices without an induced
triangle. Grey areas represent places that are adjacent to either $v_{1}$ or
$v_{2}$.

If $v_{1}$ and $v_{3}$ are in the same column (Figure 4 (a)), then every
vertex that is adjacent to $v_{1}$ is either up and to the right of $v_{1}$
and thus also adjacent to $v_{3}$, or down and to the left of $v_{1}$ and thus
also adjacent to $v_{2}$. This contradicts the assumption that
$\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\}$ is an induced 5-cycle.

Similarly, if $v_{1}$ and $v_{3}$ are in the same row (Figure 4 (b)), then
every vertex which is adjacent to $v_{3}$ is adjacent to either $v_{1}$ or
$v_{2}$, which is again a contradiction.

Now consider the case where $v_{1}$ and $v_{3}$ do not share a row or a column
(Figure 4 (c)). Suppose that $v_{4}$ is adjacent to $v_{3}$ and $v_{5}$ is
adjacent to $v_{1}$. Since $v_{4}$ is adjacent to $v_{3}$ but not adjacent to
$v_{2}$, $v_{4}$ must be up and to the right of $v_{3}$, but not down and to
the left of $v_{2}$. Since $v_{2}$ was assumed to be the vertex of the 5-cycle
that is furthest right and uppermost, we must have $v_{4}$ in the same column
as and below $v_{2}$. Thus $n(v_{4})=n(v_{2})$ and $m(v_{4})>m(v_{2})$.
Similarly, since $v_{5}$ is adjacent to $v_{1}$ but not adjacent to $v_{2}$ we
must have $m(v_{5})=m(v_{2})$ and $n(v_{5})<n(v_{2})$. Together these imply
that $n(v_{4})>n(v_{5})$ while $m(v_{5})<m(v_{4})$ which contradicts the fact
that $v_{4}$ and $v_{5}$ are adjacent. ∎

By combining Theorems 3.8, 3.9, and 3.10 with Theorem 2.6, we can now compute
the regularity of all down-left graphs in terms of an invariant of the graph.

######  Theorem 3.11.

If $G=G(n,m,\vec{a},\vec{b})$ is a down-left graph, then ${\rm
reg}(R/I(G))={\rm im}(G).$

######  Remark 3.12.

Let $G$ be a graph on $V=\\{x_{1},\ldots,x_{n},z\\}$ and suppose that $z$ is
an isolated vertex of $G$. Then $I(G)$ and $I(G^{\circ})$ have the same
generators, but $I(G)$ is an ideal of $R=k[x_{1},\ldots,x_{n},z]$ and
$I(G^{\circ})$ is an ideal of $S=k[x_{1},\ldots,x_{n}]$. It follows that ${\rm
reg}(R/I(G))={\rm reg}(S/I(G^{\circ}))$. Consequently, Theorem 3.11 also
applies to $G(n,m,\vec{a},\vec{b})^{\circ}$, in the appropriate polynomial
ring.

In the special case of $G(m,n)$, we can compute the regularity directly from
$m$ and $n$.

######  Theorem 3.13.

If $G=G(m,n)=G(m,n,\vec{0},(n+1,\ldots,n+1))$, then ${\rm
reg}(R/I(G))=\min\\{m-1,n-1\\}$.

###### Proof.

Because $G(m,n)\cong G(n,m)$, without loss of generality, we can assume $m\leq
n$. We first claim that

$E^{\prime}=\big{\\{}\\{x_{1,2},x_{2,1}\\},\\{x_{2,3},x_{3,2}\\},\dots,\\{x_{m-1,m},x_{m,m-1}\\}\big{\\}}\subset
E(G(m,n))$

is an induced matching of $G(m,n)$. Let $V^{\prime}$ be the set of vertices
which are endpoints of the edges in $E^{\prime}$ and let $H$ be the induced
subgraph on $V^{\prime}$.

The vertices of $H$ have the form $x_{i,i+1}$ for $i=1,\ldots,m-1$, and
$x_{j+1,j}$ for $j=1\ldots,m-1$. A vertex of the form $x_{i,i+1}$ cannot be
adjacent to any vertex of the form $x_{a,a+1}$ with $a\neq i$, since these
vertices are either above $x_{i,i+1}$ and to the left if $a<i$ and to the
right and below of $x_{i,i+1}$ if $a>i$. Similarly, none of the vertices of
the form $x_{j+1,j}$ are adjacent to each other. Finally, suppose that
$x_{i,i+1}$ is adjacent to $x_{j+1,j}$ with $i\neq j$ If $i<j$, then we would
have $i+1>j>i$. But since $i$, $j$ and $i+1$ are integers, we cannot have $j$
strictly between two consecutive integers. Similarly, if $j<i$, then
$j<i<j+1$, which gives a similar problem. So, the only induced edges on $H$
are those in $E^{\prime}$, and thus ${\rm im}(G)\geq m-1$.

Let us assume for the sake of a contradiction that there exists an induced
matching $B$ of $G(m,n)$ such that $|B|>m-1$. Given an edge
$e=\\{x_{i,j},x_{k,\ell}\\}$ of $G(m,n)$ with $i<k$, we denote $x_{i,j}$ as
the top-right vertex for the edge $e$ (since each edge has a top-right vertex
and bottom-left vertex). Observe that the $m$-th row cannot have a top-right
vertex because that would imply there is a vertex in the $(m+1)$-th or lower
row, which does not exist. As $B$ contains more than $m-1$ edges, by the
Pigeonhole Principle there exists a row of $G(m,n)$ containing at least two
top-right vertices of $B$. Suppose this is the $i$-th row. Let $x_{i,j_{1}}$
and $x_{i,j_{2}}$ be these top-right vertices with $j_{1}<j_{2}$, and let $v$
denote the vertex such that $\\{x_{i,j_{1}},v\\}\in B$. Then when we take the
induced subgraph on the vertices in $B$, since $v$ is also down and to the
left of $x_{i,j_{2}}$, we have the edge $\\{x_{i,j_{2}},v\\}$ in our induced
subgraph, in addition to all edges in $B$. Therefore, both
$\\{x_{i,j_{1}},v\\}$ and $\\{x_{i,j_{2}},v\\}$ must be edges in our induced
subgraph, but they are not disjoint, contradicting our assumption that $B$ was
an induced matching.

Consequently, we conclude that ${\rm im}(G(m,n))=m-1$ when $m\leq n$. ∎

##  4\. An application to toric ideals of graphs

In this section we exhibit a connection between down-left graphs and the toric
ideals of a special family of graphs. Given a finite simple graph $G=(V,E)$
with vertex set $V=\\{x_{1},\dots,x_{n}\\}$ and edge set
$E=\\{e_{1},\dots,e_{d}\\}$, we define polynomial rings on the vertex and edge
sets, that is, $k[V]=k[x_{1},\dots,x_{n}]$ and $k[E]=k[e_{1},\dots,e_{d}]$
where $k$ is any field. We define a monomial map $\pi:k[E]\rightarrow k[V]$ by
$e_{i}\mapsto x_{i_{1}}x_{i_{2}}$ where $e_{i}=\\{x_{i_{1}},x_{i_{2}}\\}\in
E$. The kernel of $\pi:k[E]\rightarrow k[V]$ is called the toric ideal defined
by $G$ and denoted $I_{G}$. It is well-known that the closed even walks in $G$
generate $I_{G}$ [12, 19]. In particular, the ideal $I_{G}$ is a homogeneous
prime ideal generated by binomials.

We are interested in combinatorial formulas or bounds on the regularity of the
toric ideal of a graph to build upon work of [1, 3, 7]. We will restrict to
the class of chordal bipartite graphs in order to take advantage of the
following result of Ohsugi and Hibi.

######  Theorem 4.1 ([13]).

If $G$ is a bipartite graph, then the following conditions are equivalent:

  1. (1)

$G$ is a chordal bipartite graph.

  2. (2)

the toric ideal $I_{G}$ has a quadratic Gröbner basis.

One consequence of this result is that for a chordal bipartite graph $G$, the
initial ideal of $I_{G}$ in the order of Ohsugi-Hibi is a squarefree quadratic
monomial ideal. In other words, the initial ideal of $I_{G}$ in this order is
the edge ideal of a different graph $H$ (we will construct this graph $H$
momentarily). In [3], Biermann, O’Keefe, and Van Tuyl use the graph $H$ to
give an upper bound on the regularity of $I_{G}$. Our goal in this section
will be to strengthen this upper bound to an exact calculation of the
regularity in the case when the chordal bipartite graph is also
$(K_{3,3}\setminus e)$-free.

The proof of 4.1 is constructive in that it explicitly produces an order and
the elements of the quadratic Gröbner basis in that order. The following two
results are consequences of the proof which we extract here as a lemma for
convenience. Recall that if $G$ is a bipartite graph with bipartition
$\\{x_{1},\ldots,x_{m}\\}\cup\\{y_{1},\ldots,y_{n}\\}$, the biadjacency matrix
of $G$ is an $m\times n$ matrix $M$ where $M_{i,j}=1$ if $\\{x_{i},y_{j}\\}$
is an edge, and $M_{i,j}=0$ otherwise.

######  Lemma 4.2 ([13]).

Let $G$ be a chordal bipartite graph with biadjacency matrix $M$.

  1. (1)

The rows and columns of $M$ can be rearranged so that they are simultaneously
decreasing from left to right and from top to bottom in the reverse
lexicographical order.

  2. (2)

Assume that the rows and columns of $M$ are arranged so that they are
decreasing from left to right and from top to bottom in the reverse
lexicographical order. Then there is no $2\times 2$ submatrix of $M$ of the
form

$\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}.$

Let $M$ be a biadjacency matrix of a chordal bipartite graph $G$. For the
remainder of this paper, we will assume that we have relabelled the vertices
so that the rows and columns are ordered as in Lemma 4.2 (1). Consequently, we
can relabel the edges of $G$ as $e_{i,j}$ if $M_{i,j}=1$. We now make a new
graph $H$ from the relabelled matrix $M$ as follows. The vertex set of $H$ is
$V(H)=\\{e_{i,j}~{}|~{}M_{i,j}=1\\}$ and the edge set of $H$ is

$E(H)=\left\\{\\{e_{a,d},e_{c,b}\\}~{}\left|~{}\begin{tabular}[]{l}$a<c,b<d$
and the submatrix of $M$ given by\\\ rows $a$ and $c$ and columns $b$ and $d$
is $\begin{bmatrix}1&1\\\ 1&1\end{bmatrix}$\end{tabular}\right\\}\right..$

Note that the graph $H$ is defined in terms of the biadjacency matrix.

As a consequence of Theorem 4.1, the initial ideal ${\rm in}_{<}(I_{G})$ of
$I_{G}$ is related to the edge ideal of the graph $H$. Note that this result
is implicit in [13], but made explicit in [3].

######  Theorem 4.3.

Let $G$ be a chordal bipartite graph with biadjacency matrix $M$. Let $H$ be
the graph constructed from $M$ as described above. Then there is a monomial
order $>$ on $k[E]$ such that ${\rm in}_{<}(I_{G})=I(H)$.

######  Example 4.4.

We illustrate some of the above ideas with the chordal bipartite graph given
in Figure 5. This is the same example as [3, Example 4.6].

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$y_{5}$ Figure 5. A
chordal bipartite graph

The vertex set has been partitioned as
$\\{x_{1},x_{2},x_{3},x_{4}\\}\cup\\{y_{1},y_{2},y_{3},y_{4},y_{5}\\}$. Since
the graph $G$ is a bipartite graph, the biadjacency matrix $M$ is the $4\times
5$ matrix given by

$M=\begin{bmatrix}1&1&1&0&0\\\ 1&1&1&0&0\\\ 0&1&1&1&1\\\
0&1&1&1&1\end{bmatrix}.$

By Lemma 4.2, we can relabel the $x_{i}$’s and $y_{j}$’s, so that the columns
and rows of $M$ are arranged in reverse-lexicographical order, from largest to
smallest from top to bottom and left to right. In our example, the matrix is
rearranged111There is a mistake in [3, Example 4.6]; the rows in that example
are arranged in the correct reverse lexicographical order, but the columns
were not rearranged in the correct order as:

$M=\begin{bmatrix}1&0&0&1&1\\\ 1&0&0&1&1\\\ 0&1&1&1&1\\\
0&1&1&1&1\end{bmatrix}.$

This relabelling amounts to swapping the labels of $y_{2}$ and $y_{4}$, and
those of $y_{3}$ and $y_{5}$. Note that in accordance to Lemma 4.2 (2), the
matrix has no submatrix of the form

$\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}.$

We relabel our edges so $e_{i,j}$ is connecting $x_{i}$ with $y_{j}$. Our new
labelled graph is given in Figure 6; we have surpressed some of the edge
labelling to increase readability:

$e_{1,1}$$e_{2,1}$$e_{4,5}$$e_{4,2}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$y_{5}$
Figure 6. The relabelled chordal bipartite graph with some of the edges
labelled

We now construct the graph $H$ from the matrix $M$. We place our vertices in a
$4\times 5$ grid, where vertex $e_{i,j}$ is in row $i$ and column $j$ (similar
to matrix notation). We then join $e_{a,d}$ to $e_{c,b}$ if the corresponding
submatrix of rows $a$ and $c$ and columns $b$ and $d$ consists only of ones
with $a<c$ and $b<d$. The graph $H$ is given in Figure 7.

$e_{2,1}$$e_{1,1}$$e_{4,2}$$e_{3,2}$$e_{4,3}$$e_{3,3}$$e_{4,4}$$e_{3,4}$$e_{2,4}$$e_{1,4}$$e_{4,5}$$e_{3,5}$$e_{2,5}$$e_{1,5}$
Figure 7. The graph $H$ constructed from $M$

By Theorem 4.3, there is a monomial ordering of $k[E]$ so that

${\rm in}_{<}(I_{G})=I(H)=\langle
e_{2,\,1}e_{1,\,4},\;e_{2,\,1}e_{1,\,5},\;e_{2,\,4}e_{1,\,5},\;e_{3,\,4}e_{1,\,5},\;e_{4,\,4}e_{1,\,5},\;e_{3,\,4}e_{2,\,5},\;e_{4,\,4}e_{2,\,5},\\\
e_{4,\,2}e_{3,\,3},\;e_{4,\,2}e_{3,\,4},\;e_{4,\,3}e_{3,\,4},\;e_{4,\,2}e_{3,\,5},\;e_{4,\,3}e_{3,\,5},\;e_{4,\,4}e_{3,\,5}\rangle.$

######  Remark 4.5.

The graph $H$ constructed from the biadjacency matrix $M$ of the chordal
bipartite graph $G$ is similiar to a down-left graph. In particular, if
$e_{a,d}$ and $e_{c,b}$ are adjacent, then $e_{c,b}$ is down and to the left
of $e_{a,d}$ if we place the vertices in a grid. Although similar, the graph
$H$ may not be a down-left graph. In the above example, $e_{3,3}$ is down and
left of $e_{2,4}$, but they are not adjacent since the corresponding submatrix
made from rows $2$ and $3$ and columns $3$ and $4$ contains a zero entry.
Moving forward, we want to find conditions on $M$ so that the resulting graph
$H$ is also a down-left graph.

The following is a technical lemma concerning the biadjacency matrix of a
$(K_{3,3}\setminus e)$-free chordal bipartite graph which we will need in
order to prove our main result.

######  Lemma 4.6.

Let $M$ be the $m\times n$ biadjacency matrix of a chordal bipartite $G$ that
is also $(K_{3,3}\setminus e)$-free. Assume that the columns and rows of $M$
are ordered as in Lemma 4.2 (1). Let $M^{\prime}$ be any $m^{\prime}\times
n^{\prime}$ submatrix of $M$ with $m^{\prime},n^{\prime}\geq 2$ such that the
entries of $M^{\prime}$ are all 1’s. Let $R$ be the set of indices of the rows
of $M^{\prime}$ as a submatrix of $M$ and let $C$ be the set of indices of the
columns. Let $(s,t)$ be such that

  1. (1)

$M_{s,t}=1$,

  2. (2)

either $s\notin R$ or $t\notin C$, and

  3. (3)

there is some $r\in R$ and some $c\in C$ such that either $s<r$ and $t>c$, or
$s>r$ and $t<c$ with $M_{r,c}=M_{s,c}=M_{r,t}=1$ and such that
$(r,c)\neq(\max(R),\max(C))$.

Let $M^{\prime\prime}$ be the submatrix of $M$ defined by the rows indexed by
$R\cup\\{s\\}$ and columns indexed by $C\cup\\{t\\}$. Then the entries of
$M^{\prime\prime}$ are all 1.

###### Proof.

We need to prove that all the entries of $M^{\prime\prime}$ in row $s$ and
column $t$ are non-zero. It is sufficient to show that there is one element of
row $s$ in $M^{\prime\prime}$ (other than $M_{s,t}$ and $M_{s,c}$) which is
non-zero or that there is one element of column $t$ (other than $M_{s,t}$ and
$M_{r,t}$) which is non-zero. To see this, assume without loss of generality
that there exists some $r^{\prime}\neq r$ with $r^{\prime}\in R$ such that
$M_{r^{\prime},t}=1$. Then the submatrix of $M$ induced by the rows $s$, $r$,
and $r^{\prime}$ and columns $t$, $c$, and $j$ for any $j$ in $C$ contains
eight entries equal to 1. The final entry $M_{s,j}$ must be 1 as well since
otherwise this submatrix is the biadjacency matrix of $K_{3,3}\setminus e$ and
by assumption $G$ is $(K_{3,3}\setminus e)$-free. This shows that all the
entries in row $s$ in $M^{\prime\prime}$ are equal to 1. A similar argument
can then be applied to show all the entries of $M^{\prime\prime}$ in column
$t$ are also equal to 1 and thus $M^{\prime\prime}$ is a matrix of 1’s.

Note that if either $s\in R$ or $t\in C$ then we are done since, for example,
if $s\in R$ then we know automatically that every element in row $s$ of
$M^{\prime\prime}$ is equal to 1. Then either, there are only the two rows of
$M^{\prime\prime}$ ($r$ and $s$) and we know that all the entries of
$M^{\prime\prime}$ are 1, or $M^{\prime\prime}$ has at least three rows. By
assumption, we also know that $C$ contains at least two elements and thus
$M^{\prime\prime}$ has at least three columns. By the above argument, any
remaining entries in column $t$ of $M^{\prime\prime}$ must be 1 to avoid a
$3\times 3$ submatrix of $M$ with eight entries equal to 1 and one 0.

Now suppose that $s\notin R$ and $t\notin C$. Since taking the transpose of
$M$ gives us the biadjacency matrix of an isomorphic graph, we may assume
without loss of generality that $r<s$ and $t<c$.

_Case 1:_ Suppose there exists some $j\in C$ with $j>t$ and $j\neq c$. This
implies that $M_{r,j}=1$. Then if $M_{s,j}=0$ the submatrix on rows $r$ and
$s$ and columns $t$ and $j$ contradicts Lemma 4.2. Therefore we must have
$M_{s,j}=1$. As discussed above, this is sufficient to show that
$M^{\prime\prime}$ consists of all 1’s.

_Case 2:_ If there is no $j\in C$ with $j\neq c$ and $j>t$, then this means
that columns $t$ and $c$ are the right-most two columns in $M^{\prime\prime}$.
Thus there exists some $j\in C$ with $j<c,t$.

Now suppose that there exists an $i\in R$ such that $i>r$. If $M_{i,t}=0$ then
the submatrix induced by rows $r$ and $i$ and columns $j$ and $t$ contradicts
Lemma 4.2. Therefore we must have $M_{i,t}=1$ and again by the above argument
we have all the entries in $M^{\prime\prime}$ are 1.

If on the other hand, there is no $i\in R$ such that $i>r$ then the rows $r$
and $s$ are the bottom-most rows in $M^{\prime\prime}$. This together with the
fact that columns $t$ and $c$ are the right-most in $M^{\prime\prime}$ means
that $(r,c)=(\max{R},\max{C})$ which contradicts our assumptions. ∎

######  Example 4.7.

The chordal bipartite graph of Example 4.4 is not $(K_{3,3}\setminus e)$-free
since the induced graph on $\\{x_{1},x_{2},x_{3},y_{1},y_{2},y_{3}\\}$ in
Figure 5 is a $K_{3,3}\setminus e$. We show how the biadjacency matrix does
not satisfy the previous lemma because the graph is not $(K_{3,3}\setminus
e)$-free. Note that the $2\times 2$ submatrix of rows $3$ and $4$ and columns
$3$ and $4$ consists only of ones. Thus $R=\\{3,4\\}$ and $C=\\{3,4\\}$. We
have $M_{s,t}=M_{2,5}=1$ with $s=2\notin R$ and $t=5\notin C$. Now consider
$r=3>2=s$ and $t=5>4=c$. We have $M_{3,4}=1=M_{2,4}=M_{3,5}$. So, all three
conditions of the previous lemma are met, but the conclusion is false since
the submatrix consisting of rows $R\cup\\{2\\}$ and $C\cup\\{5\\}$ has a zero
entry.

We are now prepared to prove our main theorem in this section, which says that
the graph the $H$ constructed from $G$ consists only of isolated vertices or
connected components that are down-left graphs of the form $G(m,n)$ with the
isolated vertices removed.

######  Theorem 4.8.

Let $G$ be a chordal bipartite graph, whose biadjacency matrix $M$ is ordered
as in Lemma 4.2, and let $H$ be the corresponding graph constructed from $M$.
If $G$ is also $(K_{3,3}\setminus e)$-free, then each connected component of
$H$ is either an isolated vertex or isomorphic to $G(m,n)^{\circ}$ for some
integers $m,n\geq 2$.

###### Proof.

Assume for the sake of contradiction that there is a connected component
$H^{\prime}$ of $H$ that is not an isolated vertex and is not isomorphic to
$G(m,n)^{\circ}$ for any $m,n\geq 2$. Recall that the vertices of $H^{\prime}$
correspond to 1’s in $M$. Let $M^{\prime}$ be the submatrix of $M$ that is
given by the rows and columns which contain the vertices of $H^{\prime}$.

Each edge in $H^{\prime}$ corresponds to a $2\times 2$ submatrix of
$M^{\prime}$ whose entries are all 1. Let $e$ be any edge in $H^{\prime}$ and
let $M^{\prime\prime}$ be a maximal submatrix of $M^{\prime}$ which contains
the $2\times 2$ submatrix corresponding to $e$ and whose entries are all 1.
Let $H^{\prime\prime}$ be the induced subgraph of $H^{\prime}$ on the vertices
corresponding to the entries of $M^{\prime\prime}$. Then if $M^{\prime\prime}$
is an $a\times b$ matrix, $H^{\prime\prime}$ is isomorphic to
$G(a,b)^{\circ}\cup\\{z_{1},z_{2}\\}$, where $z_{1}$ and $z_{2}$ are the two
isolated vertices of $G(a,b)$. Note that $a,b\geq 2$ since $H^{\prime}$
contains at least one edge. Since $H^{\prime}$ is a connected component of $H$
and $H^{\prime}$ contains at least one edge of $G(a,b)^{\circ}$,
$G(a,b)^{\circ}$ is a proper subgraph of $H^{\prime}$. Thus there must be some
edge $\\{v,v^{*}\\}$ in $H^{\prime}$ with $v$ a vertex of $G(a,b)^{\circ}$ and
$v^{*}$ not a vertex of $H^{\prime\prime}$.

By Lemma 4.6, all of the entries of the submatrix of $M$ which consists of
$M^{\prime\prime}$ plus the row and/or column containing $v^{*}$ are $1$. This
contradicts the fact that we chose $M^{\prime\prime}$ to be a maximal
submatrix of all $1$’s. Therefore, every component of $H$ that is not an
isolated vertex is isomorphic to $G(m,n)^{\circ}$ for some $m,n\geq 2$. ∎

Putting our results together, we can now give an exact formula for the
regularity of toric ideals of chordal bipartite graphs that are
$(K_{3,3}\setminus e)$-free.

######  Theorem 4.9.

Let $G$ be a chordal bipartite graph that is $(K_{3,3,}\setminus e)$-free, and
let $H$ be the graph constructed from the biadjancey matrix $M$ of $G$. Since
$H$ has the form $H=G(m_{1},n_{1})^{\circ}\sqcup\cdots\sqcup
G(m_{s},n_{s})^{\circ}\sqcup Y$ where $Y$ denotes the set of isolated
vertices, then

${\rm reg}(k[E]/I_{G})=\sum_{i=1}^{s}\min\\{m_{i}-1,n_{i}-1\\}.$

###### Proof.

Since the initial ideal ${\rm in}_{<}(I_{G})=I(H)$ is a square-free quadratic
monomial ideal, we know by Theorem 2.7 that ${\rm reg}(k[E]/I_{G})={\rm
reg}(k[E]/I(H))$. The result then follows from Theorem 4.8, Theorem 3.13 and
Remark 3.12, and Theorem 2.5. ∎

######  Example 4.10.

As noted in Example 4.7, our running example of Example 4.4 is not a
$(K_{3,3}\setminus e)$-free graph. In fact, any $3\times 3$ submatrix of our
biadjacency matrix with exactly eight $1$’s and one $0$ corresponds to an
induced $K_{3,3}\setminus e$.

Now remove the edges $\\{x_{2},y_{4}\\},\\{x_{3},y_{3}\\}$ and
$\\{x_{4},y_{2}\\}$ from this graph (again, using the relabeled graph) to
create the graph in Figure 8.

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$y_{5}$ Figure 8. The
relabelled chordal bipartite graph with some of the edges labelled

The new biadjacency matrix arranged in reverse-lexicographical order from
largest to smallest from top to bottom and left to right is given by

$M^{\prime}=\begin{bmatrix}1&0&0&0&1\\\ 1&0&0&1&1\\\ 0&1&0&1&1\\\
0&0&1&1&1\end{bmatrix}.$

From the matrix, we see that the new graph is still a chordal bipartite graph
and has no induced $(K_{3,3}\setminus e)$. The graph $H^{\prime}$ made from
the matrix $M^{\prime}$ is given in Figure 9.

$e_{2,1}$$e_{1,1}$$e_{3,2}$$e_{4,3}$$e_{4,4}$$e_{3,4}$$e_{2,4}$$e_{4,5}$$e_{3,5}$$e_{2,5}$$e_{1,5}$
Figure 9. The new graph $H^{\prime}$ constructed from $M^{\prime}$. This graph
is a $G(2,2)^{\circ}\sqcup G(3,2)^{\circ}$ plus five isolated vertices

Observe that $H^{\prime}$ is the disjoint union of a $G(2,2)^{\circ}$ and
$G(3,2)^{\circ}$ and some isolated vertices. Thus

${\rm reg}(R/I_{G})=\min\\{2-1,2-1\\}+\min\\{3-1,2-1\\}=2.$

## References

  * [1] A. Almousa, A. Dochtermann, B. Smith, Root polytopes, tropical types, and toric edge ideals. Preprint (2022) arXiv:2209.09851
  * [2] K. Bhaskara, A. Van Tuyl, Comparing invariants of toric ideals of bipartite graphs. Preprint (2023) arXiv:2303.14818
  * [3] J. Biermann, A. O’Keefe, and A. Van Tuyl, Bounds on the regularity of toric ideals of graphs. Adv. in Appl. Math. 85 (2017), 84–102.
  * [4] A. Conca and M. Varbaro, Square-free Gröbner degenerations. Invent. Math. 221 (2020), 713–730.
  * [5] A. Dochtermann, A. Engström, Algebraic properties of edge ideals via combinatorial topology. Electron. J. Combin. 16 (2009), no. 2, Special volume in honor of Anders Björner, Research Paper 2, 24 pp.
  * [6] J. Herzog, T. Hibi, Monomial ideals. Graduate Texts in Mathematics, 260. Springer-Verlag London, Ltd., London, 2011
  * [7] J. Herzog, T. Hibi, The regularity of edge rings and matching numbers. Mathematics 8 (2020), 103–114.
  * [8] F. Khosh-Ahang and S. Moradi, Regularity and projective dimension of the edge ideal of $C_{5}$-free vertex decomposable graphs. Proc. Amer. Math. Soc. 142 (2014), 1567–1576.
  * [9] D. R. Grayson and M. E. Stillman, Macaulay2, a software system for research in algebraic geometry. http://www.math.uiuc.edu/Macaulay2/.
  * [10] F.W. Moore, M. Rogers, S. Sather-Wagstaff, Monomial ideals and their decompositions. Universitext. Springer, Cham, 2018.
  * [11] S. Morey, R. Villarreal, Edge ideals: algebraic and combinatorial properties. Progress in commutative algebra 1, 85–126, de Gruyter, Berlin, 2012.
  * [12] H. Ohsugi and T. Hibi, Toric ideals generated by quadratic binomials. J. Algebra 218 (1999), 509–527.
  * [13] H. Ohsugi, T. Hibi, Koszul bipartite graphs. Adv. in Appl. Math. 22 (1999), 25–28.
  * [14] I. Peeva, _Graded syzygies._ Springer, London, 2011.
  * [15] J. S. Provan and L. Billera, Decompositions of simplicial compelexes related to diameters of convex polyhedra. Math. Oper. Res. 5 (1980), 576–594.
  * [16] C.E. Valencia, R. H. Villarreal, Canonical modules of certain edge subrings. European J. Combin. 24 (2003), 471–487.
  * [17] A. Van Tuyl, A beginner’s guide to edge and cover ideals. Monomial ideals, computations and applications, 63–94, Lecture Notes in Math., 2083, Springer, Heidelberg, 2013.
  * [18] R.H. Villarreal, Cohen-Macaulay graphs. Manuscripta Math. 66 (1990), 277–293.
  * [19] R.H. Villarreal, Rees algebras of edge ideals. Comm. Algebra 23 (1995), 3513–3524.
  * [20] R.H. Villarreal, _Monomial algebras_. Second edition. Monographs and Research Notes in Mathematics. CRC Press, Boca Raton, FL, 2015.
  * [21] R. Woodroofe, Vertex decomposable graphs and obstructions to shellability. Proc. Amer. Math. Soc. 137 (2009), 3235–3246.


University of Helsinki,
Finlandshahbaz.khan@helsinki.fihttps://orcid.org/0000-0001-9352-0088 Shahbaz
Khan [300]Mathematics of computing Trees [500]Theory of computation Data
compression [500]Theory of computation Pattern matching This work was funded
by the European Research Council (ERC) under the European Union’s Horizon 2020
research and innovation programme (grant agreement No. 851093, SAFEBIO).

###### Acknowledgements.

I would like to thank Alexandru I. Tomescu for helpful discussions, and for
critical review and insightful suggestions which helped me in refining the
paper. John Q. Open and Joan R. Access 2 42nd Conference on Very Important
Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging,
United Kingdom 42 23

# Optimal Construction of Hierarchical Overlap Graphs

Shahbaz Khan

###### Abstract

Genome assembly is a fundamental problem in Bioinformatics, where for a given
set of overlapping substrings of a genome, the aim is to reconstruct the
source genome. The classical approaches to solving this problem use assembly
graphs, such as de Bruijn graphs or overlap graphs, which maintain partial
information about such overlaps. For genome assembly algorithms, these graphs
present a trade-off between overlap information stored and scalability. Thus,
Hierarchical Overlap Graph (HOG) was proposed to overcome the limitations of
both these approaches.

For a given set $P$ of $n$ strings, the first algorithm to compute HOG was
given by Cazaux and Rivals [IPL20] requiring $O(||P||+n^{2})$ time using
superlinear space, where $||P||$ is the cummulative sum of the lengths of
strings in $P$. This was improved by Park et al. [SPIRE20] to $O(||P||\log n)$
time and $O(||P||)$ space using segment trees, and further to
$O(||P||\frac{\log n}{\log\log n})$ for the word RAM model. Both these results
described an open problem to compute HOG in optimal $O(||P||)$ time and space.
In this paper, we achieve the desired optimal bounds by presenting a simple
algorithm that does not use any complex data structures.

###### keywords:

Hierarchical Overlap Graphs, String algorithms, Genome assembly

###### category:

##  1 Introduction

Genome assembly is one of the oldest and most fundamental problems in
Bioinformatics [16]. Due to practical limitations, sequencing an entire genome
as a single complete string is not possible, rather a collection of the
substrings of the genome (called reads) are sequenced. The goal of a
sequencing technology is to produce a collection of reads that cover the
entire genome and have sufficient overlap amongst the reads. This allows the
source genome to be reconstructed by ordering the reads using this overlap
information. The genome assembly problem thus aims at computing the source
genome given such a collection of overlapping reads. Most approaches of genome
assembly capture this overlap information into an assembly graph, which can
then be efficiently processed to assemble the genome. The prominent approaches
use assembly graphs such as de Bruijn graphs [17] and Overlap graphs [12]
(also called string graphs [13]), which have been shown to be successfully
used is various practical assemblers [23, 3, 14, 2, 18, 19].

The de Bruijn graphs are built over $k$ length substrings (or $k$-mers) of the
reads as nodes, and arcs denoting $k-1$ length overlaps among the $k$-mers.
Their prominent advantage is that their size is linear in that of the input.
However, their limitations include losing information about the relationship
of $k$-mers with the reads, and not being able to represent overlaps of size
other than $k-1$ among the reads. On the other hand, Overlap graphs have each
read as a node, and edges between every pair of nodes represent their
corresponding maximum overlap. Though they store more overlap information than
de Bruijn graphs, they do not maintain whether two pairs of strings have the
same overlap. Moreover, they are inherently quadratic in size (except for some
specific applications [9]) and computing the edge weights (even optimally [10,
21, 11]) is difficult in practice for large data sets.

As a result, Hierarchical Overlap Graphs (HOG) were proposed in [6, 7] as an
alternative to overcome such limitations of the two types of assembly graphs.
The HOG has nodes for all the longest overlaps between every pair of strings,
and edges connecting strings to their suffix and prefix, using linear space.
Note that Overlap graphs have edges representing longest overlaps between
strings requiring quadratic size, whereas HOG has additional nodes for longest
overlaps between strings requiring linear size by exploiting pairs of strings
having the same longest overlaps. Thus, it is a promising alternative to both
de Bruijn graph and Overlap graph to better solve the problem of genome
assembly. Also, since it maintains if two pairs of strings have the same
overlap, it also has the potential to better solve the approximate shortest
superstring problem [22] having applications in both genome assembly and data
compression [20, 4]. Some applications of HOG have been studied in [6, 5].

Cazaux and Rivals [7] presented the first algorithm to build HOG efficiently.
They showed how HOG can be computed for a set of $n$ strings $P$ in
$O(||P||+n^{2})$ time, where $||P||$ represents the cummulative sum of lengths
of strings in $P$. However, they required $O(||P||+n\times\min(n,\max_{p\in
P}|p|))$ space, which is superlinear in input size. Park et al. [15] improved
it to $O(||P||\log n)$ time requiring linear space using Segment trees [8],
assuming a constant sized alphabet set. For the word RAM model, they further
improved it to $O(||P||\frac{\log n}{\log\log n})$ time. For practical
implementation, both these results build HOG using an intermediate Extended
HOG (EHOG) which reduces the memory footprint of the algorithm. Also, both
these results [7, 15] mentioned as an open problem the construction of HOG
using optimal $O(||P||)$ time and space. We answer this open question
positively using a simple algorithm, which results in the following

######  Theorem 1.1 (Optimal HOG).

For a set of strings $P$, the Hierarchical Overlap Graph can be computed using
$O(||P||)$ time and space.

Moreover, unlike [15] our algorithm does not use any complex data structures
for its implementation. Also, we do not assume any limitations on the alphabet
set. Finally, like [7, 15] our algorithm can also use EHOG as an intermediate
step for improving memory footprint in practice. Note that the size EHOG and
HOG can even be identical for some instances, but their ratio can tend to
infinity for some families of graphs [7]. Thus, despite the existence of
optimal algorithm for computing EHOG, an optimal algorithm for computing HOG
is significant from both theoretical and practical viewpoints.

#### Outline of the paper

We first describe notations and preliminaries that are used in our paper in
Section 2. In Section 3, we briefly describe the previous approaches to
compute HOG. Thereafter, Section 4 describes our core result in three stages
for simplicity of understanding, each building over the previous to give the
optimal algorithm. Finally, we present the conclusions in Section 5.

##  2 Preliminaries

Given a finite set $P=\\{p_{1},...,p_{n}\\}$ of $n$ non-empty strings over a
finite set of alphabets, we denote the size of a string $p_{i}$ by $|p_{i}|$
and the cummulative size of $P$ by $||P||=\sum_{i=1}^{n}|p_{i}|$ ($\geq n$ as
strings not empty). For a string $p$, any substring that starts from the first
character of $p$ is called a prefix of $p$, whereas any substring which ends
at the last character of $p$ is called a suffix of $p$. A prefix or suffix of
$p$ is called proper if it is not same as complete $p$. For an ordered pair of
string $(p_{1},p_{2})$, a string is called their overlap if it is both a
proper suffix of $p_{1}$ and a proper prefix of $p_{2}$, where
$ov(p_{1},p_{2})$ denotes the longest such overlap. Also, for the set of
strings $P$, $Ov(P)$ denotes the set of all $ov(p_{i},p_{j})$ for $1\leq
i,j\leq n$. An empty string is denoted by $\epsilon$. We also use the notions
of HOG, EHOG and Aho-Corasick trie as follows.

######  Definition 2.1 (Hierarchical Overlap Graph [7]).

Given a set of strings $P=\\{p_{1},\cdots,p_{n}\\}$, its Hierarchical Overlap
Graph is a directed graph ${\cal H}=(V,E)$, where

  * •

$V=P\cup Ov(P)\cup\\{\epsilon\\}$ and $E=E_{1}\cup E_{2}$, having

  * •

$E_{1}=\\{(x,y):x$ is the longest proper prefix of $y$ in $V\\}$ as tree
edges, and

  * •

$E_{2}=\\{(x,y):y$ is the longest proper suffix of $x$ in $V\\}$ as suffix
links.

Extended HOG of $P$ (referred as ${\cal E}$) is also similarly defined [7],
having additional nodes corresponding to every overlap (not just longest)
between each pair of strings in $P$, with the same definition of edges. The
construction of both these structures uses Aho-Corasick Trie [1] which is
computable in $O(||P||)$ time and space. The Aho-Corasick Trie of $P$
(referred as $\cal A$) contains all prefixes of strings in $P$ as nodes, with
the same definition for edges. All these structures are essentially trees
having the empty string $\epsilon$ as the root, and the strings of $P$ as its
leaves. A tree edge $(x,y)$ is labelled with the substring of $y$ not present
in $x$. Hence, despite being a graph due to the presence of suffix links (also
called failure links), we abuse the notions used for tree structures when
applying to $\cal A,E$ or $\cal H$ (ignoring suffix links). Also, while
referring to a node $v$ of $\cal A,E$ or $\cal H$, we represent its
corresponding string with $v$ as well.

Consider Figure 1 for a comparison of ${\cal A}$, $\cal E$ and $\cal H$ for
$P=\\{aabaa,aadbd,dbdaa\\}$. Since $\cal A$ contains all prefixes as nodes,
the tree edges have labels of a single alphabet. However, $\cal E$ contains
all overlaps among strings of $P$, so it can potentially have lesser internal
nodes ($\\{a,aa,db,dbd\\}$) than $\cal A$. Further, $\cal H$ contains only
longest overlaps so it can potentially have even lesser internal nodes
($\\{aa,dbd\\}$).

Figure 1: Given $P=\\{aabaa,aadbd,dbdaa\\}$, the figure shows from left to
right the Aho-Corasick Trie ($\cal A$), Extended Hierarchical Overlap Graph
($\cal E$) and Hierarchical Overlap Graph ($\cal H$) of $P$.

Now, to compute $\cal E$ or $\cal H$ one must only remove some internal nodes
from $\cal A$ and adjust the edge labels accordingly. This requires the
computation of all overlaps among strings in $P$ for $\cal E$, which is
further restricted to only the longest overlaps for $\cal H$. For a string
$p_{i}\in P$ (leaf of $\cal A$), all its prefixes are its ancestors in ${\cal
A}$, whereas all its suffixes are on the path following the suffix links from
it (referred as suffix path). Thus, every internal node is implicitly the
prefix of its descendant leaves, and to be an overlap it must merely be a
suffix of some string in $P$ [22]. Hence to compute internal nodes of $\cal E$
(or overlap) from $\cal A$ one simply traverses the suffix paths from all the
leaves of $\cal A$, and remove the non-traversed internal nodes (see Figure
1). However, to compute $\cal H$ from $\cal A$ (or $\cal E$) we need to find
only the longest overlaps, so we use the following criterion to identify the
internal nodes of $\cal H$.

######  Lemma 2.2.

An internal node $v$ in ${\cal A}$ (or $\cal E$) of $P$, is $ov(p_{i},p_{j})$
for two strings $p_{i},p_{j}\in P$ iff $v$ is an overlap of $(p_{i},p_{j})$
and no descendant of $v$ is an overlap of $(p_{i},p_{j})$.

######  Proof 2.3.

The ancestor of a node $v$ in ${\cal A}$ is its proper prefix and hence is
shorter than $v$. Since two internal nodes of $\cal A$ which are both overlaps
of $(p_{i},p_{j})$, they are prefixes of $p_{j}$ and hence have an ancestor-
descendant relationship, where the descendant is longer in length. Thus, the
longest overlap $ov(p_{i},p_{j})$ cannot have a descendant which is an overlap
of $(p_{i},p_{j})$.

Hence to compute $Ov(P)$ (or nodes of $\cal H$), we need to check each
internal node $v$ if it is the lowest overlap (in ${\cal A}$) for some pair
$(p_{i},p_{j})$. This implies that $v$ is a suffix of some $p_{i}$, such that
for some descendant leaf $p_{j}$, no suffix of $p_{i}$ is on path from $v$ to
$p_{j}$ (see Figure 1).

##  3 Previous results

Cazaux and Rivals [7] were the first to study $\cal H$, where they used $\cal
E$ [5] as an intermediate step in the computation of $\cal H$. They showed
that $\cal E$ can be constructed in $O(||P||)$ time and space from $\cal A$
[1], which itself is computable in $O(||P||)$ time and space. In order to
compute $\cal H$, the main bottleneck is the computation of $Ov(P)$, after
which we simply remove the internal nodes not in $Ov(P)$ from $\cal E$ (or
$\cal A$), in $O(||P||)$ time and space. They gave an algorithm to compute
$Ov(P)$ in $O(||P||+n^{2})$ time using
$O(||P||+n\times\min(n,\max\\{|p_{i}|\\}))$ space. This procedure was recently
improved by Park et al. [15] to require $O(||P||\log n)$ time and $O(||P||)$
space using segment trees, assuming constant sized alphabet set. For the word
RAM model they further improve the time to $O(||P||\frac{\log n}{\log\log
n})$. The main ideas of the previous results can be summarized as follows.

#### Computing $Ov(P)$ in $O(||P||+n^{2})$ time [7]

The algorithm computes $Ov(P)$ by considering the internal nodes in a bottom-
up manner, where a node is processed after its descendants. For each internal
node $u$, they compute the list $R_{l}(u)$ (called ${\cal L}_{u}$ in our
algorithm) of all leaves having $u$ as a suffix. Now, while processing a node
$u$, they check whether $u$ is a suffix of some leaf $v$ for which the path to
at least one of its descendant leaf (say $x$) does not have a suffix of $v$,
implying $u=ov(x,v)$. To perform this task, they maintain a bit-vector for all
leaves (suffix $v$), which is marked if no such descendant path exists from
$u$ for such leaves. For a leaf $v$, the bit is implicitly marked if all
children of $u$ have the bit for $v$ marked. Otherwise, if $v\in R_{l}(u)$ it
is marked adding $u$ to $\cal H$, else left unmarked. The space requirement is
dominated by that of this bit-vector, and it is computed only the branching
nodes, taking total $O(||P||+n^{2})$ time.

#### Computing $Ov(P)$ in $O(||P||\log n)$ time [15]

The algorithm firstly orders the strings in $P$ lexicographically in
$O(||P||)$ time (requires constant sized alphabet set). This allows them to
define an interval of leaves which are the descendants of each internal node
in $\cal E$. Now, for each leaf $u$ (suffix) they start with an unmarked array
corresponding to all leaves (prefix). Then starting from $u$ they follow its
suffix path and at each internal node $v$, check if some descendant leaf $x$
(prefix) is unmarked. In such a case $v=ov(x,u)$ and hence $v$ is added to
$\cal H$. Before moving further in the next suffix path the interval
corresponding to all the descendant leaves (prefix) of the $v$ is marked in
the array. Since both query and update (mark) over an interval can be
performed in $O(\log n)$ time using a segment tree, the total time taken is
$O(||P||\log n)$ using $O(||P||)$ space.

##  4 Our algorithm

Our main contribution is an alternate procedure to compute $Ov(P)$ in
$O(||P||)$ time and space which results in an optimal algorithm for computing
$\cal H$ for $P$ in $O(||P||)$ time and space. Our overall approach is similar
to that of the original algorithm [7] with the exception of a procedure to
mark the internal nodes that belong to $\cal H$, i.e., Mark${\cal H}$. The
algorithm except for the procedure Mark${\cal H}$ takes $O(||P||)$ time and
space (also shown in [7]). We describe our algorithm for Mark${\cal H}$ in
three stages, first for a single prefix leaf requiring $O(||P||)$ time, and
then for all prefix leaves requiring overall $O(||P||+n^{2})$ time (similar to
[7]), and finally improving it to overall $O(||P||)$ time, which is optimal.
The algorithm can be applied on any of ${\cal A}$ or $\cal E$, both computable
in $O(||P||)$ time and space.

###  4.1 Outline of Approach

We first describe our overall approach in Algorithm 1. After computing $\cal
A$, for each internal node $v$, we compute the list ${\cal L}_{v}$ of all the
leaves having $v$ as its suffix. As described earlier, this can be done by
following the suffix path of each leaf $x$, adding $x$ to ${\cal L}_{y}$ for
every internal node $y$ on the path. Using this information of suffix (in
${\cal L}_{v}$) and prefix (implicit in ${\cal A}$) we mark the nodes of $\cal
A$ to be added in the HOG $\cal H$. We shall describe this procedure Mark$\cal
H$ later on. Thereafter, in order to compute ${\cal H}$ we simply merge the
unmarked internal nodes of $\cal A$ with its parents. This process is carried
on using a DFS traversal of $\cal A$ (ignoring suffix links) where for each
unmarked internal node $v$, we move all its edges to its parent, prepending
their labels with the label of the parent edge of $v$.

${\cal A}\leftarrow$ Aho-Corasik Trie of $P$

// Trie with suffix links

foreach  _internal node $v$ of ${\cal A}$_ do ${\cal
L}_{v}\leftarrow\emptyset$ // List of leaves with suffix $v$

foreach  _leaf $x$ of ${\cal A}$_ do // Compute all ${\cal L}_{v}$

$y\leftarrow$ Suffix link of $x$ in ${\cal A}$

while  _$y\neq\epsilon$_ do // $\epsilon$ is the root of $\cal A$

Add $x$ to ${\cal L}_{y}$

$y\leftarrow$ Suffix link of $y$ in ${\cal A}$

$in{\cal H}\leftarrow$Mark${\cal H}({\cal A},{\cal L})$

// Procedure to mark nodes of ${\cal H}$ in flags $in{\cal H}$

foreach  _node $v\in{\cal A}$ in DFS order_ do // Compute ${\cal H}$

if  _$in{\cal H}[v]=0$_ then Merge $v$ with its parent

Algorithm 1 Hierarchical Overlap Graphs

As previously described, $\cal A$ can be computed in $O(||P||)$ time and space
[1]. Computing ${\cal L}_{v}$ for all $v\in{\cal A}$ requires each leaf
$p_{i}$ to follow its suffix path in $O(|p_{i}|)$ time, and add $p_{i}$ to at
most $|p_{i}|$ different ${\cal L}_{y}$, requiring total $O(||P||)$ time for
all $p_{i}\in P$. This also limits the size of ${\cal L}_{v}$ for all
$v\in\cal A$ to $O(||P||)$. Since merge operation on a node $v$ requires
$O(deg(v))$ cost, computing $\cal H$ using $in{\cal H}$ requires total
$O(|\cal A|)=O(||P||)$ time as well. Thus, we have the following theorem (also
proved in [7]).

######  Theorem 4.1.

For a set of strings $P$, the computation of Hierarchical Overlap Graph except
for Mark${\cal H}$ operation requires $O(||P||)$ time and space.

###  4.2 Marking the nodes of ${\cal H}$

We shall describe our procedure to mark the nodes of ${\cal H}$ in three
stages for simplicity of understanding. First, we shall describe how to mark
all internal nodes representing all longest overlaps $ov(\cdot,v)$ from a
single leaf $v$ (prefix) in $\cal A$, using $O(||P||)$ time. Thereafter, we
extend this to compute such overlaps from all leaves in ${\cal A}$ together
using $O(||P||+n^{2})$ time. Finally, we shall improve this to our final
procedure requiring optimal $O(||P||)$ time. All the three procedures require
$O(||P||)$ space.

Figure 2: Overlaps of $v$ with all leaves, where $c=ov(x,v)$ and $b=ov(z,v)$
are in $Ov(P)$.

#### Marking all nodes $ov(\cdot,v)$ for a leaf $v$

In order to compute all longest overlaps of a leaf $v$ (see Figure 2), we need
to consider all its prefixes (ancestors in $\cal A$) according to Lemma 2.2.
Here the internal nodes $a,b$ and $c$ are prefixes of $v$ and also suffixes of
$x$, whereas $z$ only has suffixes $a$ and $c$. Thus, we have ${\cal
L}_{a}={\cal L}_{b}=\\{x,z\\}$ and ${\cal L}_{c}=\\{x\\}$. Thus, given that
$a,b$ and $c$ are ancestors of $v$, $a$ and $b$ are valid overlaps of $(x,v)$
and $(z,v)$, whereas $c$ is only a valid overlap of $(x,v)$. Using Lemma 2.2,
for being the longest overlap of a pair of strings, no descendant should be an
overlap of the same pair of strings. Hence, $c=ov(x,v)$ and $b=ov(z,v)$, but
$a$ is not the longest overlap for any pair of strings because of $b$ and $c$.
Processing ${\cal L}_{u}$ for all nodes on the ancestors of the leaf (prefix)
requires $O(||P||)$ time. Thus, a simple way to mark all the longest overlaps
of strings with prefix $v$ in $O(||P||)$ time, is as follows:

Mark$\cal H$ for $ov(\cdot,v)$: Traverse the ancestral path of $v$ from the
root to $v$, storing the last internal node $y$ containing $x$ in ${\cal
L}_{y}$ for each leaf $x$ of $\cal A$. On reaching $v$, mark the stored
internal nodes for each $x$.

foreach  _internal node $v$ of ${\cal A}$_ do $in{\cal H}[v]\leftarrow 0$ //
Flag for membership in ${\cal H}$

foreach  _leaf $v$ of ${\cal A}$_ do $in{\cal H}[v]\leftarrow 1$ // Leaves
implicitly in ${\cal H}$

$in{\cal H}[\epsilon]\leftarrow 1$

// Root implicitly in $\cal H$

foreach  _leaf $v$ of ${\cal A}$_ do ${S}_{v}\leftarrow\emptyset$ // Stack of
exposed suffix

foreach  _node $v\in{\cal A}$ in DFS order_ do // Compute all $in{\cal H}[v]$

if  _internal node $v$ first visited_ then

foreach  _leaf $x$ in ${\cal L}_{v}$_ do Push $v$ on ${S}_{x}$

// Expose $v$ on stacks of ${\cal L}_{v}$

if  _internal node $v$ last visited_ then

foreach  _leaf $x$ in ${\cal L}_{v}$_ do Pop $v$ from $S_{x}$

// Remove $v$ from stacks of ${\cal L}_{v}$

if  _leaf $v$ visited_ then

foreach  _leaf node $x$_ do

if  _$S_{x}\neq\emptyset$_ then

$in{\cal H}[$Top of $S_{x}]\leftarrow 1$ // Mark $ov(x,v)$

Return $in{\cal H}$

Algorithm 2 Mark${\cal H}({\cal A},{\cal L})$

#### Marking all nodes in $Ov(P)$

We now describe how to perform this procedure for all leaves (prefix) together
(see Algorithm 2) using stacks to keep track of the last encountered internal
node for each leaf (suffix). The main reason behind using stacks is to avoid
processing ${\cal L}_{u}$ multiple times (for different prefixes). For each
internal node, we initialize the flag denoting membership in $\cal H$ to zero,
whereas the root and leaves of $\cal A$ are implicitly in $\cal H$. For each
leaf (suffix) we initialize an empty stack. Now, we traverse $\cal A$ in DFS
order (ignoring suffix links). As in the case for single leaf (prefix), the
stack $S_{x}$ maintains the last internal node $v$ containing a leaf $x$
(suffix) in ${\cal L}_{v}$. This node $v$ is added to the stack $S_{x}$ of the
leaf $x$ (suffix) when $v$ is first visited by the traversal, and removed from
the stack $S_{x}$ when it is last visited. This exposes the previously added
internal nodes on the stack. Finally, on visiting a leaf $v$ (prefix), each
non-empty stack $S_{x}$ of a leaf $x$ (suffix) exposes the internal node last
added on its top, which is the longest overlap $ov(x,v)$ by Lemma 2.2. We mark
such internal nodes as being present in $\cal H$. The correctness follows from
the same arguments used for the first approach.

In order to analyze the procedure we need to consider the processing of ${\cal
L}_{v}$ and $S_{x}$ for all $v,x\in{\cal A}$, in addition to traversing ${\cal
A}$. Since the total size of all ${\cal L}_{v}$ is $O(||P||)$, processing it
twice (on the first and last visit of $v$) requires $O(||P||)$ time. This also
includes the time to push and pop nodes from the stacks, requiring $O(1)$ time
while processing ${\cal L}_{v}$. However, on visiting the leaf (prefix) by the
traversal, we need to evaluate all $S_{x}$ and mark the top of non-empty
stacks. Since we consider $n$ leaves (prefix), each processing all stacks of
$n$ leaves (suffix), we require $O(n^{2})$ time. For analyzing size, we need
to consider only $S_{x}$ in addition to ${\cal L}_{v}$. Since the nodes in all
$S_{x}$ are added once from some ${\cal L}_{v}$, the total size of all stacks
$S_{x}$ is bounded by the size of all lists ${\cal L}_{v}$, i.e. $O(||P||)$
(as proved earlier). Thus, this procedure requires $O(||P||+n^{2})$ time and
$O(||P||)$ space to mark all nodes in $Ov(P)$.

foreach  _internal node $v$ of ${\cal A}$_ do $in{\cal H}[v]\leftarrow 0$ //
Flag for membership in ${\cal H}$

foreach  _leaf $v$ of ${\cal A}$_ do $in{\cal H}[v]\leftarrow 1$ // Leaves
implicitly in ${\cal H}$

$in{\cal H}[root]\leftarrow 1$

// Root implicitly in $\cal H$

foreach  _leaf $v$ of ${\cal A}$_ do ${S}_{v}\leftarrow\emptyset$ // Stack of
exposed suffix

${\cal S}\leftarrow\emptyset$

// List of stacks with unmarked tops

foreach  _leaf $v$ of ${\cal A}$_ do $in{\cal S}[v]\leftarrow 0$ // Flag for
membership of $S_{v}$ in $\cal S$

foreach  _node $v\in{\cal A}$ in inorder_ do // Compute all $in{\cal H}[v]$

if  _internal node $v$ first visited_ then

foreach  _leaf $x$ in ${\cal L}_{v}$_ do // Expose $v$ on stacks of ${\cal
L}_{v}$

Push $v$ on ${S}_{x}$

if  _$in{\cal S}[x]=0$_ then // Add $S_{x}$ to $\cal S$ if not present

$in{\cal S}[x]\leftarrow 1$

Add $S_{x}$ to ${\cal S}$

if  _internal node $v$ last visited_ then

foreach  _leaf $x$ in ${\cal L}_{v}$_ do // Remove $v$ from stacks of ${\cal
L}_{v}$

Pop $v$ from $S_{x}$

if  _$S_{x}\neq\emptyset$ and $in{\cal H}[$Top of $S_{x}]=0$ and $in{\cal
S}[x]=0$_ then

// $S_{x}$ non-empty with unmarked top and not present in $\cal S$

$in{\cal S}[x]\leftarrow 1$

Add $S_{x}$ to $\cal S$

if  _leaf $v$ visited_ then

foreach  _$S_{x}\in{\cal S}$_ do

$in{\cal H}[$Top of $S_{x}]\leftarrow 1$

// Mark $ov(x,v)$

$in{\cal S}[x]\leftarrow 0$

Remove $S_{x}$ from ${\cal S}$

// Remove $S_{x}$ with marked top from $\cal S$

Return $in{\cal H}$

Algorithm 3 Mark${\cal H}({\cal A},{\cal L})$

#### Optimizing Mark${\cal H}$

As described earlier, the only operation not bounded by $O(||P||)$ time is the
marking of internal nodes, while processing the leaves (prefix) considering
the stacks of all leaves (suffix). Note that this procedure is overkill as the
same top of the stack can be marked again when processing different leaves
(prefix), whereas total nodes entering and leaving stacks are $O(||P||)$.
Thus, we ensure that we do not have to process stacks of all leaves (suffix)
on processing the leaves (prefix) of ${\cal A}$, and instead, we only process
those stacks which were not processed earlier to mark the same top. Note that
the same internal node may be marked again when exposed in different stacks,
but we ensure that it is not marked again while processing the same stack.

Consider Algorithm 3, we maintain a list $\cal S$ of non-empty stacks whose
tops are not marked. Now, whenever a new node is added to a stack, it clearly
has an unmarked top, so is added to ${\cal S}$. And when a node is removed
from the stack, it is added to ${\cal S}$ if the new top is not previously
marked. Since ${\cal S}$ is a list, its members are additionally maintained
using flags $in{\cal S}$ for each stack corresponding to leaves (suffix) of
$\cal A$, so that the same stack is not added multiple times in $\cal S$. Now,
on processing the leaves (prefix) of ${\cal A}$, we only process the stacks in
$\cal S$, marking their tops and removing them from $\cal S$. Clearly, stacks
are added to $\cal S$ only while processing ${\cal L}_{v}$, hence overall we
can mark $O(|{\cal L}_{v}|)$ nodes for all $v$, requiring total $O(||P||)$
time. And the time taken in removing stacks from $\cal S$ is bounded by the
total size of all $S_{x}$, which is also $O(||P||)$. Thus, we can perform
Mark$\cal H$ using optimal $O(||P||)$ time and space, which results in our
main result (using Theorem 4.1).

See 1.1

##  5 Conclusions

Genome assembly is one of the most prominent problems in Bioinformatics, and
it traditionally relies on de Bruijn graphs or Overlap graphs, each having
limitations of either loss of information or quadratic space requirements.
Hierarchical Overlap Graphs provide a promising alternative that may result in
better algorithms for genome assembly. The previous results on computing these
graphs were not scalable (due to the quadratic time-bound) or required
complicated data structures (segment trees). Moreover, computing HOG in
optimal time and space was mentioned as an open problem in both the previous
results [7, 15]. We present a simple algorithm that achieves the desired
bounds, using only elementary data structures such as stacks and lists. We
hope our algorithm directly, or after further simplification, results in a
greater adaptability of HOGs in developing better genome assembly algorithms.

## References

  * [1] Alfred V. Aho and Margaret J. Corasick.  Efficient string matching: An aid to bibliographic search.  Commun. ACM, 18(6):333–340, 1975.
  * [2] Dmitry Antipov, Anton I. Korobeynikov, Jeffrey S. McLean, and Pavel A. Pevzner.  hybridspades: an algorithm for hybrid assembly of short and long reads.  Bioinform., 32(7):1009–1015, 2016.
  * [3] Anton Bankevich, Sergey Nurk, Dmitry Antipov, Alexey A. Gurevich, Mikhail Dvorkin, Alexander S. Kulikov, Valery M. Lesin, Sergey I. Nikolenko, Son K. Pham, Andrey D. Prjibelski, Alex Pyshkin, Alexander Sirotkin, Nikolay Vyahhi, Glenn Tesler, Max A. Alekseyev, and Pavel A. Pevzner.  Spades: A new genome assembly algorithm and its applications to single-cell sequencing.  J. Comput. Biol., 19(5):455–477, 2012.
  * [4] Avrim Blum, Tao Jiang, Ming Li, John Tromp, and Mihalis Yannakakis.  Linear approximation of shortest superstrings.  J. ACM, 41(4):630–647, 1994.
  * [5] Rodrigo Cánovas, Bastien Cazaux, and Eric Rivals.  The compressed overlap index.  CoRR, abs/1707.05613, 2017.
  * [6] Bastien Cazaux, Rodrigo Cánovas, and Eric Rivals.  Shortest DNA cyclic cover in compressed space.  In Ali Bilgin, Michael W. Marcellin, Joan Serra-Sagristà, and James A. Storer, editors, 2016 Data Compression Conference, DCC 2016, Snowbird, UT, USA, March 30 - April 1, 2016, pages 536–545. IEEE, 2016.
  * [7] Bastien Cazaux and Eric Rivals.  Hierarchical overlap graph.  Inf. Process. Lett., 155, 2020.
  * [8] Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars.  Computational geometry: algorithms and applications, 3rd Edition.  Springer, 2008.
  * [9] Hieu Dinh and Sanguthevar Rajasekaran.  A memory-efficient data structure representing exact-match overlap graphs with application for next-generation DNA assembly.  Bioinform., 27(14):1901–1907, 2011.
  * [10] Dan Gusfield, Gad M. Landau, and Baruch Schieber.  An efficient algorithm for the all pairs suffix-prefix problem.  Inf. Process. Lett., 41(4):181–185, 1992.
  * [11] Jihyuk Lim and Kunsoo Park.  A fast algorithm for the all-pairs suffix-prefix problem.  Theor. Comput. Sci., 698:14–24, 2017.
  * [12] Eugene W. Myers.  The fragment assembly string graph.  In ECCB/JBI, page 85, 2005.
  * [13] Eugene W. Myers.  The fragment assembly string graph.  Bioinformatics, 21(2):79–85, January 2005.  doi:10.1093/bioinformatics/bti1114.
  * [14] Sergey Nurk, Dmitry Meleshko, Anton I. Korobeynikov, and Pavel A. Pevzner.  metaspades: A new versatile de novo metagenomics assembler.  In Mona Singh, editor, Research in Computational Molecular Biology - 20th Annual Conference, RECOMB 2016, Santa Monica, CA, USA, April 17-21, 2016, Proceedings, volume 9649 of Lecture Notes in Computer Science, page 258. Springer, 2016.
  * [15] Sung Gwan Park, Bastien Cazaux, Kunsoo Park, and Eric Rivals.  Efficient construction of hierarchical overlap graphs.  In Christina Boucher and Sharma V. Thankachan, editors, String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings, volume 12303 of Lecture Notes in Computer Science, pages 277–290. Springer, 2020.
  * [16] Hannu Peltola, Hans Söderlund, Jorma Tarhio, and Esko Ukkonen.  Algorithms for some string matching problems arising in molecular genetics.  In IFIP Congress, pages 59–64, 1983.
  * [17] P. A. Pevzner.  l-Tuple DNA sequencing: computer analysis.  Journal of Biomolecular Structure & Dynamics, 7(1):63–73, August 1989.
  * [18] Pavel A. Pevzner, Haixu Tang, and Michael S. Waterman.  An eulerian path approach to dna fragment assembly.  Proceedings of the National Academy of Sciences of the United States of America, 98(17):9748–9753, 2001.
  * [19] Jared T. Simpson and Richard Durbin.  Efficient construction of an assembly string graph using the fm-index.  Bioinform., 26(12):367–373, 2010.
  * [20] Z. Sweedyk.  A 2½-approximation algorithm for shortest superstring.  SIAM J. Comput., 29(3):954–986, 1999.
  * [21] William H. A. Tustumi, Simon Gog, Guilherme P. Telles, and Felipe A. Louza.  An improved algorithm for the all-pairs suffix-prefix problem.  J. Discrete Algorithms, 37:34–43, 2016.
  * [22] Esko Ukkonen.  A linear-time algorithm for finding approximate shortest common superstrings.  Algorithmica, 5(3):313–323, 1990.
  * [23] Daniel R Zerbino and Ewan Birney.  Velvet: algorithms for de novo short read assembly using de bruijn graphs.  Genome research, 18(5):821—829, May 2008.  doi:10.1101/gr.074492.107.