arXiv:1410.4786v2 [] 30 Dec 2015

REVERSE LEXICOGRAPHIC SQUAREFREE INITIAL IDEALS
AND GORENSTEIN FANO POLYTOPES
HIDEFUMI OHSUGI AND TAKAYUKI HIBI

Abstract. Via the theory of reverse lexicographic squarefree initial ideals of
toric ideals, we give a new class of Gorenstein Fano polytopes (reflexive polytopes)
arising from a pair of stable set polytopes of perfect graphs.

Introduction
Recall that an integral convex polytope is a convex polytope all of whose vertices
have integer coordinates. An integral convex polytope P ⊂ Rd of dimension d is
called a Fano polytope if the origin of Rd is a unique integer point belonging to
the interior of P. We say that a Fano polytope P ⊂ Rd is Gorenstein if the dual
polytope P ∨ of P is again integral. (A Gorenstein Fano polytope is often called
a reflexive polytope in the literature.) Gorenstein Fano polytopes are related with
mirror symmetry and studied in a lot of areas of mathematics. See, e.g., [5, §8.3]
and [15]. It is known that there are only finitely many Gorenstein Fano polytopes
up to unimodular equivalence if the dimension is fixed. Classification results are
known for low dimensional cases [16, 17]. On the other hand, one of the most
important problem is to construct new classes of Gorenstein Fano polytopes. In
the case of Gorenstein Fano simplices, there are nice results on classifications and
constructions. See, e.g., [4, 14, 18] and their references. In order to find classes of
Gorenstein Fano polytopes of high dimension which are not necessarily simplices,
integral convex polytopes arising from some combinatorial objects are studied in
several papers. For example, the following classes are known:
• Gorenstein Fano polytopes arising from the order polytopes of graded posets
(Hibi [10], revisited by Hegedüs–Kasprzyk [7, Lemma 5.10]);
• Gorenstein Fano polytopes arising from the Birkhoff polytopes (appearing
in many papers. See, e.g., Stanley’s book [24, I.13] and Athanasiadis [1]);
• Gorenstein Fano polytopes arising from directed graphs satisfying some conditions (Higashitani [13]);
• Centrally symmetric configurations (Ohsugi–Hibi [23]);
• The centrally symmetric polytope O(P )± of the order polytope O(P ) of a
finite poset P (Hibi–Matsuda–Ohsugi–Shibata [12]).
2010 Mathematics Subject Classification. Primary 13P10; Secondary 52B20.
Key words and phrases. Gröbner basis, Gorenstein Fano polytope, unimodular triangulation.
1

In the present paper, via the theory of Gröbner bases, we give a new class of Gorenstein Fano polytopes which is not necessarily a simplex. For any pair of perfect
graphs G1 and G2 (here, G1 = G2 is possible) on d vertices, we show that the convex hull of QG1 ∪ −QG2 , where QGi is the stable set polytope of Gi , is a Gorenstein
Fano polytope of dimension d. Note that there are a lot of pairs of perfect simple
graphs on d vertices1 (Figure 1). Any Gorenstein Fano polytope P in our class is
number of vertices
2 3 4
5
6
7
8
perfect graphs
2 4 11 33
148
906
8887
pairs of perfect graphs 3 10 66 561 11,026 410,871 39,493,828
Figure 1. Number of perfect graphs / pairs of perfect graphs
terminal, i.e., each integer point belonging to the boundary of P is a vertex of P. In
particular, if both of two graphs are the complete (resp. empty) graphs on d vertices,
then the Gorenstein Fano polytope has 2d (resp. 2d+1 − 2) vertices. Thus, our class
has enough size and variety comparing with the existing classes above.
Let Z≥0 denote the set of nonnegative integers. Let A = [a1 , . . . , an ] ∈ Zd×n
≥0
and B = [b1 , . . . , bm ] ∈ Zd×m
,
where
each
a
and
each
b
is
a
nonzero
column
i
j
≥0
vector belonging to Zd≥0 . In Section 1, after reviewing basic materials and notation
on toric ideals, we introduce the concept that A and B are of harmony. Roughly
speaking, Theorem 1.1 says that if A and B are of harmony and if the toric ideal
of each of A and B possesses a reverse lexicographic squarefree initial ideal which
enjoys certain properties, then the toric ideal of [0, −B, A] ∈ Zd×(n+m+1) possesses a
squarefree initial ideal with respect to a reverse lexicographic order whose smallest
variable corresponds to the column 0 ∈ Zd . Working with the same situation as in
Theorem 1.1, Corollary 1.3 guarantees that if the integral convex polytope P ⊂ Rd
which is the convex hull of {−b1 , . . . , −bm , a1 , . . . , an } is a Fano polytope with
P ∩ Zd = {0, −b1 , . . . , −bm , a1 , . . . , an } and if there is a d × d minor A′ of [−B, A]
with det(A′ ) = ±1, then P is Gorenstein.
The topic of Section 2 is the incidence matrix A∆ of a simplicial complex ∆ on
[d] = {1, . . . , d}. It follows that if ∆ and ∆′ are simplicial complexes on [d], then
A∆ and A∆′ are of harmony. Following Theorem 1.1 it is reasonable to study the
problem when the toric ideal of A∆ satisfies the required condition on initial ideals
of Theorem 1.1. Somewhat surprisingly, Theorem 2.6 says that A∆ satisfies the
required condition on initial ideals of Theorem 1.1 if and only if ∆ coincides with
the set S(G) of stable sets of a perfect graph G on [d]. A related topic on Gorenstein
Fano polytopes arising from simplicial complexes will be studied (Theorem 2.8).
1

