arXiv:1605.06980v1 [math.AC] 23 May 2016

BOUNDS ON THE REGULARITY OF TORIC IDEALS OF GRAPHS
JENNIFER BIERMANN, AUGUSTINE O’KEEFE, AND ADAM VAN TUYL
Abstract. Let G be a finite simple graph. We give a lower bound for the CastelnuovoMumford regularity of the toric ideal IG associated to G in terms of the sizes and number
of induced complete bipartite graphs in G. When G is a chordal bipartite graph, we find
an upper bound for the regularity of IG in terms of the size of the bipartition of G. We
also give a new proof for the graded Betti numbers of the toric ideal associated to the
complete bipartite graph K2,n .

1. Introduction
The last two decades have seen a significant dictionary developed between the algebraic
invariants in the graded minimal free resolution of the edge ideal of a graph G and the
graph-theoretic invariants of G (e.g., see [11, 26]). Inspired by this work, we wish to work
towards a similar dictionary between finite graphs and their associated toric ideals.
Given a finite simple graph G = (V, E) with vertex set V = {x1 , . . . , xn } and edge set
E = {e1 , . . . , er }, we abuse notation and define the polynomial rings k[V ] = k[x1 , . . . , xn ]
and k[E] = k[e1 , . . . , er ] where k is any field. Define a monomial map π : k[E] → k[V ] by
ei 7→ xi1 xi2 where ei = {xi1 , xi2 } ∈ E. The kernel of π : k[E] → k[V ], denoted IG , is the
toric ideal defined by G. It is well-known that the generators of IG correspond to closed
even walks in G, and in particular, IG is a homogeneous ideal generated by binomials (see
[26, Theorem 8.2.2] or [17]). This construction is a specific instance of the more general
construction of toric ideals; in the general case, the ei ’s are mapped to distinct monomials
in K[V ], and the toric ideal is the kernel of the corresponding map (see [20, Chapter IV]
for more details).
Because IG is a homogeneous ideal of R = k[E], there is a graded minimal free resolution
associated with IG . That is, there exists a long exact sequence of the form
M
M
M
0→
R(−j)βp,j (IG ) →
R(−j)βp−1,j (IG ) → · · · →
R(−j)β0,j (IG ) → IG → 0
j∈N

j∈N

j∈N

where R(−j) is the graded R-module obtained by shifting the degrees of R by j and
p ≤ r. The numbers βi,j (IG ) are the (i, j)-th graded Betti numbers of IG .
2010 Mathematics Subject Classification. 13D02, 14M25, 05E40.
Key words and phrases. toric ideals, graphs, Castelnouvo-Mumford regularity, complete bipartite
graphs, chordal bipartite graphs.
Version: May 24, 2016.
1

2

JENNIFER BIERMANN, AUGUSTINE O’KEEFE, AND ADAM VAN TUYL

Ideally, one would like to describe the βi,j (IG )’s in terms of combinatorial data of G.
Some work in this direction has been carried out in [5]. In this paper, we focus on the
Castelnuovo-Mumford regularity (or regularity) of IG , that is,
reg(IG ) = max{j − i | βi,j (IG ) 6= 0}.
Our project should be seen within the context of the much broader problem of understanding the regularity of an arbitrary toric ideal; e.g, see [4] for a method to compute
the regularity of a toric ideal, and [24, Theorem 4.5] for an upper bound on the regularity
of an arbitrary toric ideal. Motivation to study the regularity of toric ideals is also partially driven by the Eisenbud-Goto conjecture which states that the regularity of these
ideals should be bounded in terms of the degree and codimension of the projective variety
defined by the toric ideal (see [9, 24]).
Our first main result is a lower bound on the regularity of IG in terms of the presence
of induced subgraphs that are isomorphic to complete bipartite graphs. Recall that the
complete bipartite graph Km,n is the graph on the vertex set {x1 , . . . , xm , y1 , . . . , yn } and
edge set E = {{xi , yj } | 1 ≤ i ≤ m, 1 ≤ j ≤ n}. We show:
Theorem 1.1 (Corollary 3.2). Let G be a finite simple graph. Suppose that G has an
induced subgraph H of the form H = Kn1 ,n1 ⊔ · · · ⊔ Knt ,nt with each ni ≥ 2. Then
reg(IG ) ≥ n1 + n2 + · · · + nt − (t − 1).
It is interesting to note that this result has a similar flavour to a result about edge ideals in
that the presence of certain induced subgraphs gives information about the regularity of
the ideal (see Remark 3.3). To prove Theorem 1.1 we use work of Aramova and Herzog [2]
that relates the multigraded Betti number βi,α (IG ) to the i-th reduced simplicial homology
of a simplicial complex Γ(α) associated to a fibre (see next section for complete details).
Our second main result is an upper bound for the regularity of toric ideals of chordal
bipartite graphs, that is, bipartite graphs which have no induced cycles of length six or
more. Using a result of Ohsugi and Hibi [18] that the toric ideal of IG for this family has
a quadratic Gröbner basis, we are able to associate with G a new graph H which has the
property that I(H), the edge ideal of H, satisfies βi,j (IG ) ≤ βi,j (I(H)) for all i, j ≥ 0. By
applying a result of Woodroofe [27] on the regularity of edge ideals, we derive an upper
bound for the regularity of I(H), and consequently, IG .
Theorem 1.2 (Theorem 4.9). Let G be a chordal bipartite graph with bipartition V =
{x1 , . . . , xn } ∪ {y1 , . . . , ym }. Let r = |{xi | deg xi = 1}| and s = |{yj | deg yj = 1}|. Then
reg(IG ) ≤ min{n − r, m − s}.
In the case that G = Km,n , our upper and lower bounds agree, thus giving reg(IKm,n ) =
min{m, n} (and recovering a special case of a result of Corso and Nagel [5]).
In the last section, we use the techniques of the previous sections to give a new combinatorial proof for the graded Betti numbers of the toric ideal of the complete graph K2,n .
Previous proofs used the Eagon-Northcott resolution, which we now avoid.

REGULARITY OF TORIC IDEALS OF GRAPHS

3

