Séminaire Lotharingien de Combinatoire 59 (2008), Article B59a

GRÖBNER BASIS TECHNIQUES IN ALGEBRAIC COMBINATORICS

TAKAYUKI HIBI

Abstract. Gröbner basis techniques in the algebraic study of triangulations of convex polytopes as well as of the number of faces of simplicial complexes will be discussed. Of these two traditional topics in combinatorics, the first will be studied by using initial ideals of toric ideals and the second will be studied by using generic initial ideals of monomial ideals.

Introduction

It turns out that, in the current trends on the study of convex polytopes and simplicial complexes, the algebraic techniques based on the theory of Gröbner bases could play fundamental roles. Especially, Gröbner basis techniques exert a great influence on the developments of the traditional topics in combinatorics such as triangulations of convex polytopes and the number of faces of simplicial complexes.

The present article will provide the reader with the way how to use Gröbner bases in algebraic combinatorics. No special knowledge on commutative algebra and algebraic combinatorics will be required.

First of all, in Section 1 we will present fundamental materials on Gröbner bases as quickly as possible. Our discussion will open with Dickson’s lemma in classical combinatorics on monomials. In the language of commutative algebra, Dickson’s lemma is equivalent to saying that every monomial ideal of the polynomial ring is finitely generated. Based on Dickson’s lemma, the notion of initial ideals together with Gröbner bases will be introduced. In one word, a Gröbner basis of an ideal I of the polynomial ring is a finite set of polynomials belonging to I which enjoys certain distinguished algebraic properties. In the language of Gröbner bases, the Hilbert basis theorem is an immediate consequence of the fact that every Gröbner basis of an ideal I is a system of generators of I. On the other hand, the Buchberger criterion gives an explicit answer to the problem when a system of generators of an ideal I can be a Gröbner basis of I. Moreover, the Buchberger criterion supplies an algorithm to compute a Gröbner basis of an ideal I starting from a system of generators of I.

The theory of toric ideals is one of the fascinating topics lying between commutative algebra and combinatorics (Sturmfels [24]). Section 2 will be devoted to the basic idea of the study of triangulations of convex polytopes by using initial ideals of toric ideals. Unimodular triangulations together with flag triangulations will explain the reason why the initial ideal generated by squarefree quadratic monomials would be of interest in combinatorics. Typical examples of initial ideals generated by squarefree quadratic monomials arise from finite distributive lattices [11], classical root systems [21], finite bipartite graphs [20], and decomposable models in algebraic statistics [6].

59th Séminaire Lotharingien de Combinatoire, XIV Incontro Italiano di Combinatoria Algebrica, Bertinoro, Italy, 23 – 26 September 2007.

Algebraic shifting, introduced by Gil Kalai in 1988, is a powerful tool for the study of the number of faces of simplicial complexes. Kalai defined algebraic shifting in the framework of combinatorics. However, in Section 3, we will introduce algebraic shifting by using the notion of generic initial ideals. The generic initial ideal is one of the indispensable and fundamental tools for the developments of computational commutative algebra. Among many pending problems (Kalai [14] and Herzog [9]) related with algebraic shifting, one of the most fundamental problems is to compute the algebraic shifted complexes of simplicial spheres. A simplicial sphere is, by definition, a simplicial complex whose geometric realization is homeomorphic to the sphere. In particular the boundary complex of a simplicial polytope is a simplicial sphere. In [13] Kalai introduced the squeezed sphere and showed that the class of squeezed spheres is much bigger than that of boundary complexes of simplicial polytopes. Even though Kalai introduced the squeezed sphere in the language of combinatorics, following Murai [15] we will define the squeezed sphere by using strongly stable monomial ideals. Murai [16] succeeded in computing the algebraic shifted complexes of squeezed spheres. The final goal of Section 3 is to state this nice result due to Murai.

1. Gröbner bases

Let S = K[x_{1}, …, x_{n}] denote the polynomial ring in n variables over a field K with deg x_{i} = 1 for i = 1, 2, …, n, and let

Mon(S) = {x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{n}^{a_{n}} : a_{i} ∈ ℤ_{+}, i = 1, 2, …, n},

be the set of monomials of S, where ℤ_{+} is the set of nonnegative integers. In particular 1 ∈ Mon(S). For monomials x^{a} = x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{n}^{a_{n}} and x^{b} = x_{1}^{b_{1}}x_{2}^{b_{2}} ⋯ x_{n}^{b_{n}} of S, we say that x^{b} divides x^{a} if b_{i} ≤ a_{i} for i = 1, 2, …, n. We write x^{b} | x^{a} if x^{b} divides x^{a}. Let M be a nonempty subset of Mon(S). A monomial x^{a} ∈ M is said to be a minimal element of M with respect to divisibility if whenever x^{b} | x^{a} with x^{b} ∈ M, then x^{b} = x^{a}. Let M^{min} denote the set of minimal elements of M.

Theorem 1.1 (Dickson’s lemma). Let M be a nonempty subset of Mon(S). Then M^{min} is a finite set.

Proof. We prove Dickson’s lemma by using induction on n, the number of variables of S = K[x_{1}, x_{2}, …, x_{n}]. Let n = 1. If d is the smallest integer for which x_{1}^{d} ∈ M, then M^{min} = {x_{1}^{d}}. Thus M^{min} is a finite set.

Let n ≥ 2 and B = K[x] = K[x_{1}, x_{2}, …, x_{n−1}]. We use the notation y instead of x_{n}. Thus S = K[x_{1}, x_{2}, …, x_{n−1}, y]. Let M be a nonempty subset of Mon(S). Write N for the subset of Mon(B) which consists of those monomials x^{a}, where a ∈ ℤ_{+}^{n−1}, such that x^{a}y^{b} ∈ M for some b ≥ 0. Our induction hypothesis says that N^{min} is a finite set. Let N^{min} = {u_{1}, u_{2}, …, u_{s}}. By the definition of N, for each 1 ≤ i ≤ s, there is b_{i} ≥ 0 with u_{i}y^{b_{i}} ∈ M. Let b = max{b_{1}, b_{2}, …, b_{s}}. Now, for each 0 ≤ ξ < b, define the subset N_{ξ} of N to be

N_{ξ} = {x^{a} ∈ N : x^{a}y^{ξ} ∈ M}.

Again, our induction hypothesis says that, for each 0 ≤ ξ < b, the set N_{ξ}^{min} is finite. Let N_{ξ}^{min} = {u_{1}^{(ξ)}, u_{2}^{(ξ)}, …, u_{s_{ξ}}^{(ξ)}}. We now show that each monomial belonging to M is divisible by one of the monomials which appear in the following list:

u_{1}y^{b_{1}}, u_{2}y^{b_{2}}, …, u_{s}y^{b_{s}},
u_{1}^{(0)}, u_{2}^{(0)}, …, u_{s_{0}}^{(0)},
u_{1}^{(1)}y, u_{2}^{(1)}y, …, u_{s_{1}}^{(1)}y,
· · · · · ·
u_{1}^{(b−1)}y^{b−1}, u_{2}^{(b−1)}y^{b−1}, …, u_{s_{b−1}}^{(b−1)}y^{b−1}.

In fact, since, for each monomial w = x^{a}y^{γ} ∈ M with x^{a} ∈ Mon(B), one has x^{a} ∈ N, it follows that if γ ≥ b, then w is divisible by one of the monomials u_{1}y^{b_{1}}, u_{2}y^{b_{2}}, …, u_{s}y^{b_{s}}, and that if 0 ≤ γ < b, then w is divisible by one of the monomials u_{1}^{(γ)}y^{γ}, u_{2}^{(γ)}y^{γ}, …, u_{s_{γ}}^{(γ)}y^{γ}. Clearly, the monomials listed above are in M. Hence M^{min} is a subset of the set of monomials listed above. Thus M^{min} is finite, as desired. □

A monomial order on S is a total order < on Mon(S) such that • 1 < u for all 1 ≠ u ∈ Mon(S);

• if u, v ∈ Mon(S) and u < v, then uw < vw for all w ∈ Mon(S).

Example 1.2. (a) Let a = (a_{1}, a_{2}, …, a_{n}) and b = (b_{1}, b_{2}, …, b_{n}) be vectors belonging to ℤ_{+}^{n}. We define the total order <_{lex} on Mon(S) by setting x^{a} <_{lex} x^{b} if either (i) ∑_{i=1}^{n} a_{i} < ∑_{i=1}^{n} b_{i}, or (ii) ∑_{i=1}^{n} a_{i} = ∑_{i=1}^{n} b_{i} and the left-most nonzero component of the vector a − b is negative. It follows that <_{lex} is a monomial order on S, which is called the lexicographic order on S induced by the ordering x_{1} > x_{2} > ⋯ > x_{n}.

(b) Let a = (a_{1}, a_{2}, …, a_{n}) and b = (b_{1}, b_{2}, …, b_{n}) be vectors belonging to ℤ_{+}^{n}. We define the total order <_{rev} on Mon(S) by setting x^{a} <_{rev} x^{b} if either (i) ∑_{i=1}^{n} a_{i} < ∑_{i=1}^{n} b_{i}, or (ii) ∑_{i=1}^{n} a_{i} = ∑_{i=1}^{n} b_{i} and the right-most nonzero component of the vector a−b is positive. It follows that <_{rev} is a monomial order on S, which is called the reverse lexicographic order on S induced by the ordering x_{1} > x_{2} > ⋯ > x_{n}.

For example, x_{2}x_{3} <_{lex} x_{1}x_{4} and x_{1}x_{4} <_{rev} x_{2}x_{3} in K[x_{1}, x_{2}, x_{3}, x_{4}]. Among the monomials of degree 2 of K[x_{1}, x_{2}, x_{3}], one has

x_{3}^{2} <_{lex} x_{2}x_{3} <_{lex} x_{2}^{2} <_{lex} x_{1}x_{3} <_{lex} x_{1}x_{2} <_{lex} x_{1}^{2}

and