See A052431 in “The On-Line Encyclopedia of Integer Sequences,” at http://oeis.org
2

1. Reverse lexicographic squarefree initial ideals
−1
Let K be a field and K[t, t−1 , s] = K[t1 , t−1
1 , . . . , td , td , s] the Laurent polynomial
ring in d + 1 variables over K. Given an integer d × n matrix A = [a1 , . . . , an ], where
aj = [a1j , . . . , adj ]⊤ , the transpose of [a1j , . . . , adj ], is the jth column of A, the toric
ring of A is the subalgebra K[A] of K[t, t−1, s] which is generated by the Laurent
polynomials ta1 s = ta111 · · · tdad1 s, . . . , tan s = ta11n · · · taddn s. Let K[x] = K[x1 , . . . , xn ]
denote the polynomial ring in n variables over K and define the surjective ring
homomorphism π : K[x] → K[A] by setting π(xj ) = taj s for j = 1, . . . , n. The toric
ideal of A is the kernel IA of π. Every toric ideal is generated by binomials. (Recall
Q
that a polynomial f ∈ K[x] is a binomial if f = u − v, where u = ni=1 xai i and
P
P
Q
v = ni=1 xbi i are monomials with ni=1 ai = ni=1 bi .) Let < be a monomial order
on K[x] and in< (IA ) the initial ideal of IA with respect to <. We say that in< (IA )
is squarefree if in< (IA ) is generated by squarefree monomials. We refer the reader
to [11, Chapters 1 and 5] for the information about Gröbner bases and toric ideals.
Let Zd≥0 denote the set of integer column vectors [a1 , . . . , ad ]⊤ with each ai ≥ 0.
(+)
(+)
Given an integer vector a = [a1 , . . . , ad ]⊤ ∈ Zd , let a(+) = [a1 , . . . , ad ]⊤ , a(−) =
(−)
(−)
(+)
(−)
[a1 , . . . , ad ]⊤ ∈ Zd≥0 where ai = max{0, ai } and ai = max{0, −ai }. Note that
a = a(+) − a(−) holds in general. Let Zd×n
≥0 denote the set of d × n integer matrices
(aij ) 1≤i≤d with each aij ≥ 0. Furthermore if no columns of A ∈ Zd×n
≥0 is the zero
1≤j≤n

vector 0 = [0, . . . , 0]⊤ ∈ Zd , then we introduce the d × (n + 1) integer matrix A♯
which is obtained by adding the column 0 ∈ Zd to A.
d×m
Now, given A ∈ Zd×n
≥0 and B ∈ Z≥0 , we say that A and B are of harmony if
the following condition is satisfied: Let a be a column of A♯ and b that of B ♯ . Let
c = a − b ∈ Zd . If c = c(+) − c(−) , then c(+) is a column vector of A♯ and c(−) is a
column vector of B ♯ .
d×m
Theorem 1.1. Let A = [a1 , . . . , an ] ∈ Zd×n
≥0 and B = [b1 , . . . , bm ] ∈ Z≥0 , where
none of ai ’s and bj ’s is 0 ∈ Zd , be of harmony. Let K[z, x] = K[z, x1 , . . . , xn ]
and K[z, y] = K[z, y1 , . . . , ym ] be the polynomial rings over a field K. Suppose that
in<A (IA♯ ) ⊂ K[z, x] and in<B (IB♯ ) ⊂ K[z, y] are squarefree with respect to reverse
lexicographic orders <A on K[z, x] and <B on K[z, y] respectively satisfying the
conditions that

• xi <A xj if π(xi ) divides π(xj );
• z <A xk for 1 ≤ k ≤ n, where z corresponds to the column 0 ∈ Zd of A♯ ;
• z <B yk for 1 ≤ k ≤ m, where z corresponds to the column 0 ∈ Zd of B ♯ .
Let [−B, A] denote the d × (n + m) integer matrix
[−b1 , . . . , −bm , a1 , . . . , an ].
3

