arXiv:1603.01850v1 [] 6 Mar 2016

TORIC RINGS AND IDEALS OF STABLE SET POLYTOPES
KAZUNORI MATSUDA, HIDEFUMI OHSUGI AND KAZUKI SHIBATA
Abstract. In this paper, we discuss the normality of the toric rings of stable set
polytopes, and the set of generators and Gröbner bases of toric ideals of stable
set polytopes by using the results on that of edge polytopes of finite nonsimple
graphs. In particular, for a graph of stability number two, we give a graph theoretical characterization of the set of generators of the toric ideal of the stable set
polytope, and a criterion to check whether the toric ring of the stable set polytope
is normal or not. One of the application of the results is an infinite family of stable
set polytopes whose toric ideal is generated by quadratic binomials and has no
quadratic Gröbner bases.

Introduction
Let P ⊂ Rn be an integral convex polytope, i.e., a convex polytope each of whose
vertices has integer coordinates, and let P ∩ Zn = {a1 , . . . , am }. Let K[X, X −1 , t] =
K[x1 , x1−1 , . . . , xn , x−1
n , t] be the Laurent polynomial ring in n + 1 variables over a
field K. Given an integer vector a = (a1 , . . . , an ) ∈ Zn , we set X a t = xa11 · · · xann t ∈
K[X, X −1 , t]. Then, the toric ring of P is the subalgebra K[P] of K[X, X −1 , t]
generated by {X a1 t, . . . , X am t} over K. We regard K[P] as a homogeneous algebra
by setting each deg X ai t = 1. The toric ideal IP of P is the kernel of a surjective
homomorphism π : K[y1 , . . . , ym ] → K[P] defined by π(yi ) = X ai t for 1 ≤ i ≤ m.
It is known that IP is generated by homogeneous binomials and reduced Gröbner
bases of IP consist of homogeneous binomials. See, e.g., [20]. The following properties on an integral convex polytope P have been investigated by many papers on
commutative algebra and combinatorics:
(i) P is unimodular, i.e., any triangulation of P is unimodular
(The initial ideal of IP is generated by squarefree monomials with respect to
any monomial order);
(ii) P is compressed, i.e., any “pulling” triangulation is unimodular
(The initial ideal of IP is generated by squarefree monomials with respect to
any reverse lexicographic order);
(iii) P has a regular unimodular triangulation
(There exists a monomial order such that the initial ideal of IP is generated
by squarefree monomials);
(iv) P has a unimodular triangulation;
(v) P has a unimodular covering;
(vi) P is normal, i.e., K[P] is normal.
Key words and phrases. toric ideals, Gröbner bases, graphs, stable set polytopes.
1

The hierarchy (i) ⇒ (ii) ⇒ (iii) ⇒ (iv) ⇒ (v) ⇒ (vi) is known. See, e.g., [20] for
details. However, the converse of each of the five implications is false. On the other
hand, the following properties on IP are studied by many authors:
(a) IP has a quadratic Gröbner bases;
(b) K[P] is Koszul algebra;
(c) IP is generated by quadratic binomials.
The hierarchy (a) ⇒ (b) ⇒ (c) is known. However, the converse of each of the two
implications is false. See, e.g., [13, Examples 2.1 and 2.2] and [21].
The purpose of this paper is to study such properties of toric rings and ideals of
stable set polytopes of simple graphs. Let G be a finite simple graph on the vertex
set [n] = {1, 2, . . . , n} and let E(G) denote the set
P of edges ofn G. Given a subset
W ⊂ [n], we associate the (0, 1)-vector ρ(W ) = j∈W ej ∈ R . Here, ei is the ith
unit coordinate vector of Rn . In particular, ρ(∅) is the origin of Rn . A subset W
is called stable if {i, j} ∈
/ E(G) for all i, j ∈ W with i 6= j. Note that the empty
set and each single-element subset of [n] are stable. Let S(G) denote the set of all
stable sets of G. The stable set polytope (independent set polytope) of a simple graph
G is the (0, 1)-polytope QG ⊂ Rn which is the convex full of {ρ(W ) : W ∈ S(G)}.
Stable set polytopes are very important in many areas, e.g., optimization theory.
On the other hand, several results are known for the toric ring K[QG ] and ideals
IQG of the stable set polytope QG of a simple graph G.
(1) For a graph G, the stable set polytope QG is compressed if and only if G is
perfect ([5, 15, 22]).
(2) For a perfect graph G, the toric ring K[QG ] is Gorenstein if and only if all
maximal cliques of G have the same cardinality ([16]).
(3) For a graph G, K[QG ] is strongly Koszul if and only if G is trivially perfect
([7, Theorem 5.1]).
(4) Let G(P ) be a comparability graph of a poset P . Then, QG(P ) is called a
chain polytope of P . It is known that the toric ideals of a chain polytope has
a squarefree quadratic initial ideal (see [6, Corollary 3.1]). For example, if a
graph G is bipartite, then there exists a poset P such that G = G(P ).
(5) Suppose that a graph G on the vertex set [n] is an almost bipartite graph,
i.e., there exists a vertex v such that the induced subgraph of G on the vertex
set [n] \ {v} is bipartite. Then, IQG has a squarefree quadratic initial ideal
([2, Theorem 8.1]). For example, any cycle is almost bipartite.
(6) Let G be the complement of even cycle of length 2k. Then, the maximum
degree of a minimal set of binomial generators of IQG is equal to k ([2,
Theorem 7.4]).
In the present paper, we study the normality of the toric rings of stable set polytopes,
and the set of generators and Gröbner bases of toric ideals of stable set polytopes by
using the results on that of edge polytopes of finite (nonsimple) graphs. Here, the
edge polytope PG ⊂ Rn of a graph G allowing loops and having no multiple edges is
the convex full of
{ei + ej : {i, j} is an edge of G} ∪ {2ei : there is a loop at i in G}.
2