x_{3}^{2} <_{rev} x_{2}x_{3} <_{rev} x_{1}x_{3} <_{rev} x_{2}^{2} <_{rev} x_{1}x_{2} <_{rev} x_{1}^{2}.

Exercise 1.3. List the 10 monomials of degree 3 of K[x_{1}, x_{2}, x_{3}] with respect to each of <_{lex} and <_{rev}.

Lemma 1.4. Let < be a monomial order on S. Let u, v ∈ Mon(S) with u ≠ v and suppose that u divides v. Then u < v.

Proof. Write v = uw with w ∈ Mon(S). Since w ≠ 1, one has 1 < w. Thus 1 · u < w · u. Hence u < v, as desired. □

We will work with a fixed monomial order < on S. Let f = ∑_{u∈Mon(S)} a_{u}u be a nonzero polynomial of S with each a_{u} ∈ K. The support of f is the finite set

supp(f) = {u ∈ Mon(S) : a_{u} ≠ 0}.

The initial monomial of f with respect to < is the biggest monomial with respect to < among the monomials belonging to supp(f).

Recall that an ideal of S is a nonempty subset I of S such that • if f, g ∈ I, then f ± g ∈ I;

• if f ∈ I and h ∈ S, then fh ∈ I. Given a subset {f_{λ}}_{λ∈Λ} of S, we write ({f_{λ}}_{λ∈Λ}) for the set of polynomials of the form ∑_{λ∈Λ} h_{λ}f_{λ}, where {λ ∈ Λ : h_{λ} ≠ 0} is finite. Then ({f_{λ}}_{λ∈Λ}) is an ideal of S, which is called the ideal of S generated by {f_{λ}}_{λ∈Λ}. When Λ is finite, say, Λ = {1, 2, …, s}, we write (f_{1}, f_{2}, …, f_{s}) instead of ({f_{1}, f_{2}, …, f_{s}}). Conversely, given an ideal I of S, there exists a subset ({f_{λ}}_{λ∈Λ}) of S with I = ({f_{λ}}_{λ∈Λ}). We call {f_{λ}}_{λ∈Λ} a system of generators of I. We say that an ideal I of S is finitely generated if I possesses a system of generators consisting of a finite number of polynomials. Later, we will see that every ideal of S is finitely generated (Corollary 1.9).

A monomial ideal is an ideal which is generated by a set of monomials. Let I ⊂ S be a monomial ideal. It follows that I is generated by a subset N ⊂ Mon(S) if and only if (I ∩ Mon(S))^{min} ⊂ N. Hence (I ∩ Mon(S))^{min} is a unique minimal system of monomial generators of I. Dickson’s lemma guarantees that (I ∩ Mon(S))^{min} is finite. Thus in particular every monomial ideal is finitely generated.

Let I be a nonzero ideal of S. The initial ideal of I with respect to < is the monomial ideal of S which is generated by {in_{<}(f) : 0 ≠ f ∈ I }. We write in_{<}(I) for the initial ideal of I. Thus

in_{<}(I) = ({in_{<}(f) : 0 ≠ f ∈ I }).

Since (in_{<}(I) ∩ Mon(S))^{min} is a minimal system of monomial generators of in_{<}(I), and since in_{<}(I) ∩ Mon(S) = ({in_{<}(f) : 0 ≠ f ∈ I }), there exists a finite number of nonzero polynomials g_{1}, g_{2}, …, g_{s} belonging to I such that in_{<}(I) is generated by the set {in_{<}(g_{1}), in_{<}(g_{2}), …, in_{<}(g_{s})} of their initial monomials.

Definition 1.5. Let I be a nonzero ideal of S. A finite set {g_{1}, g_{2}, …, g_{s}} of nonzero polynomials with each g_{i} ∈ I is said to be a Gröbner basis of I with respect to < if the initial ideal in_{<}(I) of I is generated by the set {in_{<}(g_{1}), in_{<}(g_{2}), …, in_{<}(g_{s})} of their initial monomials.

A Gröbner basis of I with respect to < exists. If G is a Gröbner basis of I with respect to <, then every finite set G′ with G ⊂ G′ ⊂ I is also a Gröbner basis of I with respect to <. If G = {g_{1}, …, g_{s}} is a Gröbner basis of I with respect to < and if f_{1}, …, f_{s} are nonzero polynomials belonging to I with each in_{<}(f_{i}) = in_{<}(g_{i}), then {f_{1}, …, f_{s}} is also a Gröbner basis of I with respect to <.

Example 1.6. Let S = K[x_{1}, x_{2}, …, x_{7}] and I = (f, g), where f = x_{1}x_{4} − x_{2}x_{3} and g = x_{4}x_{7} − x_{5}x_{6}. Let <_{lex} the lexicographic order on S induced by x_{1} > x_{2} > ⋯ > x_{7}. One has in_{<_{lex}}(f) = x_{1}x_{4} and in_{<_{lex}}(g) = x_{4}x_{7}. We claim that {f, g} is not a Gröbner basis of I with respect to <_{lex}. In fact, the polynomial h = x_{7}f − x_{1}g = x_{1}x_{5}x_{6} − x_{2}x_{3}x_{7} belongs to I, but its initial monomial in_{<_{lex}}(h) = x_{1}x_{5}x_{6} can be divided by neither in_{<_{lex}}(f) nor in_{<_{lex}}(g). Hence in_{<_{lex}}(h) ∉ (in_{<_{lex}}(f), in_{<_{lex}}(g)). Thus in_{<_{lex}}(I) ≠ (in_{<_{lex}}(f), in_{<_{lex}}(g)). In other words, {f, g} is not a Gröbner basis of I with respect to <_{lex}. Later, we will show that {f, g, h} is a Gröbner basis of I with respect to <_{lex} (Example 1.16).

Lemma 1.7. Let < be a monomial order on S = K[x_{1}, …, x_{n}]. Then, for any monomial u of S, there is no infinite descending sequence of the form

u = u_{0} > u_{1} > u_{2} > · · · . (1)

Proof. Suppose, on the contrary, that one has an infinite descending sequence (1) and write M for the set of monomials {u_{0}, u_{1}, u_{2}, …}. It follows from Dickson’s lemma that M^{min} is a finite set, say M^{min} = {u_{i_{1}}, u_{i_{2}}, …, u_{i_{s}}} with i_{1} < i_{2} < ⋯ < i_{s}. Then the monomial u_{i_{s}+1} is divided by u_{i_{j}} for some 1 ≤ j ≤ s. Thus by Lemma 1.4 one has u_{i_{j}} < u_{i_{s}+1}, which contradicts i_{j} < i_{s} + 1. □

Theorem 1.8. Let I be a nonzero ideal of S = K[x_{1}, …, x_{n}] and G = {g_{1}, …, g_{s}} a Gröbner basis of I with respect to a monomial order < on S. Then I = (g_{1}, …, g_{s}). In other words, every Gröbner basis of I is a system of generators of I.

Proof. (Gordan) Let 0 ≠ f ∈ I. Since in_{<}(f) ∈ in_{<}(I) and since G is a Gröbner basis of I, i.e., in_{<}(I) = (in_{<}(g_{1}), …, in_{<}(g_{s})), it follows that there is g_{i_{0}} such that in_{<}(g_{i_{0}}) divides in_{<}(f). Let in_{<}(f) = w_{0} in_{<}(g_{i_{0}}) with w_{0} ∈ Mon(S). Let h_{0} = f − c_{i_{0}}^{−1}c_{0}w_{0}g_{i_{0}}, where c_{0} is the coefficient of in_{<}(f) in f and where c_{i_{0}} is the coefficient of in_{<}(g_{i_{0}}) in g_{i_{0}}. Then h_{0} ∈ I. Since in_{<}(w_{0}g_{i_{0}}) = w_{0} in_{<}(g_{i_{0}}) it follows that in_{<}(h_{0}) < in_{<}(f). If h_{0} = 0, then f ∈ (g_{1}, …, g_{s}).

Let h_{0} ≠ 0. Then the same technique as we used for f can be applied for h_{0}. Thus h_{1} = f − c_{i_{1}}^{−1}c_{1}w_{1}g_{i_{1}} − c_{i_{0}}^{−1}c_{0}w_{0}g_{i_{0}}, where c_{1} is the coefficient of in_{<}(h_{0}) in h_{0} and where c_{i_{1}} is the coefficient of in_{<}(g_{i_{1}}) in g_{i_{1}}. Then h_{1} ∈ I and in_{<}(h_{1}) < in_{<}(h_{0}). If h_{1} = 0, then f ∈ (g_{1}, …, g_{s}).

If h_{1} ≠ 0, then we proceed as before. Lemma 1.7 guarantees that this procedure must terminate. Thus we obtain an expression of the form f = ∑_{q=0}^{N} c_{i_{q}}^{−1}c_{q}w_{q}g_{i_{q}}. In particular, f belongs to (g_{1}, g_{2}, …, g_{s}). Thus I = (g_{1}, g_{2}, …, g_{s}), as desired. □

Corollary 1.9 (Hilbert basis theorem). Every ideal of the polynomial ring S = K[x_{1}, …, x_{n}] is finitely generated.

It is natural to ask if the converse of Theorem 1.8 is true or false. That is to say, if I = (f_{1}, f_{2}, …, f_{s}) is an ideal of S = K[x_{1}, …, x_{n}], then does there exist a monomial order < on S such that {f_{1}, f_{2}, …, f_{s}} is a Gröbner basis of I with respect to < ?

Example 1.10 ([18]). Let S = K[x_{1}, x_{2}, …, x_{10}] and I the ideal of S generated by

f_{1} = x_{1}x_{8} − x_{2}x_{6}, f_{2} = x_{2}x_{9} − x_{3}x_{7}, f_{3} = x_{3}x_{10} − x_{4}x_{8},

f_{4} = x_{4}x_{6} − x_{5}x_{9}, f_{5} = x_{5}x_{7} − x_{1}x_{10}.

We claim that there exists no monomial order < on S such that {f_{1}, …, f_{5}} is a Gröbner basis of I with respect to <.