Then the toric ideal I[−B,A]♯ of [−B, A]♯ possesses a squarefree initial ideal with
respect to a reverse lexicographic order whose smallest variable corresponds to the
column 0 ∈ Zd of [−B, A]♯ .
−1
Proof. Let K[[−B, A]♯ ] ⊂ K[t, t−1 , s] = K[t1 , t−1
1 , . . . , td , td , s] be the toric ring of
[−B, A]♯ and I[−B,A]♯ ⊂ K[x, y, z] = K[x1 , . . . , xn , y1 , . . . , ym, z] the toric ideal of
[−B, A]♯ . Recall that I[−B,A]♯ is the kernel of π : K[x, y, z] → K[[−B, A]♯ ] with
π(z) = s, π(xi ) = tai s for i = 1, . . . , n and π(yj ) = t−bj s for j = 1, . . . , m.
Suppose that the reverse lexicographic orders <A and <B are induced by the
orderings z <A xn <A · · · <A x1 and z <B ym <B · · · <B y1 . Let <rev be the reverse
lexicographic order on K[x, y, z] induced by the ordering

z < xn < · · · < x1 < ym < · · · < y1 .
In general, if a = [a1 , . . . , ad ]⊤ ∈ Zd≥0 , then supp(a) is the set of those 1 ≤ i ≤ d
with ai 6= 0. Now, we introduce the following
E = { (i, j) : 1 ≤ i ≤ n, 1 ≤ j ≤ m, supp(ai ) ∩ supp(bj ) 6= ∅ }.
Let c = ai − bj with (i, j) ∈ E. Then c(+) 6= ai and c(−) 6= bj . The hypothesis that
A and B are of harmony guarantees that c(+) is a column of A♯ and c(−) is a column
of B ♯ . It follows that f = xi yj − u (6= 0) belongs to I[−B,A]♯ , where

xk yℓ if c(+) = ak and c(−) = bℓ ,



zyℓ if c(+) = 0 and c(−) = bℓ ,
u=

x z if c(+) = ak and c(−) = 0,

 k2
z
if c(+) = c(−) = 0.
If z divides u, then in<rev (f ) = xi yj , where in<rev (f ) is the initial monomial of
f ∈ K[x, y, z]. If z cannot divide u, then, since π(xk ) divides π(xi ), one has xk <A xi
and in<rev (f ) = xi yj . Hence
{ xi yj : (i, j) ∈ E } ⊂ in<rev (I[−B,A]♯ ).
Now, let MA (resp. MB ) be the minimal set of squarefree monomial generators
of in<A (IA♯ ) (resp. in<B (IB♯ )). Suppose that in<rev (I[−B,A]♯ ) cannot be generated by
the set of squarefree monomials
M = { xi yj : (i, j) ∈ E } ∪ MA ∪ MB ( ⊂ in<rev (I[−B,A]♯ ) ).
The following fact ([22, (0.1), p. 1914]) on Gröbner bases is known:
A finite set G of IA is a Gröbner basis with respect to < if and only if π(u) 6= π(v)
for any monomials u ∈
/ (in< (g) : g ∈ G) and v ∈
/ (in< (g) : g ∈ G) with u 6= v.
Since G with M = {in< (f ) : f ∈ G} is not a Gröbner basis, it follows that there
exists a nonzero irreducible binomial g = u − v belonging to I[−B,A]♯ such that each
4

of u and v can be divided by none of the monomials belonging to M. Write
!
!
!
!
Y
Y
Y
Y
u=
xipp
yqjq , v = z α
xkr r
ysℓs ,
p∈P

q∈Q

r∈R

s∈S