This paper is organized as follows. In Section 1, fundamental properties of K[QG ]
and IQG are studied. In particular, the relationship between the stable set polytopes
and the edge polytopes are given (Lemma 1.7). In addition, it is shown that QG is
unimodular if and only if the complement of G is bipartite (Proposition 1.8). We
also point out that, by the results in [2], it is easy to see that IQG has a squarefree
quadratic initial ideal if G is either a chordal graph or a ring graph (Proposition
1.4). In Section 2, we discuss the normality of the stable set polytopes. We prove
that, for a simple graph G of stability number two, QG is normal if and only if
the complement of G satisfies the “odd cycle condition” (Theorem 2.1). Using this
criterion, we construct an infinite family of normal stable set polytopes without
regular unimodular triangulations (Theorem 2.2). For general simple graphs, some
necessary conditions for QG to be normal are also given. In Section 3, we study
the set of generators and Gröbner bases of toric ideals of stable set polytopes. It
is shown that, for a simple graph G of stability number two, the set of binomial
generators of IQG is described by the even closed walk of a graph (Theorem 3.2).
If G is bipartite and if IQG is generated by quadratic binomials, then IQG has a
quadratic Gröbner basis (Corollary 3.4). Finally, using the results on normality,
generators, and Gröbner bases, we give an infinite family of nonnormal stable set
polytopes whose toric ideal is generated by quadratic binomials and has no quadratic
Gröbner bases (Theorem 2.2).
1. Fundamental properties of the stable set polytopes
In this section, we give some fundamental properties of K[QG ] and IQG . In particular, a relation between the stable set polytopes and the edge polytopes is discussed.
The stability number α(G) of a graph G is the cardinality of the largest stable set.
Example 1.1. If a simple graph G satisfies α(G) = 1, i.e., G is a complete graph,
then IQG = {0}, K[QG ] = K[x1 t, . . . , xn t, t] ≃ K[y1 , . . . , yn+1 ], and QG is a simplex.
Example 1.2. Suppose that a simple graph G is not connected. Let G1 , . . . , Gs be
connected components of G. Then, it is easy to see that K[QG ] is isomorphic to the
Segre product of K[QG1 ], . . . , K[QGs ].
Thus, it is enough to study stable set polytopes of connected simple graphs G
such that α(G) ≥ 2. The notion of toric fiber products [23] is a generalization of the
Segre product. It is known [2] that we can apply the theory of toric fiber products
to the toric rings of stable set polytopes. For i = 1, 2, let Gi be a simple graph on
the vertex set Vi and the edge set Ei . If V1 ∩ V2 is a clique of both G1 and G2 , then
we construct a new graph G1 ♯G2 on the vertex set V1 ∪ V2 and the edge set E1 ∪ E2
which is called the clique sum of G1 and G2 along V1 ∩ V2 .
Proposition 1.3. Let G1 ♯G2 be the clique sum of simple graphs G1 and G2 . Then,
IQG1 ♯G2 is a toric fiber product of IQG1 and IQG2 . We can construct a set of binomial
generators (or a Gröbner basis) of IQG1 ♯G2 from that of IQGi ’s and some quadratic
binomials. Moreover, K[QG1 ♯G2 ] is normal if and only if both K[QG1 ] and K[QG2 ]
are normal.
3