Suppose, on the contrary, that there exists a monomial order < on S such that G = {f_{1}, …, f_{5}} is a Gröbner basis of I with respect to <. First, note that each of the five polynomials

x_{1}x_{8}x_{9} − x_{3}x_{6}x_{7}, x_{2}x_{9}x_{10} − x_{4}x_{7}x_{8}, x_{2}x_{6}x_{10} − x_{5}x_{7}x_{8},

x_{3}x_{6}x_{10} − x_{5}x_{8}x_{9}, x_{1}x_{9}x_{10} − x_{4}x_{6}x_{7}

belongs to I. Let, say, x_{1}x_{8}x_{9} > x_{3}x_{6}x_{7}. Since x_{1}x_{8}x_{9} ∈ in_{<}(I), there is g ∈ G such that in_{<}(g) divides x_{1}x_{8}x_{9}. Such g ∈ G must be f_{1}. Hence x_{1}x_{8} > x_{2}x_{6}. Thus x_{2}x_{6} ∉ in_{<}(I). Hence there exists no g ∈ G such that in_{<}(g) divides x_{2}x_{6}x_{10}. Hence x_{2}x_{6}x_{10} < x_{5}x_{7}x_{8}. Thus x_{5}x_{7} > x_{1}x_{10}. Continuing these arguments, we obtain

x_{1}x_{8}x_{9} > x_{3}x_{6}x_{7}, x_{2}x_{9}x_{10} > x_{4}x_{7}x_{8}, x_{2}x_{6}x_{10} < x_{5}x_{7}x_{8},

x_{3}x_{6}x_{10} > x_{5}x_{8}x_{9}, x_{1}x_{9}x_{10} < x_{4}x_{6}x_{7}

and

x_{1}x_{8} > x_{2}x_{6}, x_{2}x_{9} > x_{3}x_{7}, x_{3}x_{10} > x_{4}x_{8},
x_{4}x_{6} > x_{5}x_{9}, x_{5}x_{7} > x_{1}x_{10}.

Hence

(x_{1}x_{8})(x_{2}x_{9})(x_{3}x_{10})(x_{4}x_{6})(x_{5}x_{7}) > (x_{2}x_{6})(x_{3}x_{7})(x_{4}x_{8})(x_{5}x_{9})(x_{1}x_{10}). (2)

The opposite relation in (2) occurs in case of x_{1}x_{8}x_{9} < x_{3}x_{6}x_{7}. However, both sides of the inequality (2) coincide with x_{1}x_{2} ⋯ x_{10}.

In high school mathematics, we learn that, given polynomials f and g ≠ 0 in one variable x, there exist unique polynomials q and r such that f = gq +r, where either r = 0 or deg r < deg g. The division algorithm generalizes this well-known result.

Theorem 1.11 (Division algorithm). Let S = K[x_{1}, …, x_{n}] denote the polynomial ring in n variables over a field K and fix a monomial order < on S. Let g_{1}, g_{2}, …, g_{s} be nonzero polynomials of S. Then, given a polynomial 0 ≠ f ∈ S, there exist polynomials f_{1}, f_{2}, …, f_{s} and f′ of S with

f = f_{1}g_{1} + f_{2}g_{2} + ⋯ + f_{s}g_{s} + f′ (3)

such that the following conditions are satisfied:

(i) if f′ ≠ 0 and if u ∈ supp(f′), then none of in_{<}(g_{1}), …, in_{<}(g_{s}) divides u, i.e., no u ∈ supp(f′) belongs to (in_{<}(g_{1}), …, in_{<}(g_{s}));

(ii) if f_{i} ≠ 0, then

in_{<}(f_{i}g_{i}) ≤ in_{<}(f).

The right hand side of equation (3) is said to be a standard expression for f with respect to g_{1}, g_{2}, …, g_{s}, and the polynomial f′ is called a remainder of f with respect to g_{1}, g_{2}, …, g_{s}.

Instead of giving a detailed proof of Theorem 1.11, we discuss a typical example which clearly explains the procedure to obtain a standard expression.

Example 1.12. Let <_{lex} denote the lexicographic order on S = K[x, y, z] induced by x > y > z. Let g_{1} = x^{2} − z, g_{2} = xy − 1 and f = x^{3} − x^{2}y − x^{2} − 1. Each of

f = x^{3} − x^{2}y − x^{2} − 1 = x(g_{1} + z) − x^{2}y − x^{2} − 1
= xg_{1} − x^{2}y − x^{2} + xz − 1 = xg_{1} − (g_{1} + z)y − x^{2} + xz − 1
= xg_{1} − yg_{1} − x^{2} + xz − yz − 1 = xg_{1} − yg_{1} − (g_{1} + z) + xz − yz − 1
= (x − y − 1)g_{1} + (xz − yz − z − 1)

and

f = x^{3} − x^{2}y − x^{2} − 1 = x(g_{1} + z) − x^{2}y − x^{2} − 1
= xg_{1} − x^{2}y − x^{2} + xz − 1 = xg_{1} − x(g_{2} + 1) − x^{2} + xz − 1
= xg_{1} − xg_{2} − x^{2} + xz − x − 1 = xg_{1} − xg_{2} − (g_{1} + z) + xz − x − 1
= (x − 1)g_{1} − xg_{2} + (xz − x − z − 1)

is a standard expression of f with respect to g_{1} and g_{2}, and each of xz − yz − z − 1 and xz − x − z − 1 is a remainder of f.

Example 1.12 says that a remainder of a nonzero polynomial may not be unique. However, we have the following fact.

Lemma 1.13. If G = {g_{1}, …, g_{s}} is a Gröbner basis of I = (g_{1}, …, g_{s}), then for any nonzero polynomial f of S, there is a unique remainder of f with respect to g_{1}, …, g_{s}.

Proof. Suppose there exist remainders f′ and f′′ with respect to g_{1}, …, g_{s} with f′ ≠ f′′. Since 0 ≠ f′ − f′′ ∈ I, the initial monomial w = in_{<}(f′ − f′′) must belong to in_{<}(I). However, since w ∈ supp(f′) ∪ supp(f′′), none of the monomials in_{<}(g_{1}), …, in_{<}(g_{s}) divides w. Hence in_{<}(I) ≠ (in_{<}(g_{1}), …, in_{<}(g_{s})). □

Given nonzero polynomials f and g of S, the notation lcm(in_{<}(f), in_{<}(g)) stands for the least common multiple of in_{<}(f) and in_{<}(g). Let c_{f} denote the coefficient of in_{<}(f) in f and c_{g} the coefficient of in_{<}(g) in g. The polynomial

S(f, g) = \frac{lcm(in_{<}(f), in_{<}(g))}{c_{f} in_{<}(f)}f − \frac{lcm(in_{<}(f), in_{<}(g))}{c_{g} in_{<}(g)}g

is called the S-polynomial of f and g.

We say that f has remainder 0 with respect to g_{1}, g_{2}, …, g_{s} if, in the division algorithm, there is a standard expression (3) of f with respect to g_{1}, g_{2}, …, g_{s} with f′ = 0.

Lemma 1.14. Let f and g be nonzero polynomials and suppose that in_{<}(f) and in_{<}(g) are relatively prime, i.e., lcm(in_{<}(f), in_{<}(g)) = in_{<}(f) in_{<}(g). Then S(f, g) has remainder 0 with respect to f, g.

Proof. To simplify notation we will assume that each of the coefficients of in_{<}(f) in f and in_{<}(g) in g is equal to 1. Let f = in_{<}(f) + f_{1} and g = in_{<}(g) + g_{1}. Since in_{<}(f) and in_{<}(g) are relatively prime, it follows that

S(f, g) = in_{<}(g)f − in_{<}(f)g
= (g − g_{1})f − (f − f_{1})g
= f_{1}g − g_{1}f.

We claim (in_{<}(f_{1}) in_{<}(g) =) in_{<}(f_{1}g) ≠ in_{<}(g_{1}f) (= in_{<}(g_{1}) in_{<}(f)). In fact, if in_{<}(f_{1}) in_{<}(g) = in_{<}(g_{1}) in_{<}(f), then, since in_{<}(f) and in_{<}(g) are relatively prime, it follows that in_{<}(f) must divide in_{<}(f_{1}). However, since in_{<}(f_{1}) < in_{<}(f), this is impossible. Let, say, in_{<}(f_{1}) in_{<}(g) < in_{<}(g_{1}) in_{<}(f). Then in_{<}(S(f, g)) = in_{<}(g_{1}f) and S(f, g) = f_{1}g − g_{1}f turns out to be a standard expression of S(f, g) in terms of f and g. Hence S(f, g) has remainder 0 with respect to f and g, and similarly for in_{<}(g_{1}) in_{<}(f) < in_{<}(f_{1}) in_{<}(g). □

We now come to the most fundamental theorem in the theory of Gröbner bases.

Theorem 1.15 (Buchberger criterion). Let I be a nonzero ideal of S and G = {g_{1}, g_{2}, …, g_{s}} a system of generators of I. Then G is a Gröbner basis of I if and only if the following condition is satisfied:

(∗) For all i ≠ j, S(g_{i}, g_{j}) has remainder 0 with respect to g_{1}, …, g_{s}.

We refer the reader to a standard textbook on Gröbner bases, e.g., [1], [4] and [5] for a proof of the Buchberger criterion. However, for a (general) Gröbner basis “user,” it may not be required to understand a detailed proof of the Buchberger criterion.

In Example 1.6, by using Lemma 1.14 together with the Buchberger criterion, it follows immediately that the set {f, g} is a Gröbner basis of I = (f, g) with respect to the reverse lexicographic order <_{rev} induced by x_{1} > x_{2} > ⋯ > x_{7}.

The Buchberger criterion supplies an algorithm to compute a Gröbner basis starting from a system of generators of an ideal.