where P and R are subsets of {1, . . . , n}, where Q and S are subsets of {1, . . . , m},
where α is a nonnegative integer, and where each of ip , jq , kr , ℓs is a positive integer.
Since g = u − v is irreducible, one has P ∩ R = Q ∩ S = ∅. Furthermore, the fact
that each of xi yj with (i, j) ∈ E can divide neither u nor v guarantees that
!
!
!
!
[
[
[
[
supp(ap ) ∩
supp(bq ) =
supp(ar ) ∩
supp(bs ) = ∅.
p∈P

q∈Q

r∈R

Since π(u) = π(v), it follows that
X
X
ip ap =
kr ar ,
p∈P

Let γP =

P

p∈P ip ,

γQ =

r∈R

P

q∈Q jq ,

γR =

X

s∈S

jq bq =

q∈Q

P

r∈R

X

ℓs bs .

s∈S

kr , and γS =

γP + γQ = α + γR + γS .

P

s∈S ℓs .

Then

Since α ≥ 0, it follows that either γP ≥ γR or γQ ≥ γS . Let, say, γP > γR , then
!
Y
Y
h=
xipp − z γP −γR
xkr r 6= 0
p∈P

belongs to I[−B,A]♯ and in<rev (h) =
γR . Then the binomial
h0 =

r∈R

ip
p∈P xp

Q

Y

xipp −

p∈P

divides u, a contradiction. Hence γP =
Y

xkr r

r∈R

Q
Q
i
belongs to I[−B,A]♯ . If h0 6= 0, then either p∈P xpp or r∈R xkr r must belong to
in<rev (I[−B,A]♯ ). This contradicts the fact that each of u and v can be divided by
none of the monomials belonging to M. Hence h0 = 0 and P = R = ∅. Similarly,
Q = S = ∅. Hence α = 0 and g = 0. This contradiction guarantees that M is the

minimal set of squarefree monomial generators of in<rev (I[−B,A]♯ ), as desired.
Given an integral convex polytope P ⊂ Rd , we write AP for the integer matrices
whose column vectors are those a ∈ Zd belonging to P. The toric ring K[AP ] is
often called the toric ring of P. A triangulation ∆ of P with using the vertices
belonging to P ∩ Zd is unimodular if the normalized volume ([11, p. 253]) of each
facet of ∆ is equal to 1 and is flag if every minimal nonface of ∆ is an edge. It follows
from [26, Chapter 8] that if the toric ideal IAP of AP possesses a squarefree initial
ideal, then P possesses a unimodular triangulation. Furthermore if IAP possesses
an initial ideal generated by quadratic squarefree monomials, then P possesses a
unimodular triangulation which is flag.
5

An integral convex polytope P ⊂ Rd of dimension d is called Fano if the origin
of Rd is a unique integer point belonging to the interior of P. We say that a Fano
polytope P is Gorenstein if the dual polytope P ∨ of P is again integral ([2], [9]). A
smooth Fano polytope is a simplicial Fano polytope P ⊂ Rd for which the d vertices
of each facet of P is a Z-basis of Zd .
Lemma 1.2. Let P ⊂ Rd be an integral convex polytope of dimension d for which
0 ∈ Zd belongs to P. Suppose that there is a d×d minor A′ of AP with det(A′ ) = ±1
and that IAP possesses a squarefree initial ideal with respect to a reverse lexicographic
order whose smallest variable corresponds to the column 0 ∈ Zd of AP . Then, for
each facet F of P with 0 6∈ F , one has ZF = Zd , where
X
ZF =
Za,
a ∈ F ∩ Zd

and the equation of the supporting hyperplane H ⊂ Rd with F ⊂ H is of the form
a1 z1 + · · · + ad zd = 1

with each aj ∈ Z.
In particular if P is a Fano polytope, then P is Gorenstein. Furthermore if P is
a simplicial Fano polytope, then P is a smooth Fano polytope.
Proof. Let ∆ be the pulling triangulation ([11, p. 268]) coming from a squarefree
initial ideal with respect to a reverse lexicographic order whose smallest variable
corresponds to the column 0 ∈ Zd of AP . A crucial fact is that the origin of Rd
belongs to each facet of ∆. Let F be a facet of ∆ with the vertices 0, b1 , . . . , bd for
which {b1 , . . . , bd } ⊂ F . The existence of a d × d minor A′ of AP with det(A′ ) = ±1
guarantees that the normalized volume of F coincides with | det(B)|, where B =
[b1 , . . . , bd ]. Since ∆ is unimodular, one has det(B) = ±1. Hence {b1 , . . . , bd } is
a Z-basis of Zd and ZF = Zd follows. Moreover the hyperplane H ⊂ Rd with each
bj ∈ H is of the form a1 z1 + · · · + ad zd = 1 with each aj ∈ Z, as desired.

Corollary 1.3. Work with the same situation as in Theorem 1.1. Let P ⊂ Rd be
the integral convex polytope which is the convex hull of {−b1 , . . . , −bm , a1 , . . . , an }.
Suppose that 0 ∈ Zd belongs to the interior of P and that there is a d × d minor A′
of AP with det(A′ ) = ±1. Then P is a Gorenstein Fano polytope. Furthermore if
P is a simplicial polytope, then P is a smooth Fano polytope.
Example 1.4. Let A1 and A2 be the following matrices:




1 0
1 0 1
A1 =
, A2 =
.
0 1
0 1 1

Then, Ai and Aj are of harmony and satisfy the condition in Theorem 1.1 for any
1 ≤ i ≤ j ≤ 2. By Corollary 1.3, we have three Gorenstein Fano polygons. It is
known that there are exactly 16 Gorenstein Fano polygons ([5, p.382]).
6

2. Convex polytopes arising from simplicial complexes
Let [d] = {1, . . . , d} and e1 , . . . , ed the standard coordinate unit vectors of Rd .
P
d
Given a subset W ⊂ [d], one has ρ(W ) =
j∈W ej ∈ R . In particular ρ(∅) is
the origin of Rd . Let ∆ be a simplicial complex on the vertex set [d]. Thus ∆ is
a collection of subsets of [d] with {i} ∈ ∆ for each i ∈ [d] such that if F ∈ ∆
and F ′ ⊂ F , then F ′ ∈ ∆. In particular ∅ ∈ ∆. The incidence matrix A∆ of ∆
is the matrix whose columns are those ρ(F ) with F ∈ ∆. We write P∆ ⊂ Rd for
the (0, 1)-polytope which is the convex hull of { ρ(F ) : F ∈ ∆ } in Rd . One has
dim P∆ = d. It follows from the definition of simplicial complexes that
Lemma 2.1. Let ∆ and ∆′ be simplicial complexes on [d]. Then A∆ and A∆′ are
of harmony.
Following Lemma 2.1 together with Theorem 1.1, it is reasonable to study the
problem when the toric ideal IA∆ of a simplicial complex ∆ possesses a squarefree
initial ideal with respect to a reverse lexicographic order whose smallest variable
corresponds to the column 0 ∈ Zd of A∆ .
Let ∆ be a simplicial complex on [d]. Since {i} ∈ ∆ for each i ∈ [d], the d × d
identity matrix is a d × d minor of A∆ . It then follows from Lemma 1.2 that
Corollary 2.2. Let ∆ be a simplicial complex on [d]. Suppose that IA∆ possesses
a squarefree initial ideal with respect to a reverse lexicographic order whose smallest
variable corresponds to the column 0 ∈ Zd of A∆ . Then, for each facet F of P∆ with
0 6∈ F , one has ZF = Zd and the equation of the supporting hyperplane H ⊂ Rd
with F ⊂ H is of the form a1 z1 + · · · + ad zd = 1 with each aj ∈ Z.
Let G be a finite simple graph on [d] and E(G) the set of edges of G. (Recall
that a finite graph is simple if G possesses no loop and no multiple edge.) A subset
W ⊂ [d] is called stable if, for all i and j belonging to W with i 6= j, one has
{i, j} 6∈ E(G). Let S(G) denote the set of stable sets of G. One has ∅ ∈ S(G)
and {i} ∈ S(G) for each i ∈ [d]. Clearly S(G) is a simplicial complex on [d]. The
stable set polytope QG ⊂ Rd of G is the (0, 1)-polytope PS(G) ⊂ Rd arising from the
simplicial complex S(G). A finite simple graph is said to be perfect ([3]) if, for any
induced subgraph H of G including G itself, the chromatic number of H is equal to
the maximal cardinality of cliques of H. (A chromatic number of G is the smallest
integer t for which there exist stable set W1 , . . . , Wt of G with [d] = W1 ∪ · · · ∪ Wt
and a clique of G is a subset W ⊂ [d] which is a stable set of the complementary
graph G of G.) A complementary graph of a perfect graph is perfect ([3]).
Recall that an integer matrix A is compressed ([21], [27]) if the initial ideal of the
toric ideal IA is squarefree with respect to any reverse lexicographic order.
Example 2.3. Let G be a perfect graph on [d]. Then A∆ , where ∆ = S(G), is
compressed ([21, Example 1.3 (c)]). Let G and G′ be perfect graphs on [d] and
7

Q ⊂ Rd be the Fano polytope which is the convex hull of QG ∪ (−QG′ ). It then
follows from Corollary 1.3 together with Lemma 2.1 that Q is Gorenstein.
Lemma 2.4. Let ∆ be one of the following simplicial complexes:
(i) the simplicial complex on [e] with the facets [e] \ {i}, 1 ≤ i ≤ e, where e ≥ 3;
(ii) S(G), where G is an odd hole of length 2ℓ + 1, where ℓ ≥ 2;
(iii) S(G), where G is an odd antihole of length 2ℓ + 1, where ℓ ≥ 2;
Let < be any reverse lexicographic order whose smallest variable corresponds to the
column 0 of A∆ . Then the initial ideal in< (IA∆ ) cannot be squarefree. (Recall
that an odd hole is an induced odd cycle of length ≥ 5 and an odd antihole is the
complementary graph of an odd hole.)
Proof. By virtue of Corollary 2.2, we find a supporting hyperplane H of P∆ with
0 6∈ H for which H ∩ P∆ is a facet of P∆ such that the equation of H cannot be of
the form a1 z1 + · · · + ad zd = 1 with each aj ∈ Z. In each of (i), (ii) and (iii), the
equation of a desired hyperplane H is as follows:
P
(i) ei=1 zi = e − 1;
P
(ii) 2ℓ+1
zi = ℓ;
Pi=1
2ℓ+1
(iii) i=1 zi = 2.
In (i), it is easy to see that H ∩ P∆ is a facet of P∆ . In each of (ii) and (iii), it is
known ([25], [28]) that H ∩ P∆ is a facet of P∆ .


Let B = [b1 , . . . , bm ] ∈ Zd×m be a submatrix of A = [a1 , . . . , an ] ∈ Zd×n . Then,
K[B] is called a combinatorial pure subring of K[A] if the convex hull of {b1 , . . . , bm }
is a face of the convex hull of {a1 , . . . , an }. For any combinatorial pure subring
K[B] of K[A], it is known that, if the initial ideal of IA is squarefree, then so is the
corresponding initial ideal of IB . See [20, 19] for details.
Lemma 2.5. Let ∆ be a simplicial complex on [d] and ∆′ an induced subcomplex of
∆ which is one of (i), (ii) and (iii) of Lemma 2.4. Let < be any reverse lexicographic
order whose smallest variable corresponds to the column 0 ∈ Zd of A∆ . Then the
initial ideal in< (IA∆ ) cannot be squarefree.
Proof. Let ∆′ be the induced subcomplex of ∆ on V , where V ⊂ [d], and <′ the
reverse lexicographic order induced by <. Lemma 2.4 says that in<′ (IA∆′ ) cannot
be squarefree. Since ∆′ is an induced subcomplex of ∆, it follows that P∆′ is a face
of P∆ . Thus K[A∆′ ] is a combinatorial pure subring of K[A∆ ] and hence in< (IA∆ )
cannot be squarefree, as required.

We are now in the position to state a combinatorial characterization of simplicial
complexes ∆ on [d] for which the toric ideal IA∆ possesses a squarefree initial ideal
with respect to a reverse lexicographic order whose smallest variable corresponds to
the column 0 ∈ Zd of A∆ .
8

Theorem 2.6. Let ∆ be a simplicial complex on [d]. Then the following conditions
are equivalent:
(i) There exists a perfect graph G on [d] with ∆ = S(G);
(ii) A∆ is compressed;
(iii) IA∆ possesses a squarefree initial ideal with respect to a reverse lexicographic
order whose smallest variable corresponds to the column 0 ∈ Zd of A∆ .
Proof. In [21, Example 1.3 (c)], (i) ⇒ (ii) is proved. (See also [6, §4].) Moreover,
(ii) ⇒ (iii) is trivial. Now, in order to show (iii) ⇒ (i), we fix a reverse lexicographic
order < whose smallest variable corresponds 0 ∈ Zd of A∆ .
(First Step) Suppose that there is no finite simple graph G on [d] with ∆ = S(G).
Given a simplicial complex ∆ on [d], there is a finite simple graph G on [d] with
∆ = S(G) if and only if ∆ is flag, i.e, every minimal nonface of ∆ is an edge of ∆.
(See, e.g., [8, Lemma 9.1.3]. Note that S(G) is the clique complex of the complement
graph of G.) Let ∆ be a simplicial complex which is not flag and V ⊂ [d], where
|V | ≥ 3, a minimal nonface of ∆. One has V \ {i} ∈ ∆ for all i ∈ V . Thus
the induced subcomplex ∆′ of ∆ on V coincides with the simplicial complex (i) of
Lemma 2.4.
(Second Step) Let G be a nonperfect graph on [d] with A∆ = S(G). The strong
perfect graph theorem [3] guarantees that G possesses either an odd hole or an odd
antihole. Thus ∆ contains an induced subcomplex ∆′ which coincides with either
(ii) or (iii) of Lemma 2.4.
As a result, Lemma 2.5 says that IA∆ possesses no squarefree initial ideal with
respect to a reverse lexicographic order whose smallest variable corresponds to the
column 0 ∈ Zd of A∆ . This completes the proof of (iii) ⇒ (i).

Example 2.7. Let A ∈ Zd×n for which each entry of A belongs to {0, 1} and IA♯
the toric ideal of A♯ . In general, even if IA♯ possesses a squarefree initial ideal with
respect to a reverse lexicographic order whose smallest variable corresponds to the
column 0 ∈ Zd of A♯ , the matrix A♯ may not be compressed. For example, if


1 0 1 1 0 0 0
 1 1 0 0 0 0 0 




 0 1 1 0 0 0 0 
A=
,
 0 0 0 1 1 0 1 


 0 0 0 0 1 1 0 
0 0 0 0 0 1 1

then IA♯ is generated by x1 x3 x5 x7 − x2 x24 x6 . Thus the initial ideals of IA♯ with
respect to the reverse lexicographic order induced by the ordering
z < x2 < x1 < x3 < x4 < x5 < x6 < x7
9

is generated by x1 x3 x5 x7 , while the initial ideals of IA♯ with respect to the reverse
lexicographic order induced by the ordering
z < x1 < x2 < x3 < x4 < x5 < x6 < x7
is generated by x2 x24 x6 . Even though A♯ satisfies the condition (iii) of Theorem 2.6,
the integer matrix A♯ cannot be compressed.
Apart from Theorem 2.6, we can ask the problem when the convex polytope
P ⊂ Rd which is the convex hull of P∆ ∪ (−P∆′ ), where ∆ and ∆′ are simplicial
complexes on [d], is a Gorenstein Fano polytope.
Theorem 2.8. Let ∆ and ∆′ be simplicial complexes on [d] and P ⊂ Rd the convex
polytope which is the convex hull of P∆ ∪ (−P∆′ ). Then P is a Gorenstein Fano
polytope if and only if there exist perfect graphs G and G′ on [d] with ∆ = S(G) and
∆′ = S(G′ ).
Proof. The “If” part follows from Example 2.3. To see why the “Only If” part
is true, suppose that either ∆ is not flag or there is a nonperfect graph G with
∆ = S(G). Since P ⊂ Rd is a Gorenstein Fano polytope, the equation of the
supporting hyperplane H ⊂ Rd for which H ∩ P is a facet of P is of the form
a1 z1 + · · · + ad zd = 1 with each aj ∈ Z.
Let ∆ be not flag and V ⊂ [d] with |V | ≥ 3 for which V \ {i} ∈ ∆ for all i ∈ V
and V ∈
/ ∆. Let, say, V = [e] with e ≥ 3. Then the hyperplane H′ ⊂ Rd defined by
the equation z1 + · · · + ze = e − 1 is a supporting hyperplane of P. Let F be a facet
of P with H′ ∩ P ⊂ F and a1 z1 + · · · + ad zd = 1 with each aj ∈ Z the equation of
the supporting hyperplane H ⊂ Rd with F ⊂ H. Since ρ(V \ {i}) ∈ H for all i ∈ V ,
P
one has j∈[e]\{i} aj = 1. Thus (e − 1)(a1 + · · · + ae ) = e. Hence a1 + · · · + ae 6∈ Z,
a contradiction.
Let ∆ = S(G), where G possesses an odd hole C of length 2ℓ+1 with the vertices,
say, 1, . . . , 2ℓ+1, where ℓ ≥ 2. Then the hyperplane H′ ⊂ Rd defined by the equation
z1 + · · · + z2ℓ+1 = ℓ is a supporting hyperplane of P. Let F be a facet of P with
H′ ∩P ⊂ F and a1 z1 +· · ·+ad zd = 1 with each aj ∈ Z the equation of the supporting
hyperplane H ⊂ Rd with F ⊂ H. The maximal stable sets of C is
{1, 3, . . . , 2ℓ − 1}, {2, 4, . . . , 2ℓ}, . . . , {2ℓ + 1, 2, 4, . . . , 2ℓ − 2}
and each i ∈ [2ℓ − 2] appears ℓ times in the above list. Since, for each maximal
P
stable set U of C, one has i∈U ai = 1, it follows that ℓ(a1 + · · · + a2ℓ+1 ) = 2ℓ + 1.
Hence a1 + · · · + ae 6∈ Z, a contradiction.
Let ∆ = S(G), where G possesses an odd antihole C with the vertices, say,
1, . . . , 2ℓ + 1, where ℓ ≥ 2. Then the hyperplane H′ ⊂ Rd defined by the equation
z1 + · · · + z2ℓ+1 = 2 is a supporting hyperplane of P. Let F be a facet of P with
H′ ∩P ⊂ F and a1 z1 +· · ·+ad zd = 1 with each aj ∈ Z the equation of the supporting
10

hyperplane H ⊂ Rd with F ⊂ H. The maximal stable sets of C is
{1, 2}, {2, 3}, . . . , {2ℓ + 1, 1}
and each i ∈ [2ℓ − 2] appears twice in the above list. Since, for each maximal stable
P
set U of C, one has i∈U ai = 1, it follows that 2(a1 + · · · + a2ℓ+1 ) = 2ℓ + 1. Hence
a1 + · · · + ae 6∈ Z, a contradiction.

Acknowledgment. The authors are grateful to an anonymous referee for useful
suggestions and helpful comments.
References
[1] C. A. Athanasiadis, Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture
of Stanley, J. Reine Angew. Math. 583 (2005), 163–174.
[2] V. Batyrev, Dual polyhedra and mirror symmetry for Calabi–Yau hypersurfaces in toric varieties, J. Algebraic Geom. 3 (1994), 493–535.
[3] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The strong perfect graph theorem,
Ann. of Math. 164 (2006), 51–229.
[4] H. Conrads, Weighted projective spaces and reflexive simplices, Manuscripta Math. 107
(2002), 215–227.
[5] D. Cox, J. Little and H. Schenck, “Toric Varieties,” Amer. Math. Soc., Providence, RI, 2011.
[6] J. Gouveia, P. A. Parrilo and R. R. Thomas, Theta bodies for polynomial ideals, SIAM Journal
on Optimization 20 (2010), 2097–2118.
[7] G. Hegedüs and A. M. Kasprzyk, The boundary volume of a lattice polytope, Bull. Aust.
Math. Soc. 85 (2012), 84–104.
[8] J. Herzog and T. Hibi, “Monomial ideals,” Grad. Texts in Math. 260, Springer, London, 2010.
[9] T. Hibi, Dual polytopes of rational convex polytopes, Combinatorica 12 (1992), 237–240.
[10] T. Hibi, Toric varieties arising from canonical triangulations of poset polytopes are projective, in “Words, Languages and Combinatorics II” (M. Ito and H. Jurgensen, Eds.), World
Scientific, Singapore, 1994, pp. 192 – 199.
[11] T. Hibi, Ed., “Gröbner Bases: Statistics and Software Systems,” Springer, 2013.
[12] T. Hibi, K. Matsuda, H. Ohsugi and K. Shibata, Centrally symmetric configurations of order
polytopes, J. Algebra 443 (2015), 469–478.
[13] A. Higashitani, Smooth Fano polytopes arising from finite directed graphs, Kyoto J. Math.
55 (2015), 579–592.
[14] A. M. Kasprzyk, Classifying terminal weighted projective space, preprint, 2013.
arXiv:1304.3029.
[15] A. M. Kasprzyk and B. Nill, Fano polytopes, in “Strings, Gauge Fields, and the Geometry
Behind – the Legacy of Maximilian Kreuzer” (A. Rebhan, L. Katzarkov, J. Knapp, R. Rashkov,
E. Scheidegger, Eds.), World Scientific, 2012, pp. 349–364.
[16] M. Kreuzer and H. Skarke, Classification of reflexive polyhedra in three dimensions, Adv.
Theor. Math. Phys. 2 (1998), no. 4, 853–871.
[17] M. Kreuzer and H. Skarke, Complete classification of reflexive polyhedra in four dimensions,
Adv. Theor. Math. Phys. 4 (2000), no. 6, 1209–1230.
[18] B. Nill, Volume and lattice points of reflexive simplices, Discrete Comput. Geom. 37 (2007),
301–320.
11

[19] H. Ohsugi, A geometric definition of combinatorial pure subrings and Gröbner bases of toric
ideals of positive roots, Comment. Math. Univ. St. Pauli 56 (2007), 27–44.
[20] H. Ohsugi, J. Herzog and T. Hibi, Combinatorial pure subrings, Osaka J. Math 37 (2000),
745–757.
[21] H. Ohsugi and T. Hibi, Convex polytopes all of whose reverse lexicographic initial ideals are
squarefree, Proc. Amer. Math. Soc. 129 (2001), 2541–2546.
[22] H. Ohsugi and T. Hibi, Quadratic initial ideals of root systems, Proc. Amer. Math. Soc. 130
(2002), 1913–1922.
[23] H. Ohsugi and T. Hibi, Centrally symmetric configurations of integer matrices, Nagoya Math.
J. 216 (2014), 153–170.
[24] R. P. Stanley, “Combinatorics and Commutative Algebra,” Second Ed., Birkhäuser, 1996.
[25] M. W. Padberg, Perfect zero-one matrices, Math. Programming 6 (1974), 180–196.
[26] B. Sturmfels, “Gröbner bases and convex polytopes,” Amer. Math. Soc., Providence, RI, 1996.
[27] S. Sullivant, Compressed polytopes and statistical disclosure limitation, Tohoku Math. J. 58
(2006), 433 – 445.
[28] A. Wagler, Critical edges in perfect line graphs and some polyhedral consequences, Disc. Appl.
Math. 95 (1999), 455–466.
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
Takayuki Hibi, Department of Pure and Applied Mathematics, Graduate School
of Information Science and Technology, Osaka University, Toyonaka, Osaka 5600043, Japan
E-mail address: hibi@math.sci.osaka-u.ac.jp

12