As a closing comment, G can also be associated to a binomial ideal via the binomial
edge ideal, that is, the ideal generated by all binomials of the form xi yj − xj yi in the
polynomial ring k[x1 , . . . , xn , y1 , . . . , yn ] whenever {i, j} is an edge of G. This ideal was
independently introduced in [12, 19]. For this family of binomial ideals, the programme to
link the combinatorial data of G with the graded minimal free resolution is much further
advanced; e.g., [8, 15] study the regularity of these ideals. However, the toric ideals of
this paper are rarely binomial edge ideals, so our work complements this research.
Acknowledgements. Macaulay2 [10] and CoCoA [1] were used for computer experiments.
We thank Lakehead University, Mount Holyoke College, and McMaster University for their
hospitality. The third author acknowledges the support of an NSERC Discovery Grant.
We would also like to thank Russ Woodroofe for answering some of our questions.
2. Preliminaries
We review the relevant background needed for the remainder of the paper.
A simplicial complex ∆ on a set V = {x1 , . . . , xn } is a set consisting of subsets of V
such that {xi } ∈ ∆ for all i = 1, . . . , n, and if F ∈ ∆ and G ⊆ F , then G ∈ ∆. The facets
of ∆ are the maximal elements of ∆ with respect to inclusion. We say that a simplicial
complex ∆ is generated by a list of faces σ1 , . . . , σr if every face of ∆ is contained in some
σi . In this case we write ∆ = hσ1 , . . . , σr i. If ∆1 and ∆2 are simplicial complexes on
vertex sets V1 and V2 , respectively, then the join of ∆1 and ∆2 , denoted ∆1 ⋆ ∆2 is the
simplicial complex on V1 ∪ V2 where ∆1 ⋆ ∆2 = {F1 ∪ F2 | Fi ∈ ∆i }.
The ring k[V ] = k[x1 , . . . , xn ] has a natural Nn -grading by setting the degree of xi to
be the i-th standard basis vector of Nn . The monomial map π : k[E] → k[V ] defined by
ei 7→ xi1 xi2 where ei = {xi1 , xi2 } then induces an Nn -grading on k[E]. In particular, for
any α = (a1 , . . . , an ) ∈ Nn , k[E]α = π −1 (k[V ]α ). In other words, the degree α component
consists of those elements of k[E] that map to k[V ]α . Note that k[E]α = (0) if a1 +· · ·+an
is odd because each ei is mapped to a monomial of degree two. Going forward, we write
α for both xα = xa11 · · · xann in k[x1 , . . . , xn ] and its Nn -degree. The support of a monomial
α is the set
supp(α) = {xi | xi divides α}.
For any monomial α ∈ k[x1 , . . . , xn ], the fibre of α is the set of monomials Cα = {m ∈
k[E] | π(m) = α}. From each fibre, we can construct a simplicial complex:
Definition 2.1. Let α be a monomial in k[x1 , . . . , xn ]. Define Γ(α) to be the simplicial
complex on the vertex set {e1 , . . . , er } generated by the following faces:
Γ(α) = hsupp(w) = {ei1 , . . . , eit } | w = ebi11 · · · ebitt ∈ Cα i.
The ideal IG is a homogeneous ideal in k[E] with respect to the Nn -grading described
above. As a consequence, IG has an Nn -graded minimal free resolution. The multigraded
Betti numbers of IG are related to the simplicial complexes Γ(α) via the following theorem.

4

JENNIFER BIERMANN, AUGUSTINE O’KEEFE, AND ADAM VAN TUYL