Let {g_{1}, g_{2}, …, g_{s}} be a system of generators of a nonzero ideal I of S and suppose that {g_{1}, g_{2}, …, g_{s}} is not a Gröbner basis of I. The Buchberger criterion then guarantees that there is an S-polynomial S(g_{i}, g_{j}) such that no remainder of S(g_{i}, g_{j}) with respect to g_{1}, g_{2}, …, g_{s} is 0. Let h_{ij} ∈ I be a remainder of a standard expression of S(g_{i}, g_{j}) with respect to g_{1}, g_{2}, …, g_{s}. Then in_{<}(h_{ij}) can be divided by none of the monomials in_{<}(g_{1}), in_{<}(g_{2}), …, in_{<}(g_{s}). In other words, the inclusion

(in_{<}(g_{1}), in_{<}(g_{2}), …, in_{<}(g_{s})) ⊂ (in_{<}(g_{1}), in_{<}(g_{2}), …, in_{<}(g_{s}), in_{<}(h_{ij})).

is strict. With setting g_{s+1} = h_{ij}, suppose that {g_{1}, g_{2}, …, g_{s}, g_{s+1}} is not a Gröbner basis of I. Again, by using the Buchberger criterion, there is a S-polynomial S(g_{k}, g_{ℓ}) such that no remainder of S(g_{k}, g_{ℓ}) with respect to g_{1}, g_{2}, …, g_{s}, g_{s+1} is 0. Let h_{kℓ} ∈ I be a remainder of S(g_{k}, g_{ℓ}) with respect to g_{1}, g_{2}, …, g_{s}, g_{s+1}. Then the inclusion

(in_{<}(g_{1}), in_{<}(g_{2}), …, in_{<}(g_{s}), in_{<}(g_{s+1})) ⊂ (in_{<}(g_{1}), in_{<}(g_{2}), …, in_{<}(g_{s}), in_{<}(g_{s+1}), in_{<}(h_{kℓ})).

is strict. By virtue of Dickson’s lemma, these procedures must terminate after a finite number of steps, and a Gröbner basis of I can be obtained.

The above algorithm to find a Gröbner basis starting from a system of generators of an ideal is said to be the Buchberger algorithm.

Example 1.16. We continue Example 1.6. Let S = K[x_{1}, x_{2}, …, x_{7}] and <_{lex} the lexicographic order on S induced by x_{1} > x_{2} > ⋯ > x_{7}. Let f = x_{1}x_{4} − x_{2}x_{3} and g = x_{4}x_{7} − x_{5}x_{6}. Thus in_{<_{lex}}(f) = x_{1}x_{4} and in_{<_{lex}}(g) = x_{4}x_{7}. Let I = (f, g). Then {f, g} is not a Gröbner basis of I with respect to <_{lex}. Now, as a remainder of S(f, g) = x_{7}f − x_{1}g = x_{1}x_{5}x_{6} − x_{2}x_{3}x_{7} with respect to f and g, we choose S(f, g) itself. Let h = x_{1}x_{5}x_{6} −x_{2}x_{3}x_{7} with in_{<_{lex}}(h) = x_{1}x_{5}x_{6}. Then in_{<_{lex}}(g) and in_{<_{lex}}(h) are relatively prime. On the other hand, S(f, h) = x_{2}x_{3}(x_{4}x_{7} − x_{5}x_{6}) has remainder 0 with respect to f, g, h. It follows from the Buchberger criterion that {f, g, h} is a Gröbner basis of I with respect to <_{lex}.

2. Initial ideals and triangulations of convex polytopes

Let A = (a_{ij})_{{1≤i≤d \atop 1≤j≤n}} ∈ ℤ^{d×n}, i.e., A is a d × n integer matrix, with a_{1}, …, a_{n} their column vectors. Such a matrix A is called a configuration if there exists a vector c ∈ ℝ^{d} such that ⟨a_{j}, c⟩ = 1 for each 1 ≤ j ≤ n, where ⟨a_{j}, c⟩ is the usual inner product in ℝ^{d}.

Let, as before, S = K[x_{1}, …, x_{n}] denote the polynomial ring in n variables over a field K with deg x_{i} = 1 for i = 1, 2, …, n. If b = (b_{1}, …, b_{n}) ∈ ℤ^{n}, then we define the binomial

f_{b} = ∏_{b_{i}>0} x_{i}^{b_{i}} − ∏_{b_{i}<0} x_{i}^{−b_{i}}

of S. For example, if n = 5 and b = (−1, 3, 2, 0, −4), then f_{b} = x_{2}^{3}x_{3}^{2} − x_{1}x_{5}^{4}.

The toric ideal of a configuration A ∈ ℤ^{d×n} is the ideal I_{A} of S which is generated by those binomials f_{b} with A b^{⊤} = 0, where b ∈ ℤ^{n} and where b^{⊤} stands for the transposed matrix of b. Thus

I_{A} = ( { f_{b} : b ∈ ℤ^{n}, A b^{⊤} = 0 }).

The convex polytope arising from a configuration A ∈ ℤ^{d×n} is the convex polytope P_{A} ⊂ ℝ^{d} which is the convex hull of the column vectors a_{1}, …, a_{n} of A.

Fix a monomial order < on S and write, as before, in_{<}(I_{A}) for the initial ideal of I_{A} with respect to <.

Example 2.1. The 4 × 5 matrix

A = [ \begin{matrix}0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{matrix} ]

is a configuration, since (0, 0, 0, 1) A = (1, 1, 1, 1). The toric ideal I_{A} is generated by the binomial x_{1}x_{5}^{2} − x_{2}x_{3}x_{4} and the convex polytope P_{A} ⊂ ℝ^{4} is a bipyramid on a triangle. One has either in_{<}(I_{A}) = (x_{1}x_{5}^{2}) or in_{<}(I_{A}) = (x_{2}x_{3}x_{4}).

We now discuss the triangulations of the convex polytope P_{A} ⊂ ℝ^{d} arising from a configuration A ∈ ℤ^{d×n}. Let a_{1}, …, a_{n} be the column vectors of A. To simplify the situation, we may assume that the additive group ℤ^{d} is generated by the set {a_{1}, …, a_{n}} of column vectors. In other words, every vector belonging to ℤ^{d} is of the form c_{1}a_{1} +⋯+c_{n}a_{n} with each c_{j} ∈ ℤ. In particular, since A is a configuration, it follows that the dimension of P_{A} is d − 1.

When ℤ^{d} cannot be generated by the set {a_{1}, …, a_{n}} of column vectors of A, write L for the subgroup of ℤ^{d} generated by the set of column vectors of A. Thus L ≃ ℤ^{e} with e < d. Let {a_{i_{1}}, …, a_{i_{e}}} with 1 ≤ i_{1} < ⋯ < i_{e} ≤ n be a ℤ-basis of L. Each vector a ∈ L has a unique expression of the form a = ∑_{j=1}^{e} q_{j}a_{i_{j}} with each q_{j} ∈ ℤ. We then introduce the ℤ-isomorphism ψ : L → ℤ^{e} by setting ψ(a) = (q_{1}, …, q_{e})^{⊤}. Let A′ = (a′_{ij})_{{1≤i≤e \atop 1≤j≤n}} denote the e × n integer matrix with the column vectors φ(a_{1}), …, φ(a_{n}). Since A is a configuration, it follows that ∑_{i=1}^{e} a′_{ij} = 1 for each 1 ≤ j ≤ n. Thus A′ ∈ ℤ^{e×n} is a configuration and the set of columns of A′ generates ℤ^{e}. Clearly discussing the toric ideal and the triangulations of A is equivalent to discussing the toric ideal and the triangulations of A′.

Example 2.2. The 3 × 5 matrix

A = [ \begin{matrix}0 & 2 & 0 & 1 & 1 \\ 0 & 0 & 2 & 1 & −1 \\ 1 & 1 & 1 & 1 & 1 \end{matrix} ]

is a configuration. The additive group L generated by the set {a_{1}, …, a_{5}} of column vectors of A is L = {(a_{1}, a_{2}, a_{3}) ∈ ℤ^{3} : a_{1} + a_{2} ∈ 2 · ℤ}, where 2 · ℤ is the set of even integers, with {a_{1}, a_{4}, a_{5}} its ℤ-basis. One has

A′ = [ \begin{matrix}1 & −1 & −1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & −1 & 0 & 1 \end{matrix} ] .

Given a subset F = {a_{i_{1}}, …, a_{i_{r}}} of {a_{1}, …, a_{n}}, the notation conv(F) stands for the convex hull of a_{i_{1}}, …, a_{i_{r}} in ℝ^{d}. A subset F of {a_{1}, …, a_{n}} is called a simplex belonging to A if conv(F) is an (r − 1)-simplex in ℝ^{d}, where r = |F |. Every subset of a simplex belonging to A is again a simplex belonging to A. A simplex F = {a_{i_{1}}, …, a_{i_{r}}} belonging to A is called unimodular if F is a subset of a ℤ-basis of ℤ^{d}. If F is unimodular and if F′ ⊂ F, then F′ is again unimodular.

A triangulation of P_{A} ⊂ ℝ^{d} is a collection Δ of simplices belonging to A such that • If F belongs to Δ and F′ ⊂ F, then F′ belongs to Δ;

• If F and G belong to Δ, then conv(F) ∩ conv(G) = conv(F ∩ G);

• P_{A} = ⋃_{F ∈Δ} conv(F). Each simplex F ∈ Δ is called a face of Δ. A facet of Δ is a face F of Δ with

|F | = d. A triangulation Δ of P_{A} is called unimodular if every F ∈ Δ is unimodular. A simplex F belonging to A is called a nonface of Δ if F ∉ Δ. A triangulation Δ of P_{A} is called flag if every minimal nonface of Δ is a 2-element subset of {a_{1}, …, a_{n}}.