Proof. This is a special case of [2, Proposition 5.1]. Note that IQG1 ∩G2 = {0}.



A simple graph G is called chordal if any induced cycle of G is of length 3. A ring
graph is a graph whose block which is not a bridge or a vertex can be constructed from
a cycle by successively adding cycles of length ≥ 3 using the edge sum construction.
Ring graphs are introduced in [3, 4] and the toric ideals of cut polytopes of ring
graphs are studied in [8].
Proposition 1.4. Suppose that a simple graph G is either a chordal graph or a ring
graph. Then, IQG has a squarefree quadratic initial ideal.
Proof. It is known that a graph G is chordal if and only if G is a clique sum of
complete graphs. By the statement in Example 1.1 and Proposition 1.3, IQG has a
squarefree quadratic initial ideal if G is chordal.
Suppose that G is a ring graph. Then, G is a clique sum of trees and cycles.
Since trees and cycles are almost bipartite, by [2, Theorem 8.1], the toric ideal IQH
has a squarefree quadratic initial ideal if H is either a tree or a cycle. Thus, by
Proposition 1.3, IQG has a squarefree quadratic initial ideal if G is a ring graph. 
A graph G is called perfect if the chromatic number of every induced subgraph of
G equals the size of the largest clique of that subgraph. See, e.g., [1]. The following
is known ([5, 15, 22]).
Proposition 1.5. Let G be a simple graph. Then, QG is compressed if and only if
G is perfect. In particular, if G is perfect, then QG is normal.
For a graph G on the vertex set [n], let G denote the complement of a graph G.
An induced cycle of G of length > 3 is called hole of G. An induced cycle of G of
length > 3 is called antihole of G. The first statement of Proposition 1.6 is called
the strong perfect graph theorem.
Proposition 1.6. Let G be a simple graph. Then, G is a perfect graph if and only
if G has no odd holes and no odd antiholes. In particular, G is a perfect graph with
α(G) = 2 if and only if G is bipartite and not empty.
⋆

For a graph G, let G be the nonsimple graph on the vertex set [n + 1] whose edge
(and loop) set is E(G) ∪ {{i, n + 1} : i ∈ [n + 1]}. The following lemma will play
an important role when we study the stable set polytope QG of G.
Lemma 1.7. Let G be a simple graph with α(G) = 2. Then, we have K[QG ] ≃
K[PG⋆ ]. Moreover, if G is bipartite, then there exists a bipartite graph H such that
K[QG ] ≃ K[PH ].
Proof. Let ϕ : K[QG ] → K[x1 , . . . , xn+1 ] be the injective ring homomorphism de2−(a +···+an )
. Then, ϕ(t) = x2n+1 , ϕ(xi t) =
fined by ϕ(xa11 · · · xann t) = xa11 · · · xann xn+1 1
xi xn+1 for i = 1, 2, . . . , n, and ϕ(xk xℓ t) = xk xℓ for each stable set {k, ℓ} of G.
Note that {k, ℓ} is a stable set of G if and only if {k, ℓ} is an edge of G. Hence, the
image of ϕ is K[PG⋆ ].
Suppose that G is bipartite. Then, G has no odd cycles. Hence, any odd cycle
⋆
of G has the vertex n + 1. (Note that {n + 1, n + 1} is an odd cycle of length
4

⋆

1.) Thus, in particular, any two odd cycles of G has a common vertex. By the
argument in [17, Proof of Proposition 5.5], there exists a bipartite graph H such
that K[QG ] ≃ K[PH ].

The first application of Lemma 1.7 is as follows:
Proposition 1.8. Let G be a simple graph. Then, the following conditions are
equivalent:
(i) QG is unimodular;
(ii) G is bipartite.
Moreover, if α(G) = 2, then the conditions
(iii) QG is compressed;
(iv) G is perfect
are also equivalent to conditions (i) and (ii).
Proof. We may assume that G is not complete (i.e., G is not empty and α(G) 6= 1).
Let A be the matrix whose columns are vertices of QG and let




0 e1 · · · en
A
e
.
A=
and B =
1 ··· 1
1 1 ··· 1

e Since | det(B)| = 1, it is known [20, p.70] that QG
Then, B is a submatrix of A.
is unimodular if and only if the absolute value of any nonzero (n + 1)-minor of the
e is 1.
matrix A
Suppose that G is not bipartite. Then, G has an odd cycle C = (i1 , . . . , i2ℓ+1 ).
e that corresponds to
The the absolute value of the (n + 1)-minor of A
{eik + eik+1 : 1 ≤ k ≤ 2ℓ} ∪ {ei1 + ei2ℓ+1 , 0} ∪ {ej : j ∈
/ {i1 , . . . , i2ℓ+1 }}