Theorem 2.2 ([2]). For any monomial α ∈ k[x1 , . . . , xn ], and any i ≥ 0
e i (Γ(α); k)),
βi,α (IG ) = dimk (H

e i (−; k) denotes the reduced simplicial homology with respect to the field k.
where H

In the statement below, if G = (V, E) is a finite simple graph and W ⊆ V , then
the induced graph on W , denoted GW , is the graph with vertex set W and edge set
{e ∈ E | e ⊆ W }.
Theorem 2.3. Let G be a finite simple graph on the vertex set V = {x1 , . . . , xn }. Let
α be a monomial in k[x1 , . . . , xn ], and suppose that α = α1 α2 with gcd(α1 , α2 ) = 1. If
Gsupp(α) = Gsupp(α1 ) ⊔ Gsupp(α2 ) , then
Γ(α) = Γ(α1 ) ⋆ Γ(α2 ).
Proof. Note that gcd(α1 , α2 ) = 1 if and only if supp(α1 ) ∩ supp(α2 ) = ∅. If F =
{ei1 , · · · , eis } ∈ Γ(α) is a facet, then there exists w = eci11 · · · eciss ∈ k[E] such that
π(w) = α. Thus for any variable eij that divides w, if eij = {xk , xl }, then {xk , xl } ∈
supp(π(w)) = supp(α). In other words, eij is an edge in the induced graph Gsupp(α) .
Because Gsupp(α) = Gsupp(α1 ) ⊔ Gsupp(α2 ) , we have that eij is an edge in either Gsupp(α1 ) or
Gsupp(α2 ) , but not both. So, after a possible relabeling, we can assume that ei1 , . . . , eit are
all edges of Gsupp(α1 ) and eit+1 , . . . , eis are all edges of Gsupp(α2 ) . We thus have
c

t+1
α = π(w) = π(eci11 · · · ecitt )π(eit+1
· · · eciss ).

c

t+1
· · · eciss )) ⊆ supp(α2 ). BeFurthermore, supp(π(eci11 · · · ecitt )) ⊆ supp(α1 ) and supp(π(eit+1
cause supp(α1 ) ∩ supp(α2 ) = ∅ and α = α1 α2 , we must have

c

t+1
· · · eciss ) = α2 .
π(eci11 · · · ecitt )) = α1 and π(eit+1

Hence ei1 · · · eit ∈ Γ(α1 ) and eit+1 · · · eis ∈ Γ(α2 ), and thus F ∈ Γ(α1 ) ⋆ Γ(α2 ).
For the reverse containment, let F1 ∈ Γ(α1 ) and F2 ∈ Γ(α2 ) be facets of Γ(α1 ) and
Γ(α2 ), respectively. So, there exists monomials w1 , w2 ∈ k[E] such that F1 = supp(w1 )
and F2 = supp(w2 ) and π(w1 ) = α1 and π(w2 ) = α2 . But then α = α1 α2 = π(w1 )π(w2 ) =
π(w) where w = w1 w2 . So supp(w) ∈ Γ(α). Note that supp(w1 ) ∩ supp(w2 ) = ∅. Indeed,
if ei ∈ supp(w1 ) ∩ supp(w2 ), then if ei = {xk , xl } we would have {xk , xl } ∈ supp(π(w1 )) ∩
supp(π(w2 )) = supp(α1 ) ∩ supp(α2 ) = ∅. So supp(w) = supp(w1 ) ∪ supp(w2 ), and thus
F1 ∪ F2 ∈ Γ(α).

Corollary 2.4. With the hypotheses as in Theorem 2.3
M
e j (Γ(α1 ); k) ⊗ H
e ℓ (Γ(α2 ); k) for all i ≥ 0.
e i (Γ(α); k) =
H
H
j+ℓ=i−1

Remark 2.5. The above result follows from the Künneth formula. Our formulation is
based upon the one found in the thesis of E. Emtander (see the bottom of page 8 in [6]).
As a consequence of the above results, lower bounds on reg(IG ) can then be found by
bounding the regularity of the toric ideals of induced subgraphs.

REGULARITY OF TORIC IDEALS OF GRAPHS

5

Theorem 2.6. Let G be a graph which contains an induced subgraph of the form H =
H1 ⊔ · · · ⊔ Ht . Then
reg(IG ) ≥ reg(IH1 ) + · · · + reg(IHt ) − t + 1.
Proof. We first note that for any graph K,
βi,j (IK ) =

X

α∈Nn ,

βi,α (IK )

|α|=2j

where |α| denotes a1 + · · · + an for α = (α1 , . . . , αn ) ∈ Nn . Note that since the homomorphism π : K[E] → K[V ] has degree two, the appropriate inner degree of the Betti
number is j not |α| = 2j.
Relabel the vertices of G so that {xℓ,1 , . . . , xℓ,nℓ } are the vertices of Hℓ for ℓ = 1, . . . , t.
If rℓ = reg(IHℓ ), then there exists an integer iℓ and a monomial αℓ with supp(αℓ ) ⊆
{xℓ,1 , . . . , xℓ,nℓ } such that βiℓ ,αℓ (IHℓ ) 6= 0 and rℓ = |α2ℓ | − iℓ . Thus, by Theorem 2.2
e i (Γ(αℓ ); k) 6= 0 for ℓ = 1, . . . , t.
H
ℓ

Set α = α1 · · · αt . It follows by repeated use of Theorem 2.3 that
Γ(α) = Γ(α1 ) ⋆ Γ(α2 ) ⋆ · · · ⋆ Γ(αt ).
Consequently, by Corollary 2.4 we will have
M
e i (Γ(α); k) =
e j1 (Γ(α1 ); k) ⊗ · · · ⊗ H
e jt (Γ(αt ); k).
(2.1)
H
H
j1 +···+jt =i−t+1

e i (Γ(α); k) 6= 0. So Theorem 2.2 implies
If i = i1 + · · · + it + (t − 1), then by (2.1) we have H
βi,α (IG ) 6= 0. Thus βi,j (IG ) 6= 0 with
2j = |α| = |α1 | + · · · + |αt | = 2(r1 + i1 ) + · · · + 2(rt + it ).

We thus get the desired inequality:
reg(IG ) = max{j − i | βi,j (IG ) 6= 0}
≥ (r1 + i1 ) + · · · + (rt + it ) − (i1 + · · · + it + (t − 1))
= reg(IH1 ) + · · · + reg(IHt ) − t + 1.

We will also need the following relationship between the graded Betti numbers of an
ideal and those of its initial ideal. See [20, Theorem 22.9] and [20, Corollary 22.13] for a
proof.
Theorem 2.7. Fix a monomial order < on R = k[x1 . . . , xn ]. Let I be a homogeneous
ideal of R, and let in< (I) denote the initial ideal of I. Then for all i, j ≥ 0
βi,j (I) ≤ βi,j (in< (I)).
Furthermore, if in< (I) has a linear resolution, then we have an equality of all i, j ≥ 0.

6

JENNIFER BIERMANN, AUGUSTINE O’KEEFE, AND ADAM VAN TUYL

3. A Lower bound on the regularity of IG
By Theorem 2.6, we can find lower bounds for reg(IG ) if we identify induced subgraphs
of G whose regularity is known. We carry out this program by finding a lower bound on
the regularity of toric ideals associated to the complete bipartite graph Kn,n .
For this section, we will find it expedient to write the vertex set of Kn,n as V =
{x1 , . . . , xn , y1, . . . , yn } and edge set as E = {ei,j = {xi , yj } | 1 ≤ i ≤ n, 1 ≤ j ≤ n}.
With this notation, our goal is to prove the following result:
Theorem 3.1. Let n ≥ 2 and α = (x1 · · · xn y1 · · · yn )n−1 . Then βn2 −2n,α (IKn,n ) 6= 0, and
consequently,
reg(IKn,n ) ≥ n.
Theorems 2.6 and 3.1 then combine to give the following main result:
Corollary 3.2. Let G be a finite simple graph. Suppose that G has an induced subgraph
H of the form H = Kn1 ,n1 ⊔ · · · ⊔ Knt ,nt with each ni ≥ 2. Then
reg(IG ) ≥ n1 + n2 + · · · + nt − (t − 1).
Remark 3.3. Corollary 3.2 has a similar “flavour” to a result about edge ideals. The edge
ideal of a graph G = (V, E) is the ideal I(G) = hxi xj | {xi , xj } ∈ Ei. Katzman [14] proved
that the induced matching number of G plus one is a lower bound for reg(I(G)). The
induced matching number is the maximum number of pairwise disjoint edges such that the
induced graph on the vertices of the edges in the matching is precisely the set of disjoint
edges. Since a disjoint edge is a K1,1 , Katzman’s result is equivalent to the statement that
if G is a graph that contains an induced subgraph of the form H = K1,1 ⊔ K1,1 ⊔ · · · ⊔ K1,1
(t copies), then reg(I(G)) ≥ t + 1.
We first outline our strategy to prove Theorem 3.1. We will focus on the simplicial complex Γ(α) when α = (x1 . . . xn y1 . . . yn )n−1 . We first show how to construct the generators
of the Stanley-Reisner ideal I(Γ(α)). Using the Taylor resolution, we then show that the
N2n -graded Betti number βn2 −n,w (I(Γ(α))) 6= 0 with w = e1,1 · · · en,n . By using Hochster’s
formula, we are then able to translate this result into a statement about the non-vanishing
e i (Γ(α); k) when i = n2 − 2n. Then Theorem 2.2 implies βn2 −2n,α (IKn,n ) 6= 0.
of H
We begin by describing the generators of the Stanley-Reisner ideal of Γ(α).

Theorem 3.4. Let G = Kn,n with n ≥ 2. If α = (x1 · · · xn y1 · · · yn )n−1 , then

I(Γ(α)) = (ei,1 ei,2 · · · ei,n | i = 1, . . . , n) + (e1,j e2,j · · · en,j | j = 1, . . . , n) ⊆ k[E].
Proof. For a fixed i ∈ {1, . . . , n}, consider the monomial ei,1 · · · ei,n ∈ k[E]. We wish
to show that ei,1 · · · ei,n ∈ I(Γ(α)), so it is enough to show that {ei,1 , . . . , ei,n } 6∈ Γ(α).
Suppose instead that {ei,1 , . . . , ei,n } ∈ Γ(α). Then there would exist a monomial w ∈ k[E]
such that π(w) = α, and furthermore {ei,1 , . . . , ei,n } ⊆ supp(w). Because xi appears in
each edge ei,j , we have xni divides π(ei,1 · · · ei,n ), which in turn divides π(w). But the

REGULARITY OF TORIC IDEALS OF GRAPHS

7

exponent of xi in π(w) is n − 1, so we get a contradiction. Thus {ei,1 , . . . , ei,n } 6∈ Γ(α).
This argument also works for all generators of the second ideal on the right hand side of
the statement. This demonstrates one containment.
For the reverse containment, let w = ei1 ,j1 · · · eit ,jt be any squarefree monomial in
I(Γ(α)). We will first show the following claim.
Claim. There is no monomial w in I(Γ(α)) such that π(w) | α.
Proof of the Claim. Suppose that such a monomial does exist and let w be a maximal
such monomial with respect to divisibility. If π(w) = α, then supp(w) ∈ Γ(α) and
hence w ∈
/ I(Γ(α)). Therefore π(w) must strictly divide α. More precisely, there exists
a1 , . . . , an , b1 , . . . , bn such that
π(w) = xa11 · · · xann y1b1 · · · ynbn | α = (x1 · · · xn y1 · · · yn )n−1
with ai , bj ≤ n − 1 for all i and j, and furthermore, at least one ai < n − 1 or bj < n − 1.
In fact, since each ei,j is a mapped to xi yj , the degrees of the xi ’s in π(w) will equal the
degree of the yi ’s. In other words, a1 + · · · + an = b1 + · · · + bn , and consequently, there
must be at least one ai < n − 1 and at least one bj < n − 1.
Because there is an edge ei,j between xi and yj ,
b +1

π(wei,j ) = xa11 · · · xiai +1 · · · xann y1b1 · · · yj j

· · · ynbn .

Note that π(wei,j ) still divides α. If π(wei,j ) = α, that would mean that supp(wei,j ) is
a facet of Γ(α) and consequently, {ei1 ,j1 , . . . , eit ,jt } ∈ Γ(α), contradicting the fact that
w ∈ I(Γ(α)). So wei,j strictly divides α, but this contradicts our choice of w.
By the claim, for any squarefree monomial w = ei1 ,j1 · · · eit ,jt ∈ I(Γ(α)), we have
π(w) ∤ α. In particular, there exists an xi (or yj ) such that xni |π(w) (or yjn |π(w)). We
assume there is an xi since the proof for the case yj is the same. So, among ei1 ,j1 , . . . , eit ,jt
there are at least n distinct edges that are adjacent to xi . But there are only n distinct
edges adjacent to xi in Kn,n , namely, ei,1 , . . . , ei,n . So w is divisible by ei,1 · · · ei,n , and so
belongs to the ideal on the right side of the statement. This now completes the proof. 
We now show that β2n−2,w (I(Γ(α))) 6= 0 with w = e1,1 · · · en,n by appealing to the theory
of cellular resolutions. For an introduction to cellular resolutions we refer the reader to
[16] or [20]. In particular we require the following definition and result.
Definition 3.5. Let ∆ be a simplicial complex whose faces are labelled by monomials,
and let w be a monomial. Then
∆<w = {σ ∈ ∆ | the label of σ strictly divides w}.
Theorem 3.6 ([16]). If I is a monomial ideal in a polynomial ring S and ∆ is a cell
complex which supports a resolution of the quotient S/I, then
e i−1 (∆<w ; k)) .
βi,w (I) = dimk (H

We will use this theorem in conjunction with Taylor’s resolution.

8

JENNIFER BIERMANN, AUGUSTINE O’KEEFE, AND ADAM VAN TUYL

Theorem 3.7 ([25]). Let I be a monomial ideal with r minimal generators in S. Then
the simplex on r vertices supports a free resolution of S/I.
Now recall that I(Γ(α)) denotes the Stanley-Reisner ideal of Γ(α). By Theorem 3.4,
I(Γ(α)) = (m1 , . . . , mn , pn+1 , . . . , pn+n )
where mi = ei,1 ei,2 · · · ei,n is the product of the edges incident to xi for 1 ≤ i ≤ n and
pn+i = e1,i e2,i · · · en,i for 1 ≤ i ≤ n is the product of edges incident to yi . Let ∆ be the
simplex on the 2n vertices {1, . . . , 2n}. By Theorem 3.7, ∆ supports a (non-minimal) free
resolution of S/I(Γ(α)) where S = k[E]. Label the faces of ∆ in the usual way. That is,
the face σ ∈ ∆ with σ = {s1 , . . . , sa , t1 , . . . , tb } is labeled by the monomial
mσ = lcm(ms1 , . . . , msa , pt1 , . . . , ptb ).
Note that the faces of ∆ naturally have the form σ = {s1 , . . . , sa , t1 , . . . , tb } where
{s1 , . . . , sa } ⊆ {1, . . . , n} and {t1 , . . . , tb } ⊆ {n + 1, . . . , 2n}.
Lemma 3.8. Let w = e1,1 e1,2 · · · en,n−1 en,n . The faces of ∆<w are exactly those of the form
σ = {s1 , . . . sa , t1 . . . tb } with {s1 , . . . , sa } ⊆ {1, . . . , n} , {t1 , . . . , tb } ⊆ {n+1, . . . , 2n}, and
1 ≤ a, b ≤ n − 1. In particular, the facets of ∆<w are given by
σi,j = {1, . . . , î . . . , n, n + 1, . . . , n[
+ j, . . . , 2n} for all 1 ≤ i, j ≤ n.
Proof. Let σ be a face of ∆<w . As noted above, σ has the form σ = {s1 , . . . , sa , t1 , . . . , tb }
where {s1 , . . . , sa } ⊆ {1, . . . , n} and {t1 , . . . , tb } ⊆ {n + 1, . . . , 2n}. It is left to prove that
a and b are both less than or equal to n − 1.
Since σ ∈ ∆<w , the label mσ of the face σ must strictly divide w. Since w is the product
of all the variables in the ring, this is equivalent to saying that there is some variable ei,j
which does not divide mσ . Since the minimal generators of I(Γ(α)) are the products of
the edges incident to each vertex in Kn,n , the variable ei,j divides exactly two of these
minimal generators, mi and pn+j . So i and n + j do not belong to σ, i.e., a, b ≤ n − 1.
Conversely, fix i and j such that 1 ≤ i, j ≤ n. Then ei,j ∤ mσi,j , so σi,j ∈ ∆<w .



We will now show that the complex ∆<w is shellable which will allow us to compute its
homology in terms of the shelling order.
Definition 3.9. A simplicial complex ∆ is shellable if there is an ordering of the facets
F1 , F2 , . . . , Ft of ∆ such that for all 1 ≤ i < ℓ ≤ t there exists some 1 ≤ j < ℓ and some
x ∈ Fℓ such that Fi ∩ Fℓ ⊆ Fj ∩ Fℓ = Fℓ \ {x}.
Theorem 3.10. Let w = e1,1 · · · en,n as in Lemma 3.8. Then ∆<w is shellable with
shelling order σ1,n+1 , σ2,n+1 , . . . , σn,n+1, σ1,n+2 , σ2,n+2 . . . , σn,n+2, . . . , σ1,2n , σ2,2n , . . . , σn,2n .
Proof. Suppose that σi1 ,i2 is earlier than σℓ1 ,ℓ2 in the shelling order. Then either i2 < ℓ2
or i2 = ℓ2 and i1 < ℓ1 . In the second case we have
+ ℓ2 . . . , 2n} = σℓ1 ,ℓ2 \ {i1 } .
σi1 ,i2 ∩ σℓ1 ,ℓ2 = {1, . . . î1 , . . . , ℓ̂1 , . . . , n, n + 1, . . . , n\

REGULARITY OF TORIC IDEALS OF GRAPHS

9

On the other hand if i2 < ℓ2 , then σℓ1 ,i2 comes earlier than σℓ1 ,ℓ2 in the shelling order and
σi1 ,i2 ∩ σℓ1 ,ℓ2 ⊆ σℓ1 ,i2 ∩ σℓ1 ,ℓ2 = σℓ1 ,ℓ2 \ {n + i2 } .
Therefore ∆<w is shellable under the given shelling order.



Corollary 3.11. Let G = Kn,n with n ≥ 2. If α = (x1 · · · xn y1 · · · yn )n−1 , then
β2n−2,w (I(Γ(α)) 6= 0 where w = e1,1 · · · en,n .
Proof. First note that ∆<w is pure of dimension 2n − 3. In the shelling order of Theorem
3.10, the intersection of the last facet in the shelling order with the earlier facets is the
entire boundary of the last facet. This means that the simplicial complex ∆<w has nonzero homology in dimension 2n − 3 (see Theorems 4.1 and 4.2 of [3]). Then by Theorem
3.6, β2n−2,w (I(Γ(α))) 6= 0.

To complete our proof of Theorem 3.1, we require Hochster’s formula which relates
the (multi)-graded Betti numbers of a simplicial complex ∆ to the reduced simplicial
homology groups of ∆ and its induced subcomplexes.
Theorem 3.12 (Hochster’s formula [13]). Let ∆ be a simplicial complex on the vertex
set V and let I(∆) be its Stanley-Reisner ideal. Then
X
e j−i−2(∆W ; k))
βi,j (I(∆)) =
dimk (H
|W |=j, W ⊆V

where ∆W is the restriction of ∆ to the vertex set W . In particular, if |V | = m then
e i (∆; k)).
βm−i−2,m (I(∆)) = dimk (H

We are now ready to prove Theorem 3.1 using the above results.
Proof. (of Theorem 3.1) Let α = (x1 · · · xn y1 · · · yn )n−1 and let w = e1,1 · · · en,n . By
Corollary 3.11 we know that the N2n -graded Betti number β2n−2,w (I(Γ(α)) 6= 0, and
therefore, the N-graded Betti number β2n−2,n2 (I(Γ(α)) 6= 0. Hochster’s formula (Theorem
e n2 −2n (Γ(α); k)) 6= 0. So by Theorem 2.2, βn2 −2n,α (IKn,n ) 6=
3.12) then implies that dimk (H
0. The multidegree α corresponds to degree n2 − n elements in the toric ideal and so

βn2 −2n,n2 −n (IKn,n ) 6= 0. Therefore reg(IKn,n ) ≥ n2 − n − (n2 − 2n) = n.
Example 3.13. We illustrate some of the ideas of this section for the graph G = K3,3 .
Let α = (x1 x2 x3 y1 y2 y3 )2 . By Theorem 3.4, the Stanley-Reisner ideal of Γ(α) is
I(Γ(α)) = (e1,1 e1,2 e1,3 , e2,1 e2,2 e2,3 , e3,1 e3,2 e3,3 , e1,1 e2,1 e3,1 , e1,2 e2,2 e3,2 , e1,3 e2,3 e3,3 )

10

JENNIFER BIERMANN, AUGUSTINE O’KEEFE, AND ADAM VAN TUYL

in the ring k[E] = k[ei,j | 1 ≤ i, j ≤ 3]. The Betti table of I(Γ(α)) is
0
6
-

0
1
2
3
4
5

1 2
- - - - 9 6 18

3
9

4
- .
1

e 3 (Γ(α); k)) 6=
We can see that the Betti number β4,9 (I(Γ(α))) 6= 0 which means that dimk (H
0. By Theorem 2.2, this means that β3,α (IK3,3 ) 6= 0, which implies that β3,6 (IK3,3 ) 6= 0.
Indeed, the Betti table of IK3,3 is
0
1
2
3

0 1 2
- - - - 9 16 9
- - -

3
- .
1

In this example, we see that reg(IK3,3 ) = 3. In fact, as we will show in the next section,
the bound reg(IKn,n ) ≥ n is actually an equality.
4. Upper bounds for chordal bipartite graphs
In this section we present an upper bound on the regularity of toric ideals associated
to a special class of bipartite graphs.
Definition 4.1. A graph is called chordal bipartite if G is a bipartite graph and G has
no induced subgraphs which are cycles of length six or larger.
The motivation behind restricting to this class of graphs is the following theorem by
Ohsugi and Hibi.
Theorem 4.2 ([17, 18]). Let G be a bipartite graph. Then the following are equivalent:
(i) G is a chordal bipartite graph.
(ii) The toric ideal IG has a Gröbner basis consisting of quadratic binomials.
To prove Theorem 4.2, Ohsugi and Hibi [17, 18] give an explicit description of the
monomial ordering which gives rise to a quadratic Gröbner basis for IG . As this ordering
will be important in our work, we take the time to define it here.
Construction 4.3 ([18]). For a chordal bipartite graph G = (V, E) with bipartition
V = V1 ∪ V2 , define AG to be the matrix with columns indexed by V2 = {y1 , . . . , ym } and
rows indexed by V1 = {x1 , . . . , xn } and the (i, j)th entry given by

1 if {xi , yj } ∈ E
(AG )i,j =
0 otherwise.

REGULARITY OF TORIC IDEALS OF GRAPHS

11

The vertices in V1 and V2 can be relabeled so that the rows and columns of AG are largest
to smallest in the reverse lexicographic order from left to right and from top to bottom
(for details see [18]). Using this relabeling, let ei,j denote the edge {xi , yj } and order the
variables of K[E] as follows: e1,1 < e1,2 < · · · < e1,m < e2,1 < · · · < e2,m < · · · < en,m .
Using the reverse lexicographic order with the variables in this order gives a quadratic
Gröbner basis of IG in k[E].
Embedded in Oshugi and Hibi’s proof of Theorem 4.2 is the following fact which we
record as a lemma.
Lemma 4.4. Let G be a chordal bipartite graph.

The matrix AG as ordered in Construc1 1
tion 4.3 has no induced submatrix of form
.
1 0
Ohsugi and Hibi go on to show that the monomial order of Construction 4.3 gives a
Gröbner basis whose elements are the binomials of the form ea,d eb,c − ea,b ec,d where a < c,
1 1
b < d and the submatrix of AG given by rows a and c and columns b and d is
.
1 1
Furthermore, the initial ideal of IG under this order is:

in< (IG ) =

*

ea,d eb,c

+
a < c, b < d, the submatrix of AG given
 by rows
1 1
.
a and c and columns b and d is
1 1

In other words,
 in< (IG ) can be determined directly from AG by identifying all submatrices
1 1
of the form
, and then the indices corresponding to the anti-diagonal of this matrix
1 1
give us a generator of in< (IG ). Note that in< (IG ) is a quadratic square-free monomial
ideal, so we can also view it as the edge ideal of some graph. We formalize this idea:
Construction 4.5. Let G = (VG , EG ) be a chordal bipartite graph, and let AG be
constructed as in Construction 4.3. Let H = (VH , EH ) be the graph with the vertex set
VH = {ei,j | (AG )i,j = 1} and edge set


EH = {ea,d , eb,c }



a < c, b < d, the submatrix of AG given
by
rows



1 1
.
a and c and columns b and d is

1 1

Equivalently, let H be the graph with edge ideal I(H) = in< (IG ).

12

JENNIFER BIERMANN, AUGUSTINE O’KEEFE, AND ADAM VAN TUYL

Example 4.6. We illustrate the above ideas with the chordal bipartite graph G:
x1

y1

x2

y2

x3

y3

x4

y4

y5

The vertex set is V = {x1 , x2 , x3 , x4 , y1 , y2, y3 , y4 , y5 }. For this graph G, the matrix AG is


1 1 1 0 0
 1 1 1 0 0

AG = 
 0 1 1 1 1 .
0 1 1 1 1

Note that under this labeling of the vertices, the rows (respectively the columns), are
ordered from largest to smallest with respect to the reverse lexicographical order from
top to bottom (respectively from left to right).
We construct the graph H from AG as follows. Replace each 1 by a vertex (keeping the
matrix like structure, i.e., vertex ei,j is position (i, j)) and remove all the zeroes. For every
2 × 2 submatrix consisting of only ones in AG , we join the two vertices corresponding to
the anti-diagonal. So, in our example, our graph H has the form:
e1,1

e1,2

e2,1 e2,2
e3,2
e4,2

e1,3
e2,3
e3,3 e3,4

e3,5

e4,3

e4,5

e4,4

Note that if we draw the graph H using the matrix AG as we did in the above example,
we can view every edge in H has having an upper-right endpoint and a lower-left endpoint.
We will use this terminology in the proof below.
Because I(H) = in< (IG ), if we can bound reg(I(H)) then a bound on reg(IG ) will follow
from Theorem 2.7. To bound reg(I(H)) we require a result of Woodroofe bounding the
regularity of an edge ideal in terms of co-chordal subgraphs of the graph.
Definition 4.7. A graph is called chordal if it has no induced subgraphs which are cycles
of length greater than three. A graph is called co-chordal if its complement is chordal. A
co-chordal cover of a graph H is a set of co-chordal subgraphs H1 , . . . , Ht of H such that

REGULARITY OF TORIC IDEALS OF GRAPHS

13

S
EH = ti=1 EHi . The co-chordal cover number of H, denoted cochord(H), is the smallest
size of a co-chordal cover of H.
Theorem 4.8 ([27]). Given a graph H with edge ideal I(H), we have
reg(I(H)) ≤ cochord(H) + 1.
We now come to the main result of this section.
Theorem 4.9. Let G be a chordal bipartite graph with bipartition V = {x1 , . . . , xn } ∪
{y1 , . . . , ym }. Let r = |{xi | deg xi = 1}| and s = |{yj | deg yj = 1}|. Then
reg(IG ) ≤ min{n − r, m − s}.
Proof. If G′ denotes the graph obtained from G by removing all the vertices of degree
one, then it follows that the toric ideals associated to G′ and G are the same. So, without
loss of generality, we can assume that G has no vertices of degree one, and that n ≤ m.
Construct H from G as in Construction 4.5. Because in< (IG ) = I(H), to prove the
bound reg(IG ) ≤ n, by Theorem 2.7 it suffices to show that reg(I(H)) ≤ n. To achieve
this goal, we will make use use of Theorem 4.8. Consequently, it suffices to produce a set
n − 1 co-chordal subgraphs of H which cover H.
For each 1 ≤ i ≤ n − 1, define Hi to be the subgraph of H with vertex set
VHi = {ea,b | ea,b ∈ VH and a ≥ i}
and edge set
EHi = {{ei,j , ek,ℓ } ∈ EH | 1 ≤ j ≤ m, k > i, ℓ < j}.
That is, Hi consists of all the edges of H whose upper-right endpoint is a vertex of the
form ei,j . So, if the vertices are positioned as in Example 4.6, i.e., vertex ei,j is in position
(i, j) where (AG )i,j = 1, then then graph Hi can be visualized as the graph where every
upper-right endpoint is on the i-th row.
Since every edge will have an upper-right endpoint of the form ea,b with 1 ≤ a ≤ n − 1,
it follows that the Hi ’s partition H. To finish the proof, it suffices to show that each Hi
is a co-chordal graph.
Fix some 1 ≤ i ≤ n − 1, and consider Hi . Every edge in Hi has its upper-right endpoint
among {ei,1 , . . . , ei,m }. (Note that not all of these vertices may appear as upper-right
endpoints. For example, if (AG )i,j = 0, then the vertex ei,j does not even appear in H.)
Every lower-left endpoint must be among the the set
{ei+1,1 , . . . , ei+1,m , ei+2,1 , . . . , ei+2,m , . . . , en,1 , . . . , en,m }.
Let V1 = VHi ∩ {ei,1 , . . . , ei,m } and V2 = VHi ∩ {ei+1,1 , . . . , ei+1,m , . . . , en,1, . . . , en,m }. By
our construction of Hi , V1 and V2 are independent sets, that is, there are no edges with
both endpoints in both V1 , respectively, V2 . Consequently, in Hic (the complement of Hi )
we have a clique on the vertices of V1 and a clique on the vertices of V2 .

14

JENNIFER BIERMANN, AUGUSTINE O’KEEFE, AND ADAM VAN TUYL

We now show that any cycle of length ≥ 4 in Hic must have a chord. For any cycle
of length ≥ 5, at least three of the vertices must be among either V1 or V2 . But since
the induced graphs on V1 and V2 in Hic are cliques, these three vertices are all mutually
adjacent, and thus the cycle has a chord.
So, now consider any cycle of length four. It must have exactly two vertices in V1 and
exactly two vertices in V2 . If not, it would have at least three vertices in V1 or V2 , and
as above, these three vertices would be mutually adjacent. Let us say that these four
vertices are ei,a , ei,b , ej,k , and er,s . Without loss of generality, we can assume that a < b.
Suppose that we have an induced four cycle on {ei,a , ei,b , ej,k , er,s }. Because ei,a ei,b ∈ Hic ,
the vertex ei,a adjacent to exactly one of ej,k and er,s in Hic . Say that ei,a ej,ℓ ∈ Hic . Thus
ei,b is adjacent to er,s in Hic , but ei,a er,s 6∈ Hic . But then ei,a er,s ∈ Hi , so s < a since
er,s must be a lower-left endpoint. But for ei,a er,s to be an edge of Hi ,and also H, the
1 1
submatrix of AG given by rows i and r and columns s and a must be
. Thus, in
1 1
the matrix AG the submatrix given by rows i and r and columns s, a, and b has the form
s a b 
i 1 1 1
j 1 1 ⋆
By Lemma 4.4, the value of ⋆ must be 1. But this means ei,b er,s is also an edge of H,
and consequently, the edge ei,b er,s 6∈ Hic . But this contradicts the fact that ei,b er,s ∈ Hic .

So Hic has no induced four cycle. Consequently, each Hi is a co-chordal subgraph.
Example 4.10. We return to our previous example. Since n = 4, if we use the notation
of the above proof, the subgraphs H1 , H2 , and H3 of H are:
e1,2
e1,1
e2,1 e2,2
e3,2
e4,2

e1,3

e1,1

e1,2

e2,3

e2,1

e2,2

e1,3
e2,3

e1,1

e1,2

e2,1

e2,2

e3,3

e3,4

e3,5

e3,2

e3,3

e3,4

e3,5

e3,2

e4,3

e4,4

e4,5

e4,2

e4,3

e4,4

e4,5

e4,2

Figure 1. Graph H1

Figure 2. Graph H2

e1,3
e2,3
e3,3 e3,4

e3,5

e4,3

e4,5

e4,4

Figure 3. Graph H3

Each of the graphs H1 , H2 , and H3 are co-chordal, that is, their complement is a chordal
graph. So reg(IG ) ≤ 3 + 1 = 4. By using Macaulay2, we actually have reg(IG ) = 4.

REGULARITY OF TORIC IDEALS OF GRAPHS

15

In some cases, the upper bound of this section agrees with the lower bound of Corollary
3.2, as in the case when G = Kn,m :
Corollary 4.11. Let G = Kn,m be a complete bipartite graph with n ≤ m. Then
reg(IG ) = n.
Remark 4.12. The above corollary is also a special case of result of [5, Proposition 5.7]
since the graph Kn,m is an example of a Ferrers graph. However, chordal bipartite graphs
are not necessarily Ferrers graphs; the example of Example 4.6 is not a Ferrers graph.
5. Betti numbers of the toric ideals IK2,d
We give a new proof for the graded Betti numbers of the toric ideals IK2,d . The matrix
AG used to construct the initial ideal of IK2,d as in Construction 4.3 is a 2 × d matrix
consisting of ones. Consequently, the graph H constructed from the initial ideal of IK2,d
will be a bipartite graph with bipartition VH = {e2 , . . . , ed } ∪ {f1 , . . . , fd−1 } with edge set
EH = {ei fj | 1 ≤ j < i ≤ d}. (For simplicity here, we have changed our notation for our
vertices using {e2 , . . . , ed , f1 , . . . , fd−1 } instead of {e1,2 , . . . , e1,d , e2,1 , . . . , e2,d−1 }). By the
next result, finding the βi,j (IK2,d )’s is equivalent to finding the Betti numbers of I(H):
Theorem 5.1. Fix some integer d ≥ 2, and consider the toric ideal IK2,d . Then IK2,d has
a linear resolution, and furthermore,
βi,i+2 (IK2,d ) = βi,i+2 (I(H)) for all i ≥ 0
where H is the graph with edge ideal I(H) = in< (IK2,d ) with < as in Construction 4.3.
Proof. The graph H is co-chordal, so by Theorem 4.8, the quadratic monomial ideal I(H)
has 2 ≤ reg(I(H)) ≤ 2. This implies that I(H) has a linear resolution, i.e., βi,j (I(H)) = 0
for j 6= i + 2. Now apply Theorem 2.7.

To compute the graded Betti numbers of the edge ideal I(H), we need the next lemma.
Lemma 5.2 ([22, Prop. 1.2]). Let G be a finite simple graph with edge ideal I(G). Then
X
βi,i+2 (I(G)) =
(#comp(GcS ) − 1) for all i ≥ 0.
S⊆V,|S|=i+2

Here, #comp(−) is the number of connected components, and Gc denotes the complement.
Putting together the above pieces, we arrive at the following formula.
Theorem 5.3. For all d ≥ 2, the graded Betti numbers of the toric ideal IK2,d are
βi,j (IK2,d ) = 0 if j 6= i + 2, and
i+1 d−2−ℓ
X
X ℓ − 1 + rd − ℓ − r 
for all i ≥ 0.
βi,i+2 (IK2,d ) =
i+2−ℓ
ℓ−1
ℓ=1 r=0

16

JENNIFER BIERMANN, AUGUSTINE O’KEEFE, AND ADAM VAN TUYL

Proof. Fix some d ≥ 2. By Theorem 5.1, it suffices to compute βi,i+2 (I(H)) for all i ≥ 0.
To compute these numbers, we can use Lemma 5.2.
Fix an i ≥ 0. For each S ⊆ V with |S| = i + 2, we wish to compute #comp(HSc ). Since
H has bipartition V = E ∪ F , if S ⊆ E or if S ⊆ F , then HSc is a complete graph, and
hence connected. Thus S does not contribute to βi,i+2 (I(H)) because #comp(HSc )−1 = 0.
So, we can assume that S ⊆ V , |S| = i + 2, S ∩ E 6= ∅, and S ∩ F 6= ∅. Because all
the ei vertices will be adjacent in HSc , and similarily, all the fj vertices will be adjacent in
HSc , we see that HSc is connected if and only if there exits an ei , fj ∈ S with i ≤ j. As we
noted above, if HSc is connected, it does not contribute to βi,i+2 (I(H)). To summarize,
we need to count the number of subsets of S ⊆ V that have the property that |S| = i + 2,
S ∩ E 6= ∅, S ∩ F 6= ∅, and if fj ∈ S, there is no ei ∈ S with i ≤ j. Note if S satisfies
these conditions, then #comp(HSc ) = 2, so each such S contributes one to βi,i+2 (I(H)).
Because the set S must contain at least one vertex of E, we can take at most i+1 vertices
from among
 the fj ’s. Fix an integer 1 ≤ ℓ ≤ i+1. Then for each r = 0, . . . , d−2−ℓ, there
ℓ−1+r
are ℓ−1 subsets T of {f1 , . . . , fd−1 } with |T | = ℓ, with fℓ+r ∈ T and for all fa ∈ T ,
a ≤ ℓ + r. To see this, pick a subset of size ℓ − 1 from {f1 , . . . , fℓ+r−1 } and then add fℓ+r .

Now consider any of the ℓ−1+r
subsets of size ℓ where ℓ + r is the largest index of a
ℓ−1
vertex among the fj ’s. In order to make a subset S of size i + 2 from this set that has
the property that Hsc is not connected, we then need to pick i + 2 − ℓ of the remaining
vertices among {eℓ+r−1 , . . . , ed }.  So, we have to pick i + 2 − ℓ things among d − r − ℓ
d−r−ℓ
things. This gives us then ℓ−1+r
possible subsets. Now summing over all ℓ and r
ℓ−1
i+2−ℓ
gives the desired formula.

Remark 5.4. It is known (e.g., [26, Proposition 9.1.2]) that when G = Ka,b , then IG is
generated by the 2 × 2 minors of a generic a × b matrix. One could deduce the graded
Betti numbers of IG using the Eagon-Northcott resolution ([7]) for 2 × 2 minors of generic
matrices. Our proof gives a combinatorial argument for the graded Betti numbers.
References
[1] J. Abbott, A.M. Bigatti, G. Lagorio, CoCoA-5: a system for doing Computations in Commutative
Algebra. Available at http://cocoa.dima.unige.it
[2] A. Aramova, J. Herzog, Koszul cycles and Eliahou-Kervaire type resolutions. J. Algebra 181 (1996),
347–370.
[3] A. Björner, M. Wachs, Shellable nonpure complexes and posets. I. Trans. Amer. Math. Soc. 348
(1996), 1299–1327.
[4] E. Briales-Morales, P. Pisón-Casares, A. Vigneron-Tenorio, The regularity of a toric variety. J.
Algebra 237 (2001), 165–185.
[5] A. Corso, U. Nagel, Monomial and toric ideals associated to Ferrers graphs. Trans. Amer. Math.
Soc. 361 (2009), 1371-1395.
[6] E. Emtander, Chordal and Complete Structures in Combinatorics and Commutative Algebra. PhD
Thesis, Stockholm University, 2010.
[7] J. Eagon, D. G. Northcott, Ideals defined by matrices and a certain complex associated to them.
Proc. Roy. Soc. Ser. A 269 (1962), 188-204.

REGULARITY OF TORIC IDEALS OF GRAPHS

17

[8] V. Ene, A. Zarojanu, On the regularity of binomial edge ideals. Math. Nachr. 288 (2015), 19–24.
[9] D. Eisenbud, S. Goto, Linear free resolutions and minimal multiplicity. J. Algebra 88 (1984), 89–133.
[10] D. R. Grayson and M. E. Stillman, Macaulay2, a software system for research in algebraic geometry.
http://www.math.uiuc.edu/Macaulay2/
[11] J. Herzog, T. Hibi, Monomial Ideals. Springer, 2011.
[12] J. Herzog, T. Hibi, F. Hreinsdotir, T. Kahle, J. Rauh, Binomial edge ideals and conditional independence statements. Adv. Appl. Math. 45 (2010), 317–333.
[13] M. Hochster, Cohen-Macaulay rings, combinatorics, and simplicial complexes. Proc. of the 2nd
Oklahoma Conf., Lecture Notes in Pure Appl. Math. 26 (1977) Marcel Dekker, 171–224.
[14] M. Katzman, Characteristic-independence of Betti numbers of graph ideals. J. Combin. Theory Ser.
A 113 (2006), 435–454.
[15] K. Matsuda, S. Murai, Regularity bounds for binomial edge ideals. J. Commut. Algebra 5 (2013),
141–149.
[16] E. Miller, B. Sturmfels, Combinatorial Commutative Algebra. Springer, 2005.
[17] H. Ohsugi, T. Hibi, Toric ideals generated by quadratic binomials. J. Algebra 218 (1999), 509-527.
[18] H. Ohsugi, T. Hibi, Koszul bipartite graphs. Adv. in Appl. Math. 22 (1999), 25–28.
[19] M. Ohtami, Graphs and ideals generated by some 2-minors. Commun. Algebra 39 (2011), 905–917.
[20] I. Peeva, Graded Syzygies. Springer, 2010.
[21] E. Reyes, C. Tatakis, A. Thoma, Minimal generators of toric ideals of graphs. Adv. in Appl. Math.
48 (2012), 64–78.
[22] M. Roth, A. Van Tuyl, On the linear strand of an edge ideal. Comm. Algebra 35 (2007), 821–832.
[23] B. Sturmfels, Gröbner bases and convex polytopes. Amer. Math. Soc., 1995.
[24] B. Sturmfels, Equations defining toric varieties. Algebraic geometry-Santa Cruz 1995, 437–449, Proc.
Sympos. Pure Math., 62, Part 2, Amer. Math. Soc., Providence, RI, 1997.
[25] D. Taylor, Ideals generated by monomials in an R-sequence. PhD. Thesis, University of Chicago,
1966.
[26] R.H. Villarreal, Monomial algebras. Marcel Dekker, Inc., New York, 2001.
[27] R. Woodroofe, Matchings, coverings, and Castelnuovo-Mumford regularity. J. Commut. Algebra 6
(2014), 287-304.
Department of Mathematics and Statistics,, Mount Holyoke College, South Hadley,
MA 01705
E-mail address: jbierman@mtholyoke.edu
Mathematics Department Connecticut College Mathematics Department 270 Mohegan
Avenue New London, CT 06320
E-mail address: aokeefe@conncoll.edu
Department of Mathematics & Statistics, McMaster University, Hamilton, ON, L8S
4L8, Canada
E-mail address: vantuyl@math.mcmaster.ca