Why is a unimodular triangulation of interest in combinatorics? Let c ∈ ℝ^{d} with ⟨a_{j}, c⟩ = 1 for each j and H ⊂ ℝ^{d} the hyperplane {a ∈ ℝ^{d} : ⟨a, c⟩ = 1}. One has P_{A} ⊂ H. Fix an invertible affine transformation ϱ : H → ℝ^{d−1} with ϱ(ℤ^{d} ∩ H) = ℤ^{d−1}. The image ϱ(P_{A}) of P_{A} under ϱ is a convex polytope in ℝ^{d−1} of dimension d − 1. Hence the volume (Lebesgue measure) vol(ϱ(P_{A})) of ϱ(P_{A}) is positive and is independent of the particular choice of ϱ. We call the positive integer (d − 1)! vol(ϱ(P_{A})) the normalized volume of P_{A}. If Δ is a triangulation of P_{A}, then it follows that the number of the facets of Δ is at most the normalized volume of P_{A} and is equal to the normalized volume of P_{A} if and only if Δ is unimodular. Consequently, the existence of a unimodular triangulation of P_{A} makes it easy to compute the normalized volume of P_{A}.

Remark 2.3. A combinatorial way to see the reason why vol(ϱ(P_{A})) is independent of the particular choice of ϱ is to show that the Ehrhart polynomial [10, p. 80] of P_{A} coincides with that of ϱ(P_{A}). It is well known, e.g., [23, Theorem 10.3, p. 45] and [10, Proposition (28.5)] that the leading coefficient of the Ehrhart polynomial of ϱ(P_{A}) is vol(ϱ(P_{A})).

Why is a flag triangulation of interest in combinatorics? Given a triangulation Δ of P_{A}, we write G_{Δ} for the finite graph on [n] = {1, …, n} whose edges, E(G_{Δ}), are those {i, j}, where i ≠ j, with {a_{i}, a_{j}} ∈ Δ. We call G_{Δ} the skeleton of Δ, and we denote the set of edges by E(G_{Δ}), as usual. A clique of G_{Δ} is a subset C ⊂ [n] such that {i, j} ∈ E(G_{Δ}) for all i, j ∈ C with i ≠ j. Let C(G_{Δ}) denote the set of cliques of G_{Δ}. It then follows that Δ ⊂ {{a_{i} : i ∈ C} : C ∈ C(G_{Δ})} and that Δ = {{a_{i} : i ∈ C} : C ∈ C(G_{Δ})} if and only if Δ is flag. Consequently, when Δ is flag, we can discuss the combinatorics on Δ (for example, the number of faces of Δ) in terms of the combinatorics on the skeleton G_{Δ} of Δ.

Example 2.4. Let A be the configuration discussed in Example 2.1. The simplices belonging to A are

F_{1} = {a_{1}, a_{2}, a_{3}, a_{4}}, F_{2} = {a_{2}, a_{3}, a_{4}, a_{5}},
F_{3} = {a_{1}, a_{5}, a_{2}, a_{3}}, F_{4} = {a_{1}, a_{5}, a_{2}, a_{4}}, F_{5} = {a_{1}, a_{5}, a_{3}, a_{4}},

together with their subsets. Since {a_{1}, a_{2}, a_{3}, a_{4}} cannot be a ℤ-basis of ℤ^{4}, it follows that F_{1} is not unimodular. Each of the simplices F_{2}, F_{3}, F_{4} and F_{5} is unimodular.

Let Δ_{1} be the triangulation of P_{A} with the facets F_{1}, F_{2}, and let Δ_{2} be the triangulation of P_{A} with the facets F_{3}, F_{4}, F_{5}. Then Δ_{1} is flag and Δ_{2} is unimodular. Since F_{1} ∈ Δ_{1}, it follows that Δ_{1} is not unimodular. Since {a_{2}, a_{3}, a_{4}} is a minimal nonface of Δ_{2}, it follows that Δ_{2} is not flag.

Let A ∈ ℤ^{d×n} be a configuration with a_{1}, …, a_{n} its columns and P_{A} ⊂ ℝ^{d} the convex polytope arising from A. Let I_{A} ⊂ S be the toric ideal of A and in_{<}(I_{A}) the initial ideal of I_{A} with respect to a monomial order < on S. For a monomial u = x_{1}^{a_{1}} ⋯ x_{n}^{a_{n}}, the notation \sqrt{u} stands for the squarefree monomial ∏_{i: a_{i}>0} x_{i}. For example, if u = x_{1}x_{3}^{5}x_{4}^{2}, then \sqrt{u} = x_{1}x_{3}x_{4}. Moreover, when in_{<}(I_{A}) is generated by monomials u_{1}, …, u_{s}, the notation \sqrt{in_{<}(I_{A})} stands for the ideal of S which is generated by the squarefree monomials \sqrt{u_{1}}, …, \sqrt{u_{s}}. Since a monomial ideal possesses a unique minimal system of monomial generators, it follows that \sqrt{in_{<}(I_{A})} is independent of the particular choice of a system of monomial generators of I_{A}.

Lemma 2.5. Let F be a subset of {a_{1}, …, a_{n}} and suppose that

∏_{a_{i}∈F} x_{i} ∉ \sqrt{in_{<}(I_{A})}. (4)

Then F is a simplex belonging to A.

Theorem 2.6 (Sturmfels [24]). Write Δ(in_{<}(I_{A})) for the set of those simplices F of A satisfying (4). Then Δ(in_{<}(I_{A})) is a triangulation of P_{A}.

Such a triangulation Δ(in_{<}(I_{A})) of P_{A} is called a regular triangulation of P_{A}. A typical example of a nonregular triangulation appears in, say, [24]. Now, it is natural to ask when a regular triangulation Δ(in_{<}(I_{A})) is unimodular or flag.

Theorem 2.7 ([24]). A regular triangulation Δ(in_{<}(I_{A})) of P_{A} is unimodular if and only if in_{<}(I_{A}) is generated by squarefree monomials, i.e., in_{<}(I_{A}) = \sqrt{in_{<}(I_{A})}.

Lemma 2.8. A regular triangulation Δ(in_{<}(I_{A})) of P_{A} is flag if and only if \sqrt{in_{<}(I_{A})} is generated by quadratic monomials.

Corollary 2.9. A regular triangulation Δ(in_{<}(I_{A})) of P_{A} is unimodular and flag if and only if in_{<}(I_{A}) is generated by squarefree quadratic monomials.

Example 2.10. Let Δ_{1} and Δ_{2} be the triangulations of P_{A} discussed in Example 2.4. Recall from Example 2.1 that one has either in_{<}(I_{A}) = (x_{1}x_{5}^{2}) or in_{<}(I_{A}) = (x_{2}x_{3}x_{4}). When in_{<}(I_{A}) = (x_{1}x_{5}^{2}), its regular triangulation Δ(in_{<}(I_{A})) coincides with the flag nonunimodular triangulation Δ_{1}. When in_{<}(I_{A}) = (x_{2}x_{3}x_{4}), then its regular triangulation Δ(in_{<}(I_{A})) coincides with the unimodular nonflag triangulation Δ_{2}.

In [19] we discovered an example of a configuration A for which the toric ideal I_{A} possesses no initial ideal generated by squarefree monomials, but the convex polytope P_{A} possesses a (nonregular) unimodular triangulation.

Corollary 2.9 does explain the reason why the existence of an initial ideal generated by squarefree quadratic monomials of a toric ideal is important in algebraic combinatorics on convex polytopes. In commutative algebra, such an existence is useful to show that the toric ring of a configuration is normal and Koszul.

We now discuss initial ideals generated by squarefree quadratic monomials arising in combinatorics. We refer the reader to [22] for the fundamental techniques behind the proof of each of Theorems 2.12, 2.14 and 2.15.

(a) Finite distributive lattices

Let L = {α_{1}, …, α_{n}} be a finite distributive lattice [10, p. 118], where i < j if α_{i} < α_{j} in L, and β_{1}, …, β_{d} the join-irreducible elements [10, p. 119] of L. In the literature on combinatorics, the unique minimal element of L may not be regarded as a join-irreducible element of L. However, we will regard the unique minimal element of L as a join-irreducible element of L. We then introduce the configuration A(L) = (a_{ij})_{{1≤i≤d \atop 1≤j≤n}} ∈ ℤ^{d×n} by setting a_{ij} = 1 if β_{i} ≤ α_{j} and a_{ij} = 0 if β_{i} ≰ α_{j}. Since we will regard the unique minimal element of L as a join-irreducible element of L, it turns out that A(L) is, in fact, a configuration.

Example 2.11. Let L be the finite distribute lattice drawn below.

[figure: α_{8}; α_{7}; α_{6}; α_{5}; α_{4}; α_{3}; α_{2}; α_{1}]

Figure 2.1. A finite distributive lattice

Its join-irreducible elements are α_{1}, α_{2}, α_{3}, α_{5} and α_{6}. The configuration A_{L} is

[ \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \end{matrix} ] .

Let S = K[x_{1}, …, x_{n}] and I_{A(L)} ⊂ S the toric ideal of A(L). For each pair (α_{i}, α_{j}) with i < j such that α_{i} and α_{j} are incomparable in L, we introduce the binomial f_{i,j} = x_{i}x_{j} − x_{k}x_{ℓ}, where α_{k} = α_{i} ∧ α_{j} and α_{ℓ} = α_{i} ∨ α_{j}. One has f_{i,j} ∈ I_{A(L)}. Write G for the finite set of those binomials f_{i,j} of I_{A(L)}. Let <_{rev} denote the reverse lexicographic order on S induced by the ordering x_{1} > ⋯ > x_{n} of the variables.

Theorem 2.12 ([11]). Working with the same notation as above, G is a Gröbner basis of I_{A(L)} with respect to <_{rev}.

For example, in the finite distributive lattice of Figure 2.1, the Gröbner basis G consists of the quadratic binomials

x_{2}x_{3} − x_{1}x_{4}, x_{2}x_{5} − x_{1}x_{7}, x_{4}x_{5} − x_{3}x_{7}, x_{5}x_{6} − x_{3}x_{8}, x_{6}x_{7} − x_{4}x_{8}.

(b) Classical root systems

Let Φ ⊂ ℤ^{n} be one of the classical irreducible root systems A_{n−1}, B_{n}, C_{n} and D_{n} ([12, pp. 64–65]) and write Φ^{(+)} for the matrix whose column vectors are all positive roots of Φ together with the origin of ℝ^{n}. Let Φ̃^{(+)} be the configuration obtained by adding the row vector (1, 1, , …, 1) to Φ^{(+)}. For example,