equals to 2. Hence, QG is not unimodular. Thus, we have (i) ⇒ (ii).
Suppose that G is bipartite. By Lemma 1.7, there exists a bipartite graph H such
that K[QG ] ≃ K[PH ]. It is well-known that the edge polytope of a bipartite graph
is unimodular. Thus, PH is unimodular and hence we have (ii) ⇒ (i).
Suppose that α(G) = 2. By Proposition 1.5, conditions (iii) and (iv) are equivalent. In addition, by Proposition 1.6, conditions (ii) and (iv) are equivalent.

We close this section with the fundamental fact on stable set and edge polytopes.
Proposition 1.9. Let G′ be an induced subgraph of a graph G. Then,
(i) The edge polytope PG′ is a face of PG ;
(ii) If G is a simple graph, then QG′ is a face of QG .
By Proposition 1.9, a lot of the properties of K[QG ] (resp. K[PG ]) are inherited
to K[QG′ ] (resp. K[PG′ ]); for example, the normality of the toric ring, the existence
of a squarefree initial ideal, the existence of a quadratic Gröbner basis, the existence
of the set of quadratic binomial generators of the toric ideal. See [10].
5

2. Normality of stable set polytopes
In this section, we study the normality of stable set polytopes. The normality of
an edge polytope studied in [11, 19] will play an important role. If C1 and C2 are
cycles in a graph G, then an edge {i, j} of G is called a bridge of C1 and C2 if i is a
vertex of C1 \ C2 and if j is a vertex of C2 \ C1 . We say that a graph G satisfies the
odd cycle condition if, for arbitrary two induced odd cycles C1 and C2 in G, either
C1 and C2 have a common vertex or there exists a bridge of C1 and C2 . For the
sake of simpleness, assume that a graph H has at most one loop. Then, it is known
[11, 19] that PH is normal if and only if each connected component of H satisfies the
odd cycle condition. By [11, Corollary 2.3] and Lemma 1.7, we have the following.
(Note that G below is not necessarily connected.)
Theorem 2.1. Let G be a simple graph with α(G) = 2. Then, the following conditions are equivalent.
(i) QG is normal;
(ii) QG has a unimodular covering;
(iii) G satisfies the odd cycle condition, i.e., if two odd holes C1 and C2 in G have
no common vertices, then there exists a bridge of C1 and C2 in G.
In particular, if QG is normal, then PG is normal.
Proof. Let G be a simple graph on the vertex set [n] with α(G) = 2. By Lemma 1.7,
we have K[QG ] ≃ K[PG⋆ ]. Hence, by [11, Corollary 2.3], conditions (i) and (ii) are
⋆
equivalent, and they hold if and only if G satisfies the odd cycle condition. (Note
⋆
⋆
that G is connected.) Since the vertex n + 1 is incident with any vertices of G , it
⋆
is easy to see that G satisfies the odd cycle condition if and only if G satisfies the
odd cycle condition.

It is known [12] that there exists a graph G such that PG is normal and that IPG
has no squarefree initial ideals. In [9], infinite families of such edge polytopes are
given. We can construct the stable set polytopes with the same properties. Let
G1 (p1 , . . . , p5 ) be a graph defined in [9, Theorem 3.10].
Theorem 2.2. Let G be a graph whose complement is G1 (p1 , . . . , p5 ) with pi ≥ 2
for i = 1, . . . , 5. Then, QG is normal and IQG has no squarefree initial ideals.
Proof. Since G has no triangles, we have α(G) = 2. Since G1 (p1 , . . . , p5 ) satisfies
the odd cycle condition, QG is normal by Theorem 2.1. On the other hand, IG
⋆
has no squarefree initial ideals. Since G is an induced subgraph of G , IQG has no
squarefree initial ideals by Lemma 1.7 and Proposition 1.9.

It seems to be a challenging problem to characterize the normal steble set polytopes with large stability number. We give several necessary conditions. The following is a consequence of Proposition 1.9 and Theorem 2.1.
Proposition 2.3. Let G be a simple graph. Suppose that QG is normal. Then, any
two odd holes of G without common vertex have a bridge in G.
6

Proof. Suppose that two odd holes C1 , C2 of G without common vertices have no
bridges in G. Let H be an induced subgraph of G whose vertex set is that of C1 ∪C2 .
Then, α(H) = 2 and hence QH is not normal by Theorem 2.1. Thus, QG is not
normal by Proposition 1.9.