Ã_{2}^{(+)} = [ \begin{matrix}0 & 1 & 1 & 0 \\ 0 & −1 & 0 & 1 \\ 0 & 0 & −1 & −1 \\ 1 & 1 & 1 & 1 \end{matrix} ] , D̃_{3}^{(+)} = [ \begin{matrix}0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & −1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & −1 & −1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} ] ,

B̃_{3}^{(+)} = [ \begin{matrix}0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & −1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & −1 & −1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} ] ,

C̃_{3}^{(+)} = [ \begin{matrix}0 & 2 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 2 & 0 & 1 & 0 & 1 & −1 & 0 & 1 \\ 0 & 0 & 0 & 2 & 0 & 1 & 1 & 0 & −1 & −1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix} ] .

Theorem 2.13 ([7]). The toric ideal of the configurations Ã_{n−1}^{(+)} possesses an initial ideal generated by squarefree quadratic monomials.

Theorem 2.14 ([21]). The toric ideal of each of the configurations B̃_{n}^{(+)}, C̃_{n}^{(+)} and D̃_{n}^{(+)} possesses an initial ideal generated by squarefree quadratic monomials.

(c) Finite bipartite graphs

Let G be a finite graph on the vertex set [d] = {1, …, d} and e_{1}, …, e_{n} its edges. The incidence matrix of G is the configuration A_{G} = \{a_{ij}\}_{{1≤i≤d \atop 1≤j≤n}}, where a_{ij} = 1 if i ∈ e_{j} and a_{ij} = 0 if i ∉ e_{j}. For example, if G is the finite graph on [6] with edges e_{1} = {1, 2}, e_{2} = {2, 3}, e_{3} = {1, 3}, e_{4} = {3, 4}, e_{5} = {4, 5}, e_{6} = {5, 6} and e_{7} = {4, 6}, then the configuration A_{G} is

[ \begin{matrix}1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \end{matrix} ] .

Theorem 2.15 ([20]). Let G be a finite bipartite graph and I_{A_{G}} the toric ideal of the configuration A_{G} arising from G. Then the following conditions are equivalent:

(i) I_{A_{G}} is generated by quadratic binomials; (ii) I_{A_{G}} possesses an initial ideal generated by squarefree quadratic monomials; (iii) Every cycle of G of length > 4 has a chord.

Finally, we refer the reader to, e.g., [2] for initial ideals generated by squarefree quadratic monomials arising in algebraic statistics.

3. Generic initial ideals and algebraic shifting

Let S = K[x_{1}, …, x_{n}] denote the polynomial ring in n variables over an infinite field K with deg x_{i} = 1 for i = 1, 2, …, n. Write GL_{n}(K) for the group of all invertible n × n matrices with entries in K. For each φ = (a_{ij})_{{1≤i≤n \atop 1≤j≤n}} ∈ GL_{n}(K) and for each f = f(x_{1}, …, x_{n}) ∈ S, one defines

φ(f) = f (∑_{i=1}^{n} a_{i1}x_{i}, …, ∑_{i=1}^{n} a_{in}x_{i}) .

If I is a homogeneous ideal of S, i.e., an ideal of S generated by homogeneous polynomials, and if φ = (a_{ij})_{{1≤i≤n \atop 1≤j≤n}} ∈ GL_{n}(K), then φ(I) = \{φ(f) : f ∈ I\} is again a homogeneous ideal of S.

Theorem 3.1 (Galligo, Bayer–Stillman). Work with the reverse lexicographic order <_{rev} on S induced by x_{1} > ⋯ > x_{n}. Let I be a homogeneous ideal of S. If φ, φ′ ∈ GL_{n}(K) are “generic,” then in_{<_{rev}}(φ(I)) = in_{<_{rev}}(φ′(I)).

To understand the precise definition that φ, φ′ ∈ GL_{n}(K) are “generic,” the language of algebraic geometry will be required. What Theorem 3.1 guarantees is that, whenever we choose the entries of φ and φ′ “randomly,” one has in_{<_{rev}}(φ(I)) = in_{<_{rev}}(φ′(I)). We write

Gin(I) = in_{<_{rev}}(φ(I)),

where φ ∈ GL_{n}(K) is generic, and call Gin(I) the generic initial ideal of I. We refer the reader who is familiar with commutative algebra and algebraic geometry to [8] for the foundations of generic initial ideals.

Example 3.2. Let n = 2 and write x and y instead of x_{1} and x_{2} respectively. Let I = (x^{2}, y^{2}) ⊂ K[x, y] and

φ = [ \begin{matrix}a & b \\ c & d \end{matrix} ] .

Thus φ(I) = ((ax + by)^{2}, (cx + dy)^{2}. Suppose that ad − bc ≠ 0 and ac ≠ 0. We compute in_{<_{rev}}(φ(I)). Let f = (ax + by)^{2} and g = (cx + dy)^{2}).

• Since a ≠ 0, one has in_{<_{rev}}(f) = x^{2} ∈ in_{<_{rev}}(φ(I)). Since c^{2}f − a^{2}g ∈ I and ad − bc ≠ 0, it follows that h_{0} = 2acxy + (ad + bc)y^{2} ∈ I. Since ac ≠ 0, one has in_{<_{rev}}(h_{0}) = xy ∈ in_{<_{rev}}(φ(I)).

• One has y^{2} ∉ in_{<_{rev}}(φ(I)). In fact, if y^{2} ∈ in_{<_{rev}}(φ(I)), then y^{2} ∈ I. Thus Cy^{2} = Af + Bg, where A, B, C ∈ K with C ≠ 0. Hence a^{2}A + c^{2}B = 0 and abA + cdB = 0. However, since ad − bc ≠ 0 and ac ≠ 0, one has A = B = 0.

• Let h_{1} = 2cyf − axh_{0} = a(3bc − ad)xy^{2} + 2b^{2}cy^{3} ∈ I. Since

2ch_{1} − (3bc − ad)yh_{0} = (ad − bc)^{2}y^{3} ∈ I

and ad − bc ≠ 0, one has y^{3} ∈ I. Thus y^{3} ∈ in_{<_{rev}}(φ(I)).

• Consequently, since (x^{2}, xy, y^{3}) ⊂ in_{<_{rev}}(φ(I)), it follows that all monomials in K[x, y] except for x, y and y^{2} must belong to in_{<_{rev}}(φ(I)). Since deg f = deg g = 2, it is clear that none of x and y belongs to in_{<_{rev}}(φ(I)). Finally, since y^{2} ∉ in_{<_{rev}}(φ(I)), it follows that in_{<_{rev}}(φ(I)) = (x^{2}, xy, y^{3}).

If we choose the entries a, b, c and d of φ “randomly,” then we could expect ad−bc ≠ 0 and ac ≠ 0. Hence if φ is “generic,” then one has in_{<_{rev}}(φ(I)) = (x^{2}, xy, y^{3}). Thus the generic initial ideal of I = (x^{2}, y^{2}) is Gin(I) = (x^{2}, xy, y^{3}).

Let M_{n} denote the set of monomials in the variables x_{1}, …, x_{n}, and M_{n}^{(sq)} the subset of M_{n} consisting of all squarefree monomials belonging to M_{n}. Let M = ⋃_{n=1}^{∞} M_{n} and M^{(sq)} = ⋃_{n=1}^{∞} M_{n}^{(sq)}. Given a monomial

u = x_{i_{1}}x_{i_{2}} ⋯ x_{i_{j}} ⋯ x_{i_{r}}

of M, where

1 ≤ i_{1} ≤ i_{2} ≤ ⋯ ≤ i_{j} ≤ ⋯ ≤ i_{r},

we introduce the squarefree monomial u^{σ} ∈ M^{(sq)} by setting

u^{σ} = x_{i_{1}}x_{i_{2}+1} ⋯ x_{i_{j}+(j−1)} ⋯ x_{i_{r}+(r−1)}.

For example,

(x_{1}^{3}x_{2}x_{3}^{2}x_{5})^{σ} = (x_{1}x_{1}x_{1}x_{2}x_{3}x_{3}x_{5})^{σ} = x_{1}x_{2}x_{3}x_{5}x_{7}x_{8}x_{11}.

The operator σ : M → M^{(sq)} is called the squarefree operator on M.

Example 3.3. Let M_{n}(d) denote the set of monomials of degree d belonging to M_{n} and M_{n}^{(sq)}(d) the set of squarefree monomials of degree d belonging to M_{n}^{(sq)}. Since (x_{1}^{d})^{σ} = x_{1}x_{2} ⋯ x_{d} and (x_{n}^{d})^{σ} = x_{n}x_{n+1} ⋯ x_{n+d−1}, it follows that σ induces a bijection between M_{n}(d) and M_{n+d−1}^{(sq)}(d).

We summarize fundamental materials on simplicial complexes from, e.g., [10] and [23]. Let [n] = {1, 2, …, n} be the vertex set and Δ a simplicial complex on [n]. Thus Δ is a collection of subsets of [n] satisfying that (i) {i} ∈ Δ for all i ∈ [n] and (ii) if F ∈ Δ and F′ ⊂ [n] with F′ ⊂ F, then F′ ∈ Δ. Each element F ∈ Δ is called a face of Δ. The dimension of a face F is |F | − 1, where the notation |F | stands for the cardinality of F. The dimension of Δ is dim Δ = d − 1, where d = max{|F | : F ∈ Δ}. A facet of Δ is a maximal face of Δ (with respect to inclusion). We say that Δ is pure if all facets of Δ have the same cardinality.

For each i = 0, 1, …, d − 1, we write f_{i} = f_{i}(Δ) for the number of faces of Δ of dimension i. The sequence f(Δ) = (f_{0}, f_{1}, …, f_{d−1}) is called the f-vector of Δ. The h-vector h(Δ) = (h_{0}, h_{1}, …, h_{d}) is defined by the formula

∑_{i=0}^{d} f_{i−1}(x − 1)^{d−i} = ∑_{i=0}^{d} h_{i}x^{d−i}