Similar conditions are required for antiholes of G.
Proposition 2.4. Let G be a simple graph. Suppose that QG is normal. Then, G
satisfies all of the following conditions:
(i) Any two odd antiholes of G having no common vertices have a bridge in G.
(ii) Any two odd antiholes of G of length ≥ 7 having exactly one common vertex
have a bridge in G.
(iii) Any odd hole and odd antihole of G having no common vertices have a bridge
in G.
Proof. Let G be a graph on the vertex set [n]. Let A = {(ρ(W ), 1)t : W ∈ S(G)}.
It is known [20, Proposition 13.5] that QG is normal if and only if we have Z≥0 A =
Q≥0 A ∩ Zn+1 .
(i) Let C1 = (i1 , . . . , i2k+1 ) and C2 = (j1 , . . . , j2ℓ+1 ) be odd antiholes in G having
no common vertices and no bridges in G. By Proposition 1.9, we may assume that
G = C1 ∪ C2 . Then,
X

W ∈S(C1 )

and

X

W ∈S(C2 )

2k+1
X

(ρ(W ), 1) = (2k + 1)en+1 + k

p=1

|W |=k

(ρ(W ), 1) = (2ℓ + 1)en+1 + ℓ

and

eip ,

2ℓ+1
X

ejq .

q=1

|W |=ℓ

Since k, ℓ ≥ 2, we have kℓ − k − ℓ ≥ 0. Hence,
5en+1 +

2k+1
X
p=1

1
=
k

eip +

2ℓ+1
X

ejq

q=1

(2k + 1)en+1 + k

2k+1
X
p=1

eip

!

1
+
ℓ

(2ℓ + 1)en+1 + ℓ

2ℓ+1
X
q=1

ejq

!

+

kℓ − k − ℓ
en+1
kℓ

belongs to Q≥0 A ∩ Zn+1 . However, this vector is not in Z≥0 A since max{|W | : W ∈
S(C1 )} = k, max{|W | : W ∈ S(C2 )} = ℓ, and ⌈(2k + 1)/k⌉ + ⌈(2ℓ + 1)/ℓ⌉ = 6 > 5.
(ii) Let C1 = (i1 , . . . , i2k+1 ) and C2 = (j1 , . . . , j2ℓ+1 ) be odd antiholes in G of
length ≥ 7 having exactly one common vertex i1 = j1 and no bridges in G. By
Proposition 1.9, we may assume that G = C1 ∪ C2 . Let
S1 = {W ∈ S(C1 ) : |W | = k and either i1 ∈ W or {i2 , i2k+1 } ⊂ W },
S2 = {W ∈ S(C2 ) : |W | = ℓ and either j1 ∈ W or {j2 , j2ℓ+1 } ⊂ W }.
7

Then,
X

(ρ(W ), 1) = (2k − 1)en+1 + kei1 + (k − 1)

W ∈S1

X

2k+1
X

eip ,

p=2

(ρ(W ), 1) = (2ℓ − 1)en+1 + ℓei1 + (ℓ − 1)

2ℓ+1
X

ejq .

q=2

W ∈S2

Since k, ℓ ≥ 3, we have 0 < 1/(k − 1) + 1/(ℓ − 1) ≤ 1. Hence,

α := 5en+1 + 3ei1 +

2k+1
X

eip +

1
+
ℓ−1

ejq

q=2

p=2

1
=
k−1

2ℓ+1
X

(2k − 1)en+1 + kei1 + (k − 1)

2k+1
X
p=2

(2ℓ − 1)en+1 + ℓei1 + (ℓ − 1)

2ℓ+1
X
q=2

eip

!

ejq

!


+ 1−


1
1
(ei1 + en+1 )
−
k−1 ℓ−1

belongs to Q≥0 A ∩ Zn+1 . Suppose that α = (ρ(W1 ), 1) + · · · + (ρ(W5 ), 1) for Wi ∈
S(G). Then, each Wi belongs to either S(C1 ) or S(C2 ). Since max{|W | : W ∈
S(C1 )} = k, max{|W | : W ∈ S(C2 )} = ℓ, we have
|{W1 , . . . , W5 } ∩ S(C1 )| ≥ 2,
|{W1 , . . . , W5 } ∩ S(C2 )| ≥ 2.
We may assume that W1 , W2 ∈ S(C1 ) and W3 , W4 , W5 ∈ S(C2 ). It then follows that
P2ℓ+1
P
ρ(W1 ) + ρ(W2 ) = 2k+1
q=2 ejq .
p=2 eip , and hence ρ(W3 ) + ρ(W4 ) + ρ(W5 ) = 3ei1 +
Hence i1 ∈ W3 ∩ W4 ∩ W5 . Thus, i2 , i2ℓ+1 ∈
/ W3 , W4 , W5 , a contradiction. Therefore,
we have α ∈
/ Z≥0 A.
(iii) Let C1 = (i1 , . . . , i2k+1 ) be an odd hole and C2 = (j1 , . . . , j2ℓ+1 ) an odd
antihole in G having no common vertices. By Proposition 1.9, we may assume that
G = C1 ∪ C2 . Then,
X

W ∈S(C1 )

and

X

W ∈S(C2 )

and

(ρ(W ), 1) = (2k + 1)en+1 + 2

2k+1
X

eip ,

p=1

|W |=2

(ρ(W ), 1) = (2ℓ + 1)en+1 + ℓ

2ℓ+1
X
q=1

|W |=ℓ

8

ejq .

Hence,
(k + 3)en+1 +

2k+1
X

eip +

q=1

p=1

1
=
2

2ℓ+1
X

(2k + 1)en+1 + 2

2k+1
X

eip

p=1

n+1

ejq
!

1
+
ℓ

(2ℓ + 1)en+1 + ℓ

2ℓ+1
X

ejq

q=1

!

+

ℓ−2
en+1
2ℓ

belongs to Q≥0 A ∩ Z . However, this vector is not in Z≥0 A since max{|W | : W ∈
S(C1 )} = 2, max{|W | : W ∈ S(C2 )} = ℓ, and ⌈(2k + 1)/2⌉ + ⌈(2ℓ + 1)/ℓ⌉ = k + 4 >
k + 3.

Unfortunately, the above conditions are not sufficient to be normal in general.
For example, if the length of the two odd antiholes of G without common vertices
are long, then a lot of bridges in G seem to be needed.
3. Generators and Gröbner bases of IQG
For a toric ideal I, let µ(I) be the maximum degree of binomials in a minimal set
of binomial generators of I. If I = {0}, then we set µ(I) = 0. In this section, we
study µ(IQG ) by using results on the toric ideals of edge polytopes.
Let G be a graph on the vertex set [n] allowing loops and having no multiple
edges. Let E(G) = {e1 , . . . , em } be a set of all edges and loops of G. The toric ideal
IPG is the kernel of a homomorphism π : K[y1 , . . . , ym] → K[x1 , . . . , xn ] defined by
π(yi ) = xk xℓ where ei = {k, ℓ}. A walk of length q of G connecting v1 ∈ [n] and
vq+1 ∈ [n] is a finite sequence of the form
(1)

Γ = ({v1 , v2 }, {v2 , v3 }, . . . , {vq , vq+1 })

with each {vk , vk+1 } ∈ E(G). An even (resp. odd) walk is a walk of even (resp. odd)
length. A walk Γ of the form (1) is called closed if vq+1 = v1 . Given an even closed
walk Γ = (ei1 , ei2 , . . . , ei2q ) of G, we write fΓ for the binomial
fΓ =

q
Y

yi2k−1 −

q
Y

yi2k ∈ IPG .

k=1

k=1

We regard a loop as an odd cycle of length 1. It is known ([13, 20, 24]) that
Proposition 3.1. Let G be a graph having at most one loop. Then, IPG is generated
by all the binomials fΓ , where Γ is an even closed walk of G. In particular, IPG = (0)
if and only if each connected component of G has at most one cycle and the cycle is
odd.
The following theorem implies that the set of binomial generators of IQG is also
characterized by the graph theoretical terminology if α(G) = 2.
Theorem 3.2. Let G be a simple graph with α(G) = 2. Then, IQG = IPG + J where
J is an ideal generated by quadratic binomials fΓ where Γ is an even closed walk of
⋆
G that satisfies one of the following:
(i) Γ = ({i, j}, {j, k}, {k, n+1}, {n+1, i}) is a cycle where {i, j}, {j, k} ∈ E(G);
9

(ii) Γ = ({i, j}, {j, n + 1}, {n + 1, n + 1}, {n + 1, i}) where {i, j} ∈ E(G).
In particular, µ(IQG ) = max{µ(IPG ), 2}.
⋆

Proof. Let Γ be an even closed walk of G . It is enough to show that fΓ ∈ IPG⋆
belongs to IPG + J. Suppose that fΓ does not belong to IPG + J. Then, the vertex
n + 1 belongs to Γ. We may assume that the degree of fΓ is minimum among such
binomials. Then, fΓ is irreducible. Let
Γ = ({n + 1, p}, {p, q}, {q, r}, Γ′).
Since fΓ is irreducible, it follows that p, q, r are distinct each other and that q 6= n+1.
Then, fΓ is generated by fΓ1 and fΓ2 where Γ1 = ({n + 1, p}, {p, q}, {q, r}, {r, n + 1})
and Γ2 = ({n+1, r}, Γ′). Since deg fΓ2 < deg fΓ , the binomial fΓ2 belongs to IPG +J
by the assumption on deg fΓ . Moreover, Γ1 satisfies one of the conditions (i) or (ii)
and hence fΓ1 ∈ J. Thus, we have fΓ ∈ hfΓ1 , fΓ2 i ⊂ IPG + J, a contradiction.

Remark 3.3. A graph theoretical characterization of a simple graph G such that
µ(IPG ) ≤ 2 is given in [13]. By Theorem 3.2, the characterization [13, Theorem 1.2]
gives a graph theoretical characterization of a simple graph G such that α(G) = 2
and µ(IQG ) ≤ 2.
It is known [2, Theorem 7.4] that, if the complement of a graph G is an even cycle
of length 2k, then we have µ(IQG ) = k. By Theorem 3.2, we can generalize this
result for a graph whose complement is an arbitrary bipartite graph.
Corollary 3.4. Let G be a simple graph such that G is bipartite. Then, we have

 0 if G is empty (i.e., G is complete),
µ(IQG ) =
k if G has a cycle,

2 otherwise,

where 2k is the maximum length of induced cycles of G. Moreover, the following
conditions are equivalent:
(i) µ(IQG ) ≤ 2, i.e., IQG is generated by quadratic binomials;
(ii) K[QG ] is Koszul;
(iii) IQG has a quadratic Gröbner basis;
(iv) The length of any induced cycle of G is 4.
Proof. Let G be a simple graph such that G is bipartite. Then, α(G) = 2. Since G
is bipartite, it is known (see, e.g., [18]) that, IPG is generated by fΓ where Γ is an
induced even cycle of G. Note that deg fΓ = k if the length of Γ is 2k. Hence, by
Theorem 3.2, we have a formula for µ(IQG ).
By this formula, it follows that (i) and (iv) are equivalent. Moreover, (iii) ⇒ (ii)
⇒ (i) holds in general. By Lemma 1.7, there exists a bipartite graph H such that
K[QG ] ≃ K[PH ]. By the theorem in [14], IPH has a quadratic Gröbner basis if and
only if µ(IPH ) ≤ 2. Thus, we have (i) ⇒ (iii).

If G is not bipartite, then condition (i) and (iii) in Corollary 3.4 are not equivalent.
In order to construct an infinite family of counterexamples, the following proposition
is important. (Proof is essentially given in [13, Proof of Proposition 1.6].)
10

Proposition 3.5. Let P be a (0, 1)-polytope. If IP has a quadratic Gröbner basis,
then the initial ideal is generated by squarefree monomials and hence P is normal.
Theorem 3.6. Let G be a simple graph such that G consists of two odd holes without
common vertices. Then, α(G) = 2 and
(a) IQG is generated by quadratic binomials;
(b) IQG has no quadratic Gröbner bases;
(c) QG is not normal.
Proof. Since G has no triangles, we have α(G) = 2. By Proposition 3.1 and Theorem
3.2, it follows that IG = {0} and IQG is generated by quadratic binomials. On the
other hand, by Theorem 2.1, QG is not normal. Thus, by Proposition 3.5, IQG has
no quadratic Gröbner bases.

The graphs in Theorem 3.6 are not strongly Koszul by the result in [7]. However,
we do not know whether they are Koszul or not in general.
Remark 3.7. It is known [13, Theorem 1.2] that, if G is a simple connected graph
and IPG is generated by quadratic binomials, then G satisfies the odd cycle condition
and hence PG is normal.
It seems to be a challenging problem to characterize the graphs G such that
α(G) > 2 and µ(IQG ) ≤ 2. The following is a consequence of Proposition 1.9,
Theorem 3.2 and [13, Theorem 1.2].
Proposition 3.8. Let G be a simple graph. If IQG is generated by quadratic binomials, then G satisfies the following conditions:
(i) Any even cycle of G of length ≥ 6 has a chord;
(ii) Any two odd holes of G having exactly one common vertex have a bridge;
(iii) Any two odd holes of G having no common vertex have at least two bridges.
Proof. Suppose that G does not satisfy one of the conditions above. If G does not
satisfy condition (i), then let H be an induced subgraph of G whose vertex set is that
of the even cycle. If G does not satisfy condition either (ii) or (iii), then let H be an
induced subgraph of G whose vertex set is that of two odd holes. Then, α(H) = 2
and hence IQH is not generated by quadratic binomials by Theorem 3.2 and [13,
Theorem 1.2]. Thus, it follows from Proposition 1.9 that IQG is not generated by
quadratic binomials.