with f_{−1} = 1. In particular h_{0} = 1, h_{1} = n − d and h_{0} + h_{1} + ⋯ + h_{d} = f_{d−1}.

In order to visualize a simplicial complex Δ we often identify Δ with its geometric realization |Δ|. For example, Figure 3.1 illustrates the simplicial complex Δ on [5] of dimension 2 whose facets are {1, 2, 4}, {1, 2, 5}, {2, 3} and {3, 4}. Its f-vector is f(Δ) = (5, 7, 2) and its h-vector is h(Δ) = (1, 2, 0, −1).

[figure: 5; 1; 2; 4; 3]

Figure 3.1. A geometric realization of Δ

We associate each subset F ⊂ [n] with the squarefree monomial x_{F} = ∏_{i∈F} x_{i} of S. A squarefree ideal of S is an ideal of S which is generated by squarefree monomials. Given a simplicial complex Δ on [n], we define its Stanley–Reisner ideal to be the squarefree ideal

I_{Δ} = ({x_{F} : F ⊂ [n], F ∉ Δ})

of S. Conversely, it follows easily that, given a squarefree ideal I of S with x_{i} ∉ I for each 1 ≤ i ≤ n, there exists a unique simplicial complex Δ on [n] with I = I_{Δ}.

Example 3.4. Let Δ be the simplicial complex of Figure 3.1. Its Stanley–Reisner ideal is I_{Δ} = (x_{1}x_{3}, x_{3}x_{5}, x_{4}x_{5}, x_{2}x_{3}x_{4}).

Algebraic shifting, introduced by Gil Kalai in 1984, turns out to be one of the powerful techniques in algebraic combinatorics on convex polytopes. In [14] the symmetric algebraic shifted complex is defined in a combinatorial way. However, our definition given here is algebraic and will require the generic initial ideal.

Let Δ be a simplicial complex on [n] and I_{Δ} ⊂ S = K[x_{1}, …, x_{n}] its Stanley– Reisner ideal. Let Gin(I_{Δ}) denote the generic initial ideal of I_{Δ} and {u_{1}, …, u_{q}} the (unique) minimal system of monomial generators of Gin(I_{Δ}).

Lemma 3.5 ([9]). Each squarefree monomial u_{i}^{σ} belongs to S. In other words, (u_{1}^{σ}, …, u_{q}^{σ}) is a squarefree ideal of S.

Definition 3.6 ([9]). The symmetric algebraic shifted complex of Δ is the simplicial complex Δ^{s} on [n] with I_{Δ^{s}} = (u_{1}^{σ}, …, u_{q}^{σ}).

The operator Δ → Δ^{s} is called symmetric algebraic shifting. In [14] exterior algebraic shifting as well as symmetric algebraic shifting is introduced.

A simplicial complex Δ on [n] is called shifted if F ∈ Δ, j ∈ F and i > j imply (F \ {j}) ∪ {i} ∈ Δ. The shifted complexes played an important role in classical combinatorics on finite sets.

Lemma 3.7 ([9] and [14]). Let Δ and Δ′ be simplicial complexes.

• Δ^{s} is shifted;

• f(Δ^{s}) = f(Δ); • If Δ is shifted, then Δ^{s} = Δ;

• If Δ ⊂ Δ′, then Δ^{s} ⊂ (Δ′)^{s}.

Let P ⊂ ℝ^{N} be a simplicial polytope [10, p. 9] of dimension d with n vertices and Δ(P) its boundary complex [10, p. 10]. It follows that Δ(P) is a simplicial complex on [n] of dimension d − 1 whose geometric realization is homeomorphic to the (d − 1)-sphere 𝕊^{d−1}.

A simplicial (d − 1)-sphere is a simplicial complex of dimension d − 1 whose geometric realization is homeomorphic to the (d − 1)-sphere 𝕊^{d−1}. Every boundary complex of a simplicial polytope of dimension d is a simplicial (d − 1)-sphere. The h-vector h(Δ) = (h_{0}, h_{1}, …, h_{d}) of a simplicial (d − 1)-sphere is nonnegative ([10, pp. 44–45]) and symmetric ([10, p. 24]), i.e., each h_{i} ≥ 0 and h_{i} = h_{d−i} for 0 ≤ i ≤ d.

One of the outstanding conjectures in algebraic and enumerative combinatorics is the “g-conjecture,” which gives a complete characterization of the h-vectors of simplicial spheres. We recall what the g-conjecture is.

Let M denote the set of monomials in the variables x_{1}, x_{2}, … with deg x_{i} = 1 for i = 1, 2, . . .. A finite subset B of M is called an order ideal of monomials if whenever u and v are monomials with u ∈ B and if v divides u, then v ∈ B. A finite sequence (h_{0}, h_{1}, …, h_{s}) of integers is called an M-vector if there exists an order ideal of monomials B such that |{u ∈ B : deg u = i}| = h_{i} for 0 ≤ i ≤ s.

Theorem 3.8 (Billera–Lee, Stanley). Given a finite sequence (h_{0}, h_{1}, …, h_{d}) of positive integers, there exists a simplicial polytope P of dimension d with h(Δ(P) = (h_{0}, h_{1}, …, h_{d}) if and only if the following conditions are satisfied:

(i) h_{0} = 1; (ii) h_{i} = h_{d−i} for 0 ≤ i ≤ d; (iii) (h_{0}, h_{1} − h_{0}, h_{2} − h_{1}, …, h_{[d/2]} − h_{[d/2]−1}) is an M-vector.

In particular, the h-vector h(Δ(P) = (h_{0}, h_{1}, …, h_{d}) of the boundary complex of a simplicial polytope of dimension d satisfies

h_{0} ≤ h_{1} ≤ ⋯ ≤ h_{[d/2]}.

Conjecture 3.9 (g-conjecture). Let Δ be a simplicial (d−1)-sphere with h(Δ) = (h_{0}, h_{1}, …, h_{d}). Then (h_{0}, h_{1} − h_{0}, h_{2} − h_{1}, …, h_{[d/2]} − h_{[d/2]−1}) is an M-vector.

Let n > d. We write C(n, d) for the convex hull of n points a(t_{1}), …, a(t_{n}), where t_{1} < ⋯ < t_{n}, in the moment curve {a(t) = (t, t^{2}, …, t^{d}) ∈ ℝ^{d} : t ∈ ℝ}. It is known ([10, p. 26]) that C(n, d) is a simplicial polytope of dimension d with {a(t_{1}), …, a(t_{n})} its vertex set. We say that C(n, d) is the cyclic polytope of type (n, d). The combinatorial type [10, p. 27] of the boundary complex Δ(C(n, d)) is independent of the particular choice of real numbers t_{1} < ⋯ < t_{n}. Thus in particular the f-vector (and h-vector) of Δ(C(n, d)) is independent of the particular choice of real numbers t_{1} < ⋯ < t_{n}.

Kalai computed the symmetric algebraic shifted complex of Δ(C(n, d)). The following conjecture due to Kalai and Sarkaria is called the “Shifting Theoretic Upper Bound Conjecture.”

Conjecture 3.10. Every simplicial (d − 1)-sphere Δ on [n] satisfies

Δ^{s} ⊂ Δ(C(n, d))^{s}.

Conjecture 3.10 is much stronger than Conjecture 3.9. In fact, the conclusion in the above conjecture implies the conclusion in Conjecture 3.9.

Lemma 3.11 (Kalai). Let Δ be a simplicial (d−1)-sphere with h(Δ) = (h_{0}, h_{1}, …, h_{d}). Suppose that Δ^{s} ⊂ Δ(C(n, d))^{s}. Then (h_{0}, h_{1} − h_{0}, h_{2} − h_{1}, …, h_{[d/2]} − h_{[d/2]−1}) is an M-vector.

From a computational viewpoint of commutative algebra, it is strongly desirable to characterize the symmetric shifted complexes of simplicial (d − 1)-spheres.

Let A_{n}^{d} denote the set of simplicial complexes Σ on [n] of dimension d − 1 such that

(i) Σ is pure; (ii) Σ is shifted; (iii) the h-vector of Σ is symmetric; (iv) Σ ⊂ Δ(C(n, d))^{s}.

Conjecture 3.12. (a) Every simplicial (d − 1)-sphere Δ on [n] satisfies Δ^{s} ∈ A_{n}^{d}.

(b) Conversely, for each Σ ∈ A_{n}^{d}, there exists a simplicial (d − 1)-sphere Δ on [n] with Δ^{s} = Σ.

Later, Conjecture 3.12 (b) will be proved in Theorem 3.18 (b).

In 1988 Gil Kalai [14] introduced the squeezed sphere. The original definition given by Kalai is purely combinatorial. We will follow [16] and introduce the squeezed sphere in the language of monomial ideals.

A monomial ideal I of S = K[x_{1}, …, x_{n}] is called strongly stable if, for each monomial u ∈ I and for each i ∈ [n] such that x_{i} divides u, one has x_{j}(u/x_{i}) ∈ I for all i < j.

Example 3.13. Each of the monomial ideals (x_{1}^{3}, x_{1}^{2}x_{2}, x_{1}x_{2}^{2}, x_{2}^{3}) and (x_{1}^{3}, x_{1}^{2}x_{2}, x_{1}x_{2}^{2}) of K[x_{1}, x_{2}] is strongly stable. However, the monomial ideal (x_{1}^{3}, x_{1}x_{2}^{2}, x_{3}^{3}) of K[x_{1}, x_{2}] is not strongly stable.

Fix p ≥ 0. Let T_{p} = K[x_{1}, …, x_{p}] denote the polynomial ring in p variables with deg x_{i} = 1 for i = 1, 2, …, p and 𝔪 = (x_{1}, …, x_{p}). An 𝔪-primary ideal of T_{p} is an ideal I of T_{p} for which 𝔪^{N} ⊂ I for N ≫ 0. Here 𝔪^{N} is the ideal of T_{p} generated by all monomials of T of degree N.

Given a strongly stable 𝔪-primary ideal I of T_{p} with I ⊂ 𝔪^{2}, we construct the squeezed sphere arising from I as follows:

• Let δ = δ(I) denote the largest number i ≥ 1 for which 𝔪^{i} ⊄ I.

• Fix an integer n ≥ p + 2δ. Let d = n − p − 1.

• Let {u_{1}, …, u_{q}} denote the (unique) minimal system of monomial generators of I.

• Since n ≥ p + 2δ, it follows that (u_{i}^{σ})^{σ} belongs to S = K[x_{1}, …, x_{n}] for each 1 ≤ i ≤ q.

• Let (I^{σ})^{σ} denote the squarefree ideal ((u_{1}^{σ})^{σ}, …, (u_{q}^{σ})^{σ}) of S.

• Write B_{d}(I) for the simplicial complex on [n] whose Stanley–Reisner ideal coincides with (I^{σ})^{σ}.

Lemma 3.14 ([13]). The geometric realization of the simplicial complex B_{d}(I) is homeomorphic to the d-ball 𝔹^{d}.

We say that B_{d}(I) is the squeezed ball arising from I. Let S_{d−1}(I) denote the boundary complex of B_{d}(I). It follows that the geometric realization of S_{d−1}(I) is homeomorphic to the (d−1)-sphere 𝕊^{d−1}. We say that S_{d−1}(I) is the squeezed sphere arising from I.

In the above algebraic definition of the squeezed ball, since the maximal ideal I = 𝔪 is excluded, the simplex cannot be a squeezed ball. However, for the sake of convenience, we will regard the simplex as a squeezed ball.

Example 3.15. Let p = 2 and I = 𝔪^{3} = (x_{1}^{3}, x_{1}^{2}x_{2}, x_{1}x_{2}^{2}, x_{2}^{3}). Thus δ = 2. Let n = p + 2δ = 6. Hence d = n − p − 1 = 3. Since ((x_{1}^{3})^{σ})^{σ} = x_{1}x_{3}x_{5}, (x_{1}^{2}x_{2})^{σ})^{σ} = x_{1}x_{3}x_{6}, (x_{1}x_{2}^{2})^{σ})^{σ} = x_{1}x_{4}x_{6} and (x_{2}^{3})^{σ})^{σ} = x_{2}x_{4}x_{6}, one has