References
[1] R. Diestel, “Graph Theory,” Fourth Edition, Graduate Texts in Mathematics 173, Springer,
2010.
[2] A. Engström and P. Norén, Ideals of graph homomorphisms, Ann. Comb. 17 (2013), 71–103.
[3] I. Gitler, E. Reyes and R. H. Villarreal, Ring graphs and toric ideals, Electron. Notes Discrete
Math., 28 (2007), 393–400.
[4] I. Gitler, E. Reyes and R. H. Villarreal, Ring graphs and complete intersection toric ideals,
Discrete Math. 310 (2010), 430–441.
[5] J. Gouveia, P. A. Parrilo and R. R. Thomas, Theta bodies for polynomial ideals, SIAM J.
Optim. 20 (2010), 2097–2118.
11

[6] T. Hibi and N. Li, Chain polytopes and algebras with straightening laws, Acta Math. Vietnam.
40 (2015) 447–452.
[7] K. Matsuda, Strong Koszulness of toric rings associated with stable set polytopes of trivially
perfect graphs, J. Algebra Appl. 13 (2014), 1350138 [11 pages].
[8] U. Nagel and S. Petrović, Properties of cut ideals associated to ring graphs, J. Commut.
Algebra 1 (2009) 547–565.
[9] H. Ohsugi, Toric ideals and an infinite family of normal (0, 1)-polytopes without unimodular
regular triangulations, Discrete Comput. Geom. 27 (2002), 551–565.
[10] H. Ohsugi, J. Herzog and T. Hibi, Combinatorial pure subrings, Osaka J. Math. 37 (2000),
745–757.
[11] H. Ohsugi and T. Hibi, Normal polytopes arising from finite graphs, J. Algebra 207 (1998),
409–426.
[12] H. Ohsugi and T. Hibi, A normal (0, 1)-polytope none of whose regular triangulations is
unimodular, Discrete Comput. Geom. 21 (1999), 201–204.
[13] H. Ohsugi and T. Hibi, Toric ideals generated by quadratic binomials, J. Algebra 218 (1999),
509–527.
[14] H. Ohsugi and T. Hibi, Koszul bipartite graphs, Adv. Appl. Math. 22 (1999), 25–28.
[15] H. Ohsugi and T. Hibi, Convex polytopes all of whose reverse lexicographic initial ideals are
squarefree, Proc. Amer. Math. Soc., 129 (2001), No.9, 2541–2546.
[16] H. Ohsugi and T. Hibi, Special simplices and Gorenstein toric rings, J. Combin. Theory Ser.
A 113 (2006), Issue 4, 718–725.
[17] H. Ohsugi and T. Hibi, Centrally symmetric configurations of integer matrices, Nagoya Math.
J. 216 (2014), 153–170.
[18] A. Simis, On the Jacobian module associated to a graph, Proc. Amer. Math. Soc., 126 No. 4
(1998), 989–997.
[19] A. Simis, W. V. Vasconcelos and R. H. Villarreal, The integral closure of subrings associated
to graphs, J. Algebra 199 (1998), 281–289.
[20] B. Sturmfels, “Gröbner bases and convex polytopes,” Amer. Math. Soc., Providence, RI, 1996.
[21] B. Sturmfels, Four counterexamples in combinatorial algebraic geometry, J. Algebra 230
(2000) 282–294.
[22] S. Sullivant, Compressed polytopes and statistical disclosure limitation, Tohoku Math. J. 58
(2006), 433–445.
[23] S. Sullivant, Toric fiber products, J. Algebra 316 (2007), 560–577.
[24] R. Villarreal, Rees algebras of edge ideals, Comm. Algebra, 23 (1995), 3513–3524.
Kazunori Matsuda, Department of Pure and Applied Mathematics, Graduate
School of Information Science and Technology, Osaka University, Suita, Osaka
565-0871, Japan
E-mail address: kaz-matsuda@ist.osaka-u.ac.jp
Hidefumi Ohsugi, Department of Mathematical Sciences, School of Science and
Technology, Kwansei Gakuin University, Sanda, Hyogo, 669-1337, Japan
E-mail address: ohsugi@kwansei.ac.jp
Kazuki Shibata, Department of Mathematics, College of Science, Rikkyo University, Toshima-ku, Tokyo 171-8501, Japan
E-mail address: k-shibata@rikkyo.ac.jp

12