(I^{σ})^{σ} = (x_{1}x_{3}x_{5}, x_{1}x_{3}x_{6}, x_{1}x_{4}x_{6}, x_{2}x_{4}x_{6}).

The facets of the squeezed sphere S_{2}(I) arising from I are {1, 2, 3}, {1, 3, 4}, {1, 4, 5}, {1, 5, 6}, {1, 2, 6}, {2, 3, 6}, {3, 4, 6}, {4, 5, 6}. It follows that S_{2}(I) is the unique simplicial 2-sphere, up to isomorphism, on [6] with a vertex of degree 5.

Example 3.16. The boundary complex of an octahedron cannot be a squeezed sphere.

The h-vector of the squeezed sphere arising from I can be computed easily. We write h_{i}, 0 ≤ i ≤ δ, for the number of monomials u of S_{p} of degree i with u ∉ I. Thus in particular h_{0} = 1, h_{1} = p = n − (d + 1) and h_{δ} ≠ 0. It follows that such a sequence (h_{0}, h_{1}, …, h_{δ}) is an M-vector. Lemma 3.17 below then says immediately that every squeezed sphere satisfies the g-conjecture.

Lemma 3.17. (a) The h-vector of the squeezed ball B_{d}(I) is (h_{0}, h_{1}, …, h_{δ}, 0, …, 0). (b) Let δ′ = min{δ, [d − 1/2]}. Then the h-vector of the squeezed sphere S_{d}(I) is

(h_{0}, h_{0} + h_{1}, …, ∑_{i=0}^{δ′−1} h_{i}, ∑_{i=0}^{δ′} h_{i}, …, ∑_{i=0}^{δ′} h_{i}, ∑_{i=0}^{δ′−1} h_{i}, …, h_{0} + h_{1}, h_{0}).

Murai [16] succeeded in giving a complete characterization of the symmetric algebraic shifted complexes of squeezed spheres.

Theorem 3.18 (Murai [16]). (a) Every squeezed (d − 1)-sphere Δ on [n] satisfies Δ^{s} ∈ A_{n}^{d}.

(b) Conversely, for each Σ ∈ A_{n}^{d}, there exists a squeezed (d − 1)-sphere Δ on [n] with Δ^{s} = Σ.

Here is a brief outline of Murai’s proof of Theorem 3.18.

• Each Σ ∈ A_{n}^{d} is strong Lefschetz. Thus in particular Σ ∈ A_{n}^{d} is determined by its faces of dimension ≤ ⌊d/2⌋ − 1.

• Kalai [13] constructed for the (⌊d/2⌋ − 1)-skeleton Σ_{⌊d/2⌋−1} of each Σ ∈ A_{n}^{d} a squeezed sphere S_{Σ} and conjectured that (S_{Σ}^{s})_{⌊d/2⌋−1} = Σ_{⌊d/2⌋−1}.

• The above conjecture by Kalai was proved by Murai [15]. Thus in order to complete a proof of Theorem 3.18 one must show that every squeezed sphere is strong Lefschetz.

• Murai [16] showed that every squeezed sphere is strongly edge decomposable, a notion introduced by Nevo [17], and that a strongly edge decomposable complex is strong Lefschetz. The last result was essentially proved in Babson and Nevo [3] independently.

Finally, the number of combinatorial types of squeezed spheres is much larger than that of boundary complexes of simplicial polytopes (Kalai [13]). However, it seems difficult to find a strongly stable 𝔪-primary ideal I of T_{p} for which the squeezed sphere S_{d−1}(I) cannot be the boundary complex of a simplicial polytope.

References

[1] W. Adams and P. Loustaunau, “An Introduction to Gröbner Bases,” Amer. Math. Soc., Providence, RI, 1994.

[2] S. Aoki, T. Hibi, H. Ohsugi and A. Takemura, Gröbner bases of nested configurations,

arχiv:math.AC/0801.0929.

[3] E. Babson and E. Nevo, Lefschetz properties and basic constructions on simplicial spheres,

arχiv:0802.1058.

[4] T. Becker and V. Weispfenning, “Gröbner Bases,” Springer–Verlag, Berlin, Heidelberg, New York, 1993.

[5] D. Cox, J. Little and D. O’Shea, “Ideals, Varieties and Algorithms,” Springer–Verlag, Berlin, Heidelberg, New York, 1992.

[6] A. Dobra, Markov bases for decomposable graphical models, Bernoulli 9 (2003), 1093–1108.

[7] I. M. Gelfand, M. I. Graev and A. Postnikov, Combinatorics of hypergeometric functions associated with positive roots, in “Arnold–Gelfand Mathematics Seminars, Geometry and Singularity Theory” (V. I. Arnold, I. M. Gelfand, M. Smirnov and V. S. Retakh, Eds.), Birkhäuser, Boston, 1997, pp. 205–221.

[8] M. Green, Generic initial ideals, in “Six Lectures on Commutative Algebra” (J. Elias, J. M. Giral, R. M. Miró–Roig and S. Zarzuela, Eds.) Birkhäuser, Boston, 1998, pp. 119–186.

[9] J. Herzog, Generic initial ideals and graded Betti numbers, in “Computational Commutative Algebra and Combinatorics” (T. Hibi, Ed.), Advanced Studies in Pure Math., Volume 33, 2002, pp. 75–120.

[10] T. Hibi, “Algebraic Combinatorics on Convex Polytopes,” Carslaw Publications, Glebe, N.S.W., Australia, 1992.

[11] T. Hibi, Distributive lattices, affine semigroup rings and algebras with straightening laws, in “Commutative Algebra and Combinatorics” (M. Nagata and H. Matsumura, Eds.), Advanced Studies in Pure Math., Volume 11, 1987, pp. 93–109.

[12] J. E. Humphreys, “Introduction to Lie Algebras and Representation Theory,” Second Printing, Revised, Springer–Verlag, Berlin, Heidelberg, New York, 1972.

[13] G. Kalai, Many triangulated spheres, Discrete Comput. Geom. 3 (1988), 1–14.

[14] G. Kalai, Algebraic shifting, in “Computational Commutative Algebra and Combinatorics” (T. Hibi, Ed.), Advanced Studies in Pure Math., Volume 33, 2002, pp. 121–163.

[15] S. Murai, Generic initial ideals and squeezed spheres, Advances in Math. 214 (2007), 701–729.

[16] S. Murai, Algebraic shifting of strongly edge decomposable spheres, arχiv:0709.4518.

[17] E. Nevo, Higher minors and Van Kampen’s obstruction, Math. Scandi. 101 (2007), 161–176.

[18] H. Ohsugi and T. Hibi, Toric ideals generated by quadratic binomials, J. Algebra 218 (1999), 509–527.

[19] H. Ohsugi and T. Hibi, A normal (0, 1)-polytope none of whose regular triangulations is unimodular Discrete Comput. Geom. 21 (1999), 201–204.

[20] H. Ohsugi and T. Hibi, Koszul bipartite graphs, Adv. in Appl. Math. 22 (1999), 25–28.

[21] H. Ohsugi and T. Hibi, Quadratic initial ideals of root systems, Proc. Amer. Math. Soc. 130 (2002), 1913–1922.

[22] H. Ohsugi and T. Hibi, Quadratic Gröbner bases arising from combinatorics, in “Integer Points in Polyhedra” (M. Beck, et al., Eds.), Contemporary Math., Volume 452, 2008, pp. 123–138.

[23] R. Stanley, “Combinatorics and Commutative Algebra,” Second Edition, Birkhäuser, Boston, 1995.

[24] B. Sturmfels, “Gröbner Bases and Convex Polytopes,” Amer. Math. Soc., Providence, RI, 1995.

Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Osaka University, Toyonaka, Osaka 560-0043, Japan.

  E-mail address: hibi@math.sci.osaka-u.ac.jp