\documentclass[12pt]{amsart} % %------ GENERAL MACROS ----- % % Standard rings and fields, affine and projective space % \def\NZQ{\mathbb} % the font for N,Z,Q,R,C \def\NN{{\NZQ N}} \def\QQ{{\NZQ Q}} \def\ZZ{{\NZQ Z}} \def\RR{{\NZQ R}} \def\CC{{\NZQ C}} \def\AA{{\NZQ A}} \def\PP{{\NZQ P}} \def\BB{{\NZQ B}} \def\SS{{\NZQ S}} % %------------------------------------------------ % Symbols in "Fraktur" % \def\frk{\mathfrak} % font for "Fraktur" \def\aa{{\frk a}} \def\pp{{\frk p}} \def\Pp{{\frk P}} \def\qq{{\frk q}} \def\Qq{{\frk Q}} \def\mm{{\frk m}} \def\Mm{{\frk M}} \def\nn{{\frk n}} \def\Nn{{\frk N}} % %------------------------------------------------ % Small letters in bold % \def\ab{{\mathbf a}} \def\bb{{\mathbf b}} \def\cb{{\mathbf c}} \def\eb{{\mathbf e}} \def\hb{{\mathbf h}} \def\tb{{\mathbf t}} \def\xb{{\mathbf x}} \def\yb{{\mathbf y}} \def\zb{{\mathbf z}} % \def\opn#1#2{\def#1{\operatorname{#2}}} % to make operators %------------------------------------------------ % Numerical invariants of rings, ideals, and modules % \opn\chara{char} \opn\length{\ell} \opn\pd{pd} \opn\rk{rk} \opn\projdim{proj\,dim} \opn\injdim{inj\,dim} \opn\rank{rank} \opn\depth{depth} \opn\grade{grade} \opn\height{height} \opn\embdim{emb\,dim} \opn\codim{codim} \def\OO{{\cal O}} \opn\Tr{Tr} \opn\bigrank{big\,rank} \opn\superheight{superheight}\opn\lcm{lcm} \opn\trdeg{tr\,deg}% \opn\reg{reg} \opn\lreg{lreg} \opn\skel{skel} \opn\com{com} % %------------------------------------------------ % Divisors % \opn\div{div} \opn\Div{Div} \opn\cl{cl} \opn\Cl{Cl} % %------------------------------------------------ % Subsets of the spectrum of a ring % \opn\Spec{Spec} \opn\Supp{Supp} \opn\supp{supp} \opn\Sing{Sing} \opn\Ass{Ass} % %------------------------------------------------ % Standard operations on ideals and modules % \opn\Ann{Ann} \opn\Rad{Rad} \opn\Soc{Soc} % %------------------------------------------------ % Linear algebra and homology, endo- and automorphisms % \opn\Ker{Ker} \opn\Coker{Coker} \opn\Im{Im} \opn\Hom{Hom} \opn\Tor{Tor} \opn\Ext{Ext} \opn\End{End} \opn\Aut{Aut} \opn\id{id} \def\Frob{{\cal F}} \opn\nat{nat} \opn\pff{pf}% \pf exists already \opn\Pf{Pf} \opn\GL{GL} \opn\SL{SL} \opn\mod{mod} \opn\ord{ord} % %------------------------------------------------ % Convexity % \opn\aff{aff} \opn\conv{conv} \opn\relint{relint} \opn\st{st} \opn\lk{lk} \opn\cn{cn} \opn\core{core} \opn\vol{vol} \opn\link{link} \opn\star{star} % %------------------------------------------------ % Graded rings and Rees algebras % \opn\gr{gr} \def\Rees{{\cal R}} % %------------------------------------------------ % Polynomials and power series % \def\poly#1#2#3{#1[#2_1,\dots,#2_{#3}]} \def\pot#1#2{#1[\kern-0.28ex[#2]\kern-0.28ex]} \def\Pot#1#2#3{\pot{#1}{#2_1,\dots,#2_{#3}}} \def\konv#1#2{#1\langle #2\rangle} \def\Konv#1#2#3{\konv{#1}{#2_1,\dots,#2_{#3}}} % %------------------------------------------------ % Direct and inverse limits % \opn\dirlim{\underrightarrow{\lim}} \opn\inivlim{\underleftarrow{\lim}} % % % Names with a meaning % \let\union=\cup \let\sect=\cap \let\dirsum=\oplus \let\tensor=\otimes \let\iso=\cong \let\Union=\bigcup \let\Sect=\bigcap \let\Dirsum=\bigoplus \let\Tensor=\bigotimes % %------------------------------------------------ % \let\to=\rightarrow \let\To=\longrightarrow \def\Implies{\ifmmode\Longrightarrow \else \unskip${}\Longrightarrow{}$\ignorespaces\fi} \def\implies{\ifmmode\Rightarrow \else \unskip${}\Rightarrow{}$\ignorespaces\fi} \def\iff{\ifmmode\Longleftrightarrow \else \unskip${}\Longleftrightarrow{}$\ignorespaces\fi} \let\gets=\leftarrow \let\Gets=\longleftarrow \let\followsfrom=\Leftarrow \let\Followsfrom=\Longleftarrow \let\:=\colon % % % \newtheorem{Theorem}{Theorem}[section] \newtheorem{Lemma}[Theorem]{Lemma} \newtheorem{Corollary}[Theorem]{Corollary} \newtheorem{Proposition}[Theorem]{Proposition} \newtheorem{Remark}[Theorem]{Remark} \newtheorem{Remarks}[Theorem]{Remarks} \newtheorem{Example}[Theorem]{Example} \newtheorem{Examples}[Theorem]{Examples} \newtheorem{Definition}[Theorem]{Definition} \newtheorem{Problem}[Theorem]{Problem} \newtheorem{Exercise}[Theorem]{Exercise} \newtheorem{Conjecture}[Theorem]{Conjecture} \newtheorem{Question}[Theorem]{Question} % % We like the var forms of some greek letters (as taught in German schools) % \let\epsilon\varepsilon \let\phi=\varphi \let\kappa=\varkappa % % We print on A4 paper % \textwidth=15cm \textheight=22cm \topmargin=0.5cm \oddsidemargin=0.5cm \evensidemargin=0.5cm %\pagestyle{plain} % % The pf environment of AMSART needs a little help % %\def\qed{\ifhmode\textqed\fi % \ifmmode\ifinner\quad\qedsymbol\else\dispqed\fi\fi} %\def\textqed{\unskip\nobreak\penalty50 % \hskip2em\hbox{}\nobreak\hfil\qedsymbol % \parfillskip=0pt \finalhyphendemerits=0} %\def\dispqed{\rlap{\qquad\qedsymbol}} %\def\noqed{\def\qed{\relax}} % % ------ END OF GENERAL MACROS ------- % % ------ MACROS FOR THIS ARTICLE ------- % \def\CT{{\tilde{\cal C}}} \def\HT{{\tilde H}} \def\AA{{\cal A}} \def\HH{{\cal H}} \def\KK{{\cal K}} \def\FF{{\cal F}} \def\MM{{\cal M}} \def\LL{{\cal L}} \def\GG{{\cal G}} \def\rr{{\frak r}} \opn\initial{in} \opn\inim{inm} \opn\rev{rev} \opn\Gin{Gin} \opn\Lex{Lex} \opn\Shift{Shift} \opn\shift{shift} \opn\rate{rate} \opn\Mon{Mon} \opn\Mat{Mat} \opn\lex{lex} \opn\rev{rev} \opn\purelex{purelex} \opn\red{red} \opn\max{max} \opn\min{min} \opn\initial{in} \opn\Ker{Ker} \opn\GL{GL} \opn\proj{proj} % % % \begin{document} \title{Gr\"obner basis techniques in algebraic combinatorics} \author{Takayuki Hibi} \thanks{59th S\'eminaire Lotharingien de Combinatoire, XIV Incontro Italiano di Combinatoria Algebrica, Bertinoro, Italy, 23 -- 26 September 2007. } \address{Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Osaka University, Toyonaka, Osaka 560-0043, Japan.} \email{hibi@math.sci.osaka-u.ac.jp} \date{} \begin{abstract} Gr\"obner 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. \end{abstract} \maketitle %First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire %--first part \thispagestyle{myheadings} \font\rms=cmr8 \font\its=cmti8 \font\bfs=cmbx8 \markright{\its S\'eminaire Lotharingien de Combinatoire \bfs 59 \rms (2008), Article~B59a\hfill} \def\thepage{} \section*{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\"obner bases could play fundamental roles. Especially, Gr\"obner 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\"obner 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\"obner 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\"obner bases will be introduced. In %Christian: %a one word, a Gr\"obner 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\"obner bases, %Christian: the the Hilbert basis theorem is an immediate consequence of the fact that every Gr\"obner 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\"obner basis of $I$. Moreover, the Buchberger criterion supplies an algorithm to compute a Gr\"obner basis of an ideal $I$ starting from a system of generators of $I$. %Christian: The toric ideal The theory of toric ideals is one of the fascinating topics lying between commutative algebra and combinatorics (Sturmfels \cite{Sturmfels}). Section~$2$ will be devoted to the basic idea of the study of triangulations of convex polytopes by using initial ideals of toric ideals. %Christian: The unimodular triangulation Unimodular triangulations together with %Christian: the flag triangulation 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 \cite{Hibidistributivelattice}, classical root systems \cite{OhHirootsystem}, finite bipartite graphs \cite{OhHibipartite}, and decomposable models in algebraic statistics \cite{Dobra}. Algebraic shifting, introduced by Gil Kalai in 1988, is a powerful tool for the study %Christian: on of the number of faces of simplicial complexes. Kalai defined algebraic shifting in the %Christian: frame 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 \cite{Kalai} and Herzog \cite{Herzog}) 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 \cite{Kalaisqueezed} 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 \cite{MuraiPhD} we will define the squeezed sphere by using strongly stable monomial ideals. Murai \cite{Murai} 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. %First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire %--restoring the headers and pagenumbering \pagenumbering{arabic} \addtocounter{page}{1} \markboth{\SMALL TAKAYUKI HIBI}{\SMALL GR\"OBNER BASIS TECHNIQUES IN ALGEBRAIC COMBINATORICS} % % \section{Gr\"obner bases} Let $S = K[x_1, \ldots, x_n]$ denote the polynomial ring in $n$ variables over a field $K$ with %Christian: each $\deg x_i = 1$ for $i=1,2,\dots,n$, and let % $\Mon(S)$ the set of monomials of $S$. Thus \[ \Mon(S) = \{ x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n} : a_i \in \ZZ_{+}, i = 1, 2, \ldots, n \}, \] be the set of monomials of $S$, where $\ZZ_{+}$ is the set of nonnegative integers. In particular $1 \in \Mon(S)$. For monomials $\xb^\ab = x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$ and $\xb^\bb = x_1^{b_1} x_2^{b_2} \cdots x_n^{b_n}$ of $S$, we say that $\xb^\bb$ {\em divides} $\xb^\ab$ if %Christian: each $b_i \leq a_i$ for $i=1,2,\dots,n$. We write $\xb^\bb \, | \, \xb^\ab$ if $\xb^\bb$ divides $\xb^\ab$. Let ${\mathcal M}$ be a nonempty subset of $\Mon(S)$. A monomial $\xb^\ab \in {\mathcal M}$ is said to be a {\em minimal element} of ${\mathcal M}$ with respect to divisibility if whenever $\xb^\bb \, | \, \xb^\ab$ with $\xb^\bb \in {\mathcal M}$, then $\xb^\bb = \xb^\ab$. Let ${\mathcal M}^{\min}$ denote the set of minimal elements of ${\mathcal M}$. \begin{Theorem}[\sc Dickson's lemma] \label{Dickson:2.1} Let ${\mathcal M}$ be a nonempty subset of $\Mon(S)$. Then ${\mathcal M}^{\min}$ is a finite set. \end{Theorem} \begin{proof} We prove Dickson's lemma by using induction on $n$, the number of variables of $S = K[x_1, x_2, \ldots, x_n]$. Let $n = 1$. If $d$ is the smallest integer for which $x_1^d \in {\mathcal M}$, then ${\mathcal M}^{\min} = \{ x_1^d \}$. Thus ${\mathcal M}^{\min}$ is a finite set. Let $n \geq 2$ and $B = K[\xb] = K[x_1, x_2, \ldots, x_{n-1}]$. We use the notation $y$ instead of $x_n$. Thus $S = K[x_1, x_2, \ldots, x_{n-1}, y]$. Let ${\mathcal M}$ be a nonempty subset of $\Mon(S)$. Write ${\mathcal N}$ for the subset of $\Mon(B)$ which consists of those monomials $\xb^\ab$, where $\ab \in \ZZ_{+}^{n-1}$, such that $\xb^\ab y^b \in {\mathcal M}$ for some $b \geq 0$. Our %Christian: assumption of induction induction hypothesis says that ${\mathcal N}^{\min}$ is a finite set. Let ${\mathcal N}^{\min} = \{ u_1, u_2, \ldots, u_s % \xb^{\ab_1}, \xb^{\ab_2}, \ldots, \xb^{\ab_s} \}$. By the definition of ${\mathcal N}$, for each $1 \leq i \leq s$, there is $b_i \geq 0$ with $u_i y^{b_i} \in {\mathcal M}$. % $\xb^{\ab_i} y^{b_i} \in {\mathcal M}$. Let $b = \max \{ b_1, b_2, \ldots, b_s \}$. Now, for each $0 \leq \xi < b$, define the subset ${\mathcal N}_\xi$ of ${\mathcal N}$ to be \[ {\mathcal N}_\xi = \{ \xb^{\ab} \in {\mathcal N}\, \: \xb^{\ab}y^{\xi} \in {\mathcal M} \}. \] Again, our %Christian: assumption of induction induction hypothesis says that, for each $0 \leq \xi < b$, the set ${{\mathcal N}_\xi}^{\min}$ is finite. Let ${{\mathcal N}_\xi}^{\min} = \{ u_1^{(\xi)}, u_2^{(\xi)}, \ldots, u_{s_\xi}^{(\xi)} \}$. We now show that each monomial belonging to ${\mathcal M}$ is divisible by one of the monomials which appear in the following list: \begin{gather*} u_1y^{b_1}, u_2y^{b_2}, \ldots, u_sy^{b_s}, \\ u_1^{(0)}, u_2^{(0)}, \ldots, u_{s_0}^{(0)}, \\ u_1^{(1)}y, u_2^{(1)}y, \ldots, u_{s_1}^{(1)}y, \\ \cdots \cdots \\ u_1^{(b-1)}y^{b-1}, u_2^{(b-1)}y^{b-1}, \ldots, u_{s_{b-1}}^{(b-1)}y^{b-1}. \end{gather*} \noindent In fact, since, for each monomial $w = \xb^\ab y^\gamma \in {\mathcal M}$ with $\xb^\ab \in \Mon(B)$, one has $\xb^\ab \in {\mathcal N}$, it follows that if $\gamma \geq b$, then $w$ is divisible by one of the monomials $u_1y^{b_1}, u_2y^{b_2}, \ldots, u_sy^{b_s}$, and that if $0 \leq \gamma < b$, then $w$ is divisible by one of the monomials $u_1^{(\gamma)}y^\gamma, u_2^{(\gamma)}y^\gamma, \ldots, u_{s_{\gamma}}^{(\gamma)}y^\gamma$. % Clearly, the monomials listed above are in ${\mathcal M}$. % Hence ${\mathcal M}^{\min}$ is a subset of the set of monomials listed above. Thus ${\mathcal M}^{\min}$ is finite, as desired. \end{proof} A {\em monomial order} on $S$ is a total order $<$ on $\Mon(S)$ such that \begin{itemize} \item $1 < u$ for all $1 \neq u \in \Mon(S)$; \item if $u, v \in \Mon(S)$ and $u < v$, then $uw < vw$ for all $w \in \Mon(S)$. \end{itemize} \begin{Example} \label{lexrev:2.1} {\em (a) Let $\ab = (a_1, a_2, \ldots, a_n)$ and $\bb = (b_1, b_2, \ldots, b_n)$ be vectors belonging to $\ZZ_{+}^n$. We define the total order $<_{\lex}$ on $\Mon(S)$ by setting $\xb^\ab <_{\lex} \xb^\bb$ if either (i) $\sum_{i=1}^{n} a_i < \sum_{i=1}^{n} b_i$, or (ii) $\sum_{i=1}^{n} a_i = \sum_{i=1}^{n} b_i$ and the left-most nonzero component of the vector $\ab - \bb$ is negative. It follows that $<_{\lex}$ is a monomial order on $S$, which is called the {\em lexicographic order} on $S$ induced by the ordering $x_1 > x_2 > \cdots > x_n$. % \smallskip (b) Let $\ab = (a_1, a_2, \ldots, a_n)$ and $\bb = (b_1, b_2, \ldots, b_n)$ be vectors belonging to $\ZZ_{+}^n$. We define the total order $<_{\rev}$ on $\Mon(S)$ by setting $\xb^\ab <_{\rev} \xb^\bb$ if either (i) $\sum_{i=1}^{n} a_i < \sum_{i=1}^{n} b_i$, or (ii) $\sum_{i=1}^{n} a_i = \sum_{i=1}^{n} b_i$ and the right-most nonzero component of the vector $\ab - \bb$ is positive. It follows that $<_{\rev}$ is a monomial order on $S$, which is called the {\em reverse lexicographic order} on $S$ induced by the ordering $x_1 > x_2 > \cdots > x_n$. } \end{Example} % For example, $x_2x_3 <_{\lex} x_1x_4$ and $x_1x_4 <_{\rev} x_2x_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_2x_3 <_{\lex} x_2^2 <_{\lex} x_1x_3 <_{\lex} x_1x_2 <_{\lex} x_1^2 \] and \[ x_3^2 <_{\rev} x_2x_3 <_{\rev} x_1x_3 <_{\rev} x_2^2 <_{\rev} x_1x_2 <_{\rev} x_1^2. \] % \begin{Exercise} \label{exercise} {\em List the $10$ monomials of degree $3$ of $K[x_1, x_2, x_3]$ with respect to each of $<_{\lex}$ and $<_{\rev}$. } \end{Exercise} \begin{Lemma} \label{udividesv} Let $<$ be a monomial order on $S$. Let $u, v \in \Mon(S)$ with $u \neq v$ and suppose that $u$ divides $v$. Then $u < v$. \end{Lemma} \begin{proof} Write $v = uw$ with $w \in \Mon(S)$. Since $w \neq 1$, one has $1 < w$. Thus $1 \cdot u < w \cdot u$. Hence $u < v$, as desired. \end{proof} We will work with a fixed monomial order $<$ on $S$. % We introduce the concepts of initial ideals % and Gr\"obner bases of ideals of $A$ % with respect to $<$. Let $f = \sum_{u \in \Mon(S)} a_u u$ be a nonzero polynomial of $S$ with each $a_u \in K$. The {\em support} of $f$ is the finite set \[ \supp(f) = \{ u \in \Mon(S) : a_u \neq 0 \}. \] The {\em 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 \begin{itemize} \item if $f, g \in I$, then $f \pm g \in I$; \item if $f \in I$ and $h \in S$, then $fh \in I$. \end{itemize} Given a subset $\{ f_\lambda \}_{\lambda \in \Lambda}$ of $S$, we write $(\{ f_\lambda \}_{\lambda \in \Lambda})$ for the set of polynomials of the form $\sum_{\lambda \in \Lambda} h_\lambda f_\lambda$, where $\{ \lambda \in \Lambda : h_\lambda \neq 0 \}$ is finite. Then $(\{ f_\lambda \}_{\lambda \in \Lambda})$ is an ideal of $S$, which is called the ideal of $S$ {\em generated by} $\{ f_\lambda \}_{\lambda \in \Lambda}$. When $\Lambda$ is finite, say, $\Lambda = \{1, 2, \ldots, s \}$, we write $(f_1, f_2, \ldots, f_s)$ instead of $(\{ f_1, f_2, \ldots, f_s \})$. Conversely, given an ideal $I$ of $S$, there exists a subset $(\{ f_\lambda \}_{\lambda \in \Lambda})$ of $S$ with $I = (\{ f_\lambda \}_{\lambda \in \Lambda})$. We call $\{ f_\lambda \}_{\lambda \in \Lambda}$ {\em a system of generators} of $I$. We say that an ideal $I$ of $S$ is {\em 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~\ref{Hilbert:2.1}). A {\em monomial ideal} is an ideal which is generated by a set of monomials. Let $I \subset S$ be a monomial ideal. It follows that $I$ is generated by a subset ${\mathcal N} \subset \Mon(S)$ if and only if %Christian: I \Sect \Mon(S))^{\min} % \bigcap is reserved for intersections with indices below. $(I \cap \Mon(S))^{\min} \subset {\mathcal N}$. Hence $(I \cap \Mon(S))^{\min}$ is a {\em unique} minimal system of monomial generators of $I$. Dickson's lemma guarantees that $(I \cap \Mon(S))^{\min}$ is finite. Thus in particular every monomial ideal is finitely generated. Let $I$ be a nonzero ideal of $S$. The {\em initial ideal} of $I$ with respect to $<$ is the monomial ideal of $S$ which is generated by $\{ \initial_<(f) \, : \, 0 \neq f \in I \, \}$. We write $\initial_<(I)$ for the initial ideal of $I$. Thus \[ \initial_<(I) = ( \{ \initial_<(f)\, \: 0 \neq f \in I \, \} ). \] Since $(\initial_<(I) \cap \Mon(S))^{\min}$ is a minimal system of monomial generators of $\initial_<(I)$, and since $\initial_<(I) \cap \Mon(S) = (\{ \initial_<(f)\, \: 0 \neq f \in I \, \})$, there %Christian: exist exists a finite number of nonzero polynomials $g_1, g_2, \ldots, g_s$ belonging to $I$ such that % the initial ideal $\initial_<(I)$ % of $I$ with respect to $<$ is generated by the set $\{ \initial_<(g_1), \initial_<(g_2), \ldots, \initial_<(g_s) \}$ of their initial monomials. \begin{Definition} \label{Groebner:2.1} {\em Let $I$ be a nonzero ideal of $S$. A finite set $\{ g_1, g_2, \ldots, g_s \}$ of nonzero polynomials with each $g_i \in I$ is said to be a {\em Gr\"obner basis} of $I$ with respect to $<$ if the initial ideal $\initial_<(I)$ of $I$ is generated by the set $\{ \initial_<(g_1), \initial_<(g_2), \ldots, \initial_<(g_s) \}$ of their initial monomials. } \end{Definition} A Gr\"obner basis of $I$ with respect to $<$ exists. If $\mathcal G$ is a Gr\"obner basis of $I$ with respect to $<$, then every finite set $\mathcal G'$ with $\mathcal G \subset \mathcal G' \subset I$ is also a Gr\"obner basis of $I$ with respect to $<$. If $\mathcal G = \{ g_1, \ldots, g_s \}$ is a Gr\"obner basis of $I$ with respect to $<$ and if $f_1, \ldots, f_s$ are nonzero polynomials belonging to $I$ with each $\initial_<(f_i) = \initial_<(g_i)$, then $\{ f_1, \ldots, f_s \}$ is %Christian: also also a Gr\"obner basis of $I$ with respect to $<$. \begin{Example} \label{example:2.1} {\em Let $S = K[x_1, x_2, \ldots, x_7]$ and $I = (f, g)$, where $f = x_1x_4 - x_2x_3$ and $g = x_4x_7 - x_5x_6$. Let $<_{\lex}$ the lexicographic order on $S$ induced by $x_1 > x_2 > \cdots > x_7$. One has $\initial_{<_{\lex}}(f) = x_1x_4$ and $\initial_{<_{\lex}}(g) = x_4x_7$. % \initial_{<_{\rev}}(f) = x_2x_3$ and % $\initial_{<_{\rev}}(g) = x_5x_6$. We claim that $\{ f, g \}$ is not a Gr\"obner basis of $I$ with respect to $<_{\lex}$. In fact, the polynomial $h = x_7 f - x_1 g = x_1x_5x_6 - x_2x_3x_7$ belongs to $I$, but its initial monomial $\initial_{<_{\lex}}(h) = x_1x_5x_6$ can be divided by neither $\initial_{<_{\lex}}(f)$ nor $\initial_{<_{\lex}}(g)$. Hence $\initial_{<_{\lex}}(h) \not\in (\initial_{<_{\lex}}(f), \initial_{<_{\lex}}(g))$. Thus $\initial_{<_{\lex}}(I) \neq (\initial_{<_{\lex}}(f), \initial_{<_{\lex}}(g))$. In other words, $\{ f, g \}$ is not a Gr\"obner basis of $I$ with respect to $<_{\lex}$. Later, we will show that $\{ f, g, h \}$ is a Gr\"obner basis of $I$ with respect to $<_{\lex}$ (Example~\ref{continue:2.3}). } \end{Example} \begin{Lemma} \label{descending:2.1} Let $<$ be a monomial order on $S = K[x_1, \ldots, x_n]$. Then, for any monomial $u$ of $S$, there is no infinite descending sequence of the form \begin{eqnarray} % \label{sequence:2.1} \cdots < u_2 < u_1 < u_0 = u. \label{sequence:2.1} u = u_0 > u_1 > u_2 > \cdots. \end{eqnarray} \end{Lemma} \begin{proof} Suppose, on the contrary, that one has an infinite descending sequence (\ref{sequence:2.1}) and write ${\mathcal M}$ for the set of monomials $\{ u_0, u_1, u_2, \ldots \}$. It follows from Dickson's lemma that ${\mathcal M}^{\min}$ is a finite set, say ${\mathcal M}^{\min} = \{ u_{i_1}, u_{i_2}, \ldots, u_{i_s} \}$ with $i_1 < i_2 < \cdots < i_s$. Then the monomial $u_{i_s+1}$ is divided by $u_{i_j}$ for some $1 \leq j \leq s$. Thus by Lemma~\ref{udividesv} one has $u_{i_j} < u_{i_s+1}$, which contradicts $i_j < i_s + 1$. \end{proof} \begin{Theorem} \label{generator:2.1} Let $I$ be a nonzero ideal of % the polynomial ring $S = K[x_1, \ldots, x_n]$ % over a field $K$ and ${\mathcal G} = \{ g_1, \ldots, g_s \}$ a Gr\"obner basis of $I$ with respect to a monomial order $<$ on $S$. Then $I = (g_1, \ldots, g_s)$. In other words, every Gr\"obner basis of $I$ is a system of generators of $I$. \end{Theorem} \begin{proof} (Gordan) Let $0 \neq f \in I$. Since $\initial_{<}(f) \in \initial_{<}(I)$ and since ${\mathcal G}$ is a Gr\"obner basis of $I$, i.e., $\initial_{<}(I) = (\initial_{<}(g_1), \ldots, \initial_{<}(g_s))$, it follows that there is $g_{i_0}$ such that $\initial_<(g_{i_0})$ divides $\initial_<(f)$. Let $\initial_<(f) = w_0 \initial_<(g_{i_0})$ with $w_0 \in \Mon(S)$. Let $h_0 = f - c_{i_0}^{-1} c_0 w_0 g_{i_0}$, where $c_0$ is the coefficient of $\initial_<(f)$ in $f$ and where $c_{i_0}$ is the coefficient of $\initial_<(g_{i_0})$ in $g_{i_0}$. Then $h_0 \in I$. Since $\initial_<(w_0 g_{i_0}) = w_0 \initial_<(g_{i_0})$ it follows that $\initial_<(h_0) < \initial_<(f)$. If $h_0 = 0$, then $f \in (g_1, \ldots, g_s)$. Let $h_0 \neq 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 $\initial_<(h_0)$ in $h_0$ and where $c_{i_1}$ is the coefficient of $\initial_<(g_{i_1})$ in $g_{i_1}$. Then $h_1 \in I$ and $\initial_<(h_1) < \initial_<(h_0)$. If $h_1 = 0$, then $f \in (g_1, \ldots, g_s)$. If $h_1 \neq 0$, then we proceed as before. Lemma~\ref{descending:2.1} guarantees that this procedure must terminate. Thus we obtain an expression of the form $f = \sum_{q=0}^{N} c_{i_q}^{-1} c_q w_q g_{i_q}$. In particular, $f$ belongs to $(g_1, g_2, \ldots, g_s)$. Thus $I = (g_1, g_2, \ldots, g_s)$, as desired. \end{proof} \begin{Corollary}[\sc Hilbert basis theorem] \label{Hilbert:2.1} Every ideal of the polynomial ring %Christian: $S=K[x_1, \ldots, x_n]$ is finitely generated. \end{Corollary} It is natural to ask if the converse of Theorem~\ref{generator:2.1} is true or false. That is to say, if $I = (f_1, f_2, \ldots, f_s)$ is an ideal of $S = K[x_1, \ldots, x_n]$, then does there exist a monomial order $<$ on $S$ such that $\{ f_1, f_2, \ldots, f_s \}$ is a Gr\"obner basis of $I$ with respect to $<$ ? \begin{Example}[\cite{OhHiquadratic}] \label{Ohsugi:2.1} {\em Let $S = K[x_1, x_2, \ldots, x_{10}]$ and $I$ the ideal of $S$ generated by \begin{center} $f_1 = x_1x_8 - x_2x_6,$ \, \, \, $f_2 = x_2x_9 - x_3x_7,$ \, \, \, $f_3 = x_3x_{10} - x_4x_8,$ $f_4 = x_4x_6-x_5x_9,$ \, \, \, \, \, $f_5 = x_5x_7 - x_1x_{10}.$ \end{center} We claim that there exists {\em no} monomial order $<$ on $S$ such that $\{ f_1,\dots, f_5 \}$ is a Gr\"obner basis of $I$ with respect to $<$. Suppose, on the contrary, that there exists a monomial order $<$ on $S$ such that ${\mathcal G} = \{ f_1,\dots, f_5 \}$ is a Gr\"obner basis of $I$ with respect to $<$. First, note that each of the five polynomials \begin{center} $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}$ \end{center} 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 \initial_<(I)$, there is $g \in {\mathcal G}$ such that $\initial_<(g)$ divides $x_{1}x_{8}x_{9}$. Such $g \in {\mathcal G}$ must be $f_1$. Hence $x_1x_8 > x_2x_6$. Thus $x_2x_6 \not\in \initial_<(I)$. Hence there exists no $g \in {\mathcal G}$ such that $\initial_<(g)$ divides $x_2x_6x_{10}$. Hence $x_{2}x_{6}x_{10} < x_{5}x_{7}x_{8}$. Thus $x_5x_7 > x_1x_{10}$. Continuing these arguments, %Christian: "Continuing ... yields", this is grammatically wrong. % One could say "A continuation of these arguments yields". %yields we obtain \begin{center} $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}$ \end{center} and \begin{center} $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}$. \end{center} Hence \begin{eqnarray} \label{inequality} (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}). \end{eqnarray} The opposite relation in $(\ref{inequality})$ occurs in case of $x_{1}x_{8}x_{9} < x_{3}x_{6}x_{7}$. However, both sides of the inequality $(\ref{inequality})$ coincide with $x_{1}x_{2} \cdots x_{10}$. } \end{Example} In high school mathematics, we learn that, given polynomials $f$ and $g \neq 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. \begin{Theorem}[\sc Division algorithm] \label{division:2.2} Let $S = K[x_1, \ldots, 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, \ldots, g_s$ be nonzero polynomials of $S$. Then, given a polynomial $0 \neq f \in S$, there exist polynomials $f_1, f_2, \ldots, f_s$ and $f'$ of $S$ with \begin{eqnarray} \label{standardexpression:2.2} f = f_1g_1 + f_2g_2 + \cdots + f_sg_s + f' \end{eqnarray} such that the following conditions are satisfied: \begin{enumerate} \item[{(i)}] if $f' \neq 0$ and if $u\in\supp(f')$, then none of %the initial monomials % $\initial_<(g_i)$, $1\leq i \leq s$, $\initial_<(g_1), % \initial_<(g_2), \ldots, \initial_<(g_s)$ divides $u$, i.e., no $u \in \supp(f')$ belongs to $(\initial_<(g_1), \ldots, \initial_<(g_s))$; \item[{(ii)}] if $f_i \neq 0$, then \[ \initial_<(f_ig_i) \leq \initial_<(f). \] \end{enumerate} \end{Theorem} The right hand side of equation (\ref{standardexpression:2.2}) is said to be a {\em standard expression} for $f$ with respect to $g_1, g_2, \ldots, g_s$, and the polynomial $f'$ is called a {\em remainder} of $f$ with respect to $g_1, g_2, \ldots, g_s$. Instead of giving a detailed proof of Theorem~\ref{division:2.2}, we discuss a typical example % (\cite[pp.~000]{CLO}) which clearly explains the procedure to obtain a standard expression. \begin{Example} \label{remainder:2.2} {\em 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^2y - x^2 - 1$. Each of \begin{align*} f & = x^3 - x^2y - x^2 - 1 = x(g_1 + z) - x^2y - x^2 - 1 \\ & = xg_1 - x^2y - 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) \end{align*} and \begin{align*} f & = x^3 - x^2y - x^2 - 1 = x(g_1 + z) - x^2y - x^2 - 1 \\ & = xg_1 - x^2y - 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 - x g_2 + (xz - x - z - 1) \end{align*} 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$. } \end{Example} Example~\ref{remainder:2.2} says that a remainder of a nonzero polynomial may not be unique. However, %Christian: no trailing sentences. we have the following fact. \begin{Lemma} \label{uniqueremainder:2.2} If ${\mathcal G} = \{ g_1, \ldots, g_s \}$ is a Gr\"obner basis of $I = (g_1, \ldots, g_s)$, then for any nonzero polynomial $f$ of $S$, there is a unique remainder of $f$ with respect to $g_1, \ldots, g_s$. \end{Lemma} \begin{proof} Suppose there exist remainders $f'$ and $f''$ with respect to $g_1, \ldots, g_s$ with $f'\neq f''$. Since $0 \neq f' - f'' \in I$, the initial monomial $w = \initial_{<}(f' - f'')$ must belong to $\initial_<(I)$. However, since $w \in \supp(f') \cup \supp(f'')$, none of the monomials $\initial_<(g_1), \ldots, \initial_<(g_s)$ divides $w$. Hence $\initial_<(I) \neq (\initial_<(g_1), \ldots, \initial_<(g_s))$. \end{proof} Given nonzero polynomials $f$ and $g$ of $S$, the notation $\lcm(\initial_<(f), \initial_<(g))$ stands for the least common multiple of $\initial_<(f)$ and $\initial_<(g)$. Let $c_f$ denote the coefficient of $\initial_<(f)$ in $f$ and $c_g$ the coefficient of $\initial_<(g)$ in $g$. The polynomial \[ S(f,g) = \frac{\lcm(\initial_<(f), \initial_<(g))} {c_f \initial_<(f)} f - \frac{\lcm(\initial_<(f), \initial_<(g))} {c_g \initial_<(g)} g \] is called the {\em $S$-polynomial} of $f$ and $g$. We say that {\em $f$ has remainder $0$} with respect to $g_1, g_2, \ldots, g_s$ if, in the division algorithm, there is a standard expression (\ref{standardexpression:2.2}) of $f$ with respect to $g_1, g_2, \ldots, g_s$ with $f' = 0$. \begin{Lemma} \label{relativelyprime:2.3} Let $f$ and $g$ be nonzero polynomials and suppose that $\initial_<(f)$ and $\initial_<(g)$ are relatively prime, i.e., $\lcm(\initial_<(f), \initial_<(g)) = \initial_<(f)\initial_<(g)$. Then $S(f,g)$ has remainder $0$ with respect to $f, g$. \end{Lemma} \begin{proof} To simplify notation we will assume that each of the coefficients of $\initial_<(f)$ in $f$ and $\initial_<(g)$ in $g$ is equal to $1$. Let $f = \initial_<(f) + f_1$ and $g = \initial_<(g) + g_1$. Since $\initial_<(f)$ and $\initial_<(g)$ are relatively prime, it follows that \begin{align*} S(f,g) & = \initial_<(g) f - \initial_<(f) g \\ & = (g - g_1) f - (f - f_1) g \\ & = f_1g - g_1f. \end{align*} We claim $( \initial_<(f_1)\initial_<(g) = ) \initial_<(f_1g) \neq \initial_<(g_1f) \, \, ( = \initial_<(g_1)\initial_<(f) )$. In fact, if $\initial_<(f_1)\initial_<(g) = \initial_<(g_1)\initial_<(f)$, then, since $\initial_<(f)$ and $\initial_<(g)$ are relatively prime, it follows that $\initial_<(f)$ must divide $\initial_<(f_1)$. However, since $\initial_<(f_1) < \initial_<(f)$, this is impossible. Let, say, $\initial_<(f_1)\initial_<(g) < \initial_<(g_1)\initial_<(f)$. Then $\initial_<(S(f,g)) = \initial_<(g_1 f)$ and $S(f,g) = f_1g - g_1f$ 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 $\initial_<(g_1)\initial_<(f) < \initial_<(f_1)\initial_<(g)$. \end{proof} We now come to the most fundamental theorem in the theory of Gr\"obner bases. \begin{Theorem}[\sc Buchberger criterion] \label{BuchbergerCriterion:2.3} Let $I$ be a nonzero ideal of $S$ and ${\mathcal G} = \{ g_1, g_2, \ldots, g_s \}$ a system of generators of $I$. Then ${\mathcal G}$ is a Gr\"obner basis of $I$ if and only if the following condition is satisfied: \begin{enumerate} \item[$(*)$] For all $i \neq j$, $S(g_i, g_j)$ has remainder $0$ with respect to $g_1, \ldots, g_s$. \end{enumerate} \end{Theorem} We refer the reader to a standard textbook on Gr\"obner bases, e.g., \cite{AL}, \cite{BW} and \cite{CLO} for a proof of the Buchberger criterion. However, for a (general) Gr\"obner basis ``user,'' it may not be required to understand a detailed proof of the Buchberger criterion. In Example~\ref{example:2.1}, by using Lemma~\ref{relativelyprime:2.3} together with the Buchberger criterion, it follows immediately that the set $\{f, g\}$ is a Gr\"obner basis of $I = (f, g)$ with respect to the reverse lexicographic order $<_{\rev}$ induced by $x_1 > x_2 > \cdots > x_7$. The Buchberger criterion supplies an algorithm to compute a Gr\"obner basis starting from a system of generators of an ideal. Let $\{ g_1, g_2, \ldots, g_s \}$ be a system of generators of a nonzero ideal $I$ of $S$ and suppose that $\{ g_1, g_2, \ldots, g_s \}$ is {\em not} a Gr\"obner basis of $I$. The Buchberger criterion then guarantees that there is an $S$-polynomial $S(g_i,g_j)$ such that {\em no} remainder of $S(g_i,g_j)$ with respect to $g_1, g_2, \ldots, g_s$ is $0$. Let $h_{ij} \in I$ be a remainder of a standard expression of $S(g_i,g_j)$ with respect to $g_1, g_2, \ldots, g_s$. Then $\initial_<(h_{ij})$ can be divided by none of the monomials $\initial_<(g_1), \initial_<(g_2), \ldots, \initial_<(g_s)$. In other words, the inclusion \[ (\initial_<(g_1), \initial_<(g_2), \ldots, \initial_<(g_s)) \subset (\initial_<(g_1), \initial_<(g_2), \ldots, \initial_<(g_s), \initial_<(h_{ij})). \] is strict. With setting $g_{s+1} = h_{ij}$, suppose that $\{ g_1, g_2, \ldots, g_s, g_{s+1} \}$ is not a Gr\"obner basis of $I$. Again, by using the Buchberger criterion, there is a $S$-polynomial $S(g_k,g_\ell)$ such that no remainder of $S(g_k,g_\ell)$ with respect to $g_1, g_2, \ldots, g_s, g_{s+1}$ is $0$. Let $h_{k\ell} \in I$ be a remainder of $S(g_k,g_\ell)$ with respect to $g_1, g_2, \ldots, g_s, g_{s+1}$. Then the inclusion \begin{multline*} (\initial_<(g_1), \initial_<(g_2), \ldots, \initial_<(g_s), \initial_<(g_{s+1})) \\ \subset (\initial_<(g_1), \initial_<(g_2), \ldots, \initial_<(g_s), \initial_<(g_{s+1}), \initial_<(h_{k\ell})). \end{multline*} % With setting $g_{s+2} = h_{k\ell}$, % apply Buchberger Criterion to % $\{ g_1, \ldots, g_s, g_{s+1}, g_{s+2} \}$. is strict. By virtue of Dickson's lemma, these procedures must terminate after a finite number of steps, and a Gr\"obner basis of $I$ can be obtained. The above algorithm to find a Gr\"obner basis starting from a system of generators of an ideal is said to be the {\em Buchberger algorithm}. \begin{Example} \label{continue:2.3} {\em We continue Example~\ref{example:2.1}. Let $S = K[x_1, x_2, \ldots, x_7]$ and $<_{\lex}$ the lexicographic order on $S$ induced by $x_1 > x_2 > \cdots > x_7$. Let $f = x_1x_4 - x_2x_3$ and $g = x_4x_7 - x_5x_6$. Thus % with their initial monomials $\initial_{<_{\lex}}(f) = x_1x_4$ and $\initial_{<_{\lex}}(g) = x_4x_7$. Let $I = (f, g)$. Then $\{ f, g \}$ is not a Gr\"obner basis of $I$ with respect to $<_{\lex}$. Now, as a remainder of $S(f,g) = x_7 f - x_1 g = x_1x_5x_6 - x_2x_3x_7$ with respect to $f$ and $g$, we choose $S(f,g)$ itself. Let $h = x_1x_5x_6 - x_2x_3x_7$ with $\initial_{<_{\lex}}(h) = x_1x_5x_6$. Then $\initial_{<_{\lex}}(g)$ and $\initial_{<_{\lex}}(h)$ are relatively prime. On the other hand, $S(f,h) = x_2x_3(x_4x_7 - x_5x_6)$ has remainder $0$ with respect to $f, g, h$. It follows from the Buchberger criterion that $\{ f, g, h \}$ is a Gr\"obner basis of $I$ with respect to $<_{\lex}$. } \end{Example} \section{Initial ideals and triangulations of convex polytopes} Let $A = (a_{ij})_{\genfrac{}{}{0pt}{}{1 \leq i \leq d}{ 1 \leq j \leq n}} \in \ZZ^{d \times n}$, i.e., $A$ is a $d \times n$ integer matrix, with ${\bf a}_{1}, \ldots, {\bf a}_{n}$ their column vectors. Such a matrix $A$ is called a {\em configuration} if there exists a vector ${\bf c} \in \RR^d$ such that $\langle {\bf a}_j, {\bf c} \rangle = 1$ for each $1 \leq j \leq n$, where $\langle {\bf a}_j, {\bf c} \rangle$ is the usual inner product in $\RR^d$. Let, as before, $S = K[x_1, \ldots, x_n]$ denote the polynomial ring in $n$ variables over a field $K$ with %Christian: each $\deg x_i = 1$ for $i=1,2,\dots,n$. If ${\bf b} = (b_1, \ldots, b_n) \in \ZZ^n$, then we define the binomial \[ f_{\bf b} = \prod_{b_i >0} x_i^{b_i} - \prod_{b_i < 0} x_i^{-b_i} \] of $S$. For example, if $n = 5$ and ${\bf b} = (-1, 3, 2, 0, -4)$, then $f_{\bf b} = x_2^3 x_3^2 - x_1 x_5^4$. The {\em toric ideal} of a configuration $A \in \ZZ^{d \times n}$ is the ideal $I_A$ of $S$ which is generated by those binomials $f_{\bf b}$ with $A \, {\bf b}^\top = 0$, where ${\bf b} \in \ZZ^n$ and where ${\bf b}^\top$ stands for the transposed matrix of ${\bf b}$. Thus \[ I_A = ( \, \{ \, f_{\bf b} \, : \, {\bf b} \in \ZZ^n, \,\, A \, {\bf b}^\top = 0 \, \} \, ). \] The convex polytope arising from a configuration $A \in \ZZ^{d \times n}$ is the convex polytope ${\mathcal P}_A \subset \RR^d$ which is the convex hull of the column vectors ${\bf a}_{1}, \ldots, {\bf a}_{n}$ of $A$. Fix a monomial order $<$ on $S$ and write, as before, $\initial_<(I_A)$ for the initial ideal of $I_A$ with respect to $<$. \begin{Example} \label{asusual} {\em The $4 \times 5$ matrix \begin{eqnarray*} A = \left[ \begin{array}{ccccc} 0&1&1&0&1\\ 0&1&0&1&1\\ 0&0&1&1&1\\ 1&1&1&1&1\\ \end{array} \right] \end{eqnarray*} is a configuration, since $(0,0,0,1) \, A = (1,1,1,1)$. The toric ideal $I_A$ is generated by the binomial $x_1x_5^2 - x_2x_3x_4$ and the convex polytope ${\mathcal P}_A \subset \RR^4$ is a bipyramid on a triangle. One has either $\initial_<(I_A) = (x_1x_5^2)$ or $\initial_<(I_A) = (x_2x_3x_4)$. } \end{Example} We now discuss the triangulations of the convex polytope ${\mathcal P}_A \subset \RR^d$ arising from a configuration $A \in \ZZ^{d \times n}$. Let ${\bf a}_{1}, \ldots, {\bf a}_{n}$ be the column vectors of $A$. To simplify the situation, % throughout the present section, we may assume that the additive group $\ZZ^d$ is generated by the set $\{ {\bf a}_{1}, \ldots, {\bf a}_{n} \}$ of column vectors. In other words, every vector belonging to $\ZZ^d$ is of the form $c_1 {\bf a}_{1} + \cdots + c_n {\bf a}_{n}$ with each $c_j \in \ZZ$. In particular, since $A$ is a configuration, it follows that the dimension of ${\mathcal P}_A$ is $d - 1$. When $\ZZ^d$ cannot be generated by the set $\{ {\bf a}_{1}, \ldots, {\bf a}_{n} \}$ of column vectors of $A$, write ${\mathcal L}$ for the subgroup of $\ZZ^d$ generated by the set of column vectors of $A$. Thus ${\mathcal L} \simeq \ZZ^e$ with $e < d$. Let $\{ {\bf a}_{i_1}, \ldots, {\bf a}_{i_e} \}$ with $1 \leq i_1 < \cdots < i_e \leq n$ be a $\ZZ$-basis of ${\mathcal L}$. Each vector ${\bf a} \in {\mathcal L}$ has a unique expression of the form ${\bf a} = \sum_{j=1}^{e} q_j {\bf a}_{i_j}$ with each $q_j \in \ZZ$. We then introduce the $\ZZ$-isomorphism $\psi : {\mathcal L} \to \ZZ^e$ by setting $\psi({\bf a}) = (q_1, \ldots, q_e)^\top$. Let $A' = (a'_{ij})_{\genfrac{}{}{0pt}{}{1 \leq i \leq e} {1 \leq j \leq n}}$ denote the $e \times n$ integer matrix with the column vectors $\varphi({\bf a}_{1}), \ldots, \varphi({\bf a}_{n})$. Since $A$ is a configuration, it follows that $\sum_{i=1}^{e} a'_{ij} = 1$ for each $1 \leq j \leq n$. Thus $A' \in \ZZ^{e \times n}$ is a configuration and the set of columns of $A'$ generates $\ZZ^e$. Clearly discussing the toric ideal and the triangulations of $A$ is equivalent to discussing the toric ideal and the triangulations of $A'$. \begin{Example} \label{clear} {\em The $3 \times 5$ matrix \begin{eqnarray*} A = \left[ \begin{array}{ccccc} 0&2&0&1& 1 \\ 0&0&2&1&-1 \\ 1&1&1&1&1 \end{array} \right] \end{eqnarray*} is a configuration. The additive group ${\mathcal L}$ generated by the set $\{ {\bf a}_1, \ldots, {\bf a}_5 \}$ of column vectors of $A$ is $ {\mathcal L} = \{ (a_1, a_2, a_3) \in \ZZ^3 : a_1 + a_2 \in 2 \cdot \ZZ \}, $ where $2 \cdot \ZZ$ is the set of even integers, with $\{ {\bf a}_1, {\bf a}_4, {\bf a}_5 \}$ its $\ZZ$-basis. One has \begin{eqnarray*} A' = \left[ \begin{array}{ccccc} 1&-1&-1&0&0 \\ 0& 1& 1&1&0 \\ 0& 1&-1&0&1 \end{array} \right]. \end{eqnarray*} % and % \[ % I_A = I_{A'} = (x_1x_2 - x_4x_5, x_1x_4 - x_2x_5). % \] } \end{Example} Given a subset $F = \{ {\bf a}_{i_1}, \ldots, {\bf a}_{i_r} \}$ of $\{ {\bf a}_{1}, \ldots, {\bf a}_{n} \}$, the notation $\conv(F)$ stands for the convex hull of ${\bf a}_{i_1}, \ldots, {\bf a}_{i_r}$ in $\RR^d$. A subset $F$ of $\{ {\bf a}_{1}, \ldots, {\bf a}_{n} \}$ is called a {\em simplex belonging to $A$} if $\conv(F)$ is an %Christian: $(q - 1)$-simplex $(r - 1)$-simplex in $\RR^d$, where %Christian: $q = |F|$. $r = |F|$. Every subset of a simplex belonging to $A$ is again a simplex belonging to $A$. A simplex $F = \{ {\bf a}_{i_1}, \ldots, {\bf a}_{i_r} \}$ belonging to $A$ is called {\em unimodular} if $F$ is a subset of a $\ZZ$-basis of $\ZZ^d$. If $F$ is unimodular and if $F' \subset F$, then $F'$ is again unimodular. A {\em triangulation} of ${\mathcal P}_A \subset \RR^d$ is a collection $\Delta$ of simplices belonging to $A$ such that \begin{itemize} \item If $F$ belongs to $\Delta$ and $F' \subset F$, then $F'$ belongs to $\Delta$; \item If $F$ and $G$ belong to $\Delta$, then $\conv(F) \cap \conv(G) = \conv(F \cap G)$; \item ${\mathcal P}_A = \bigcup_{F \in \Delta} \conv(F)$. \end{itemize} Each simplex $F \in \Delta$ is called a {\em face} of $\Delta$. A {\em facet} of $\Delta$ is a face $F$ of $\Delta$ with $|F| = d$. A triangulation $\Delta$ of ${\mathcal P}_A$ is called {\em unimodular} if every $F \in \Delta$ is unimodular. A simplex $F$ belonging to $A$ is called a {\em nonface} of $\Delta$ if $F \not\in \Delta$. A triangulation $\Delta$ of ${\mathcal P}_A$ is called {\em flag} if every minimal nonface of $\Delta$ is a $2$-element subset of $\{ {\bf a}_{1}, \ldots, {\bf a}_{n} \}$. Why is a unimodular triangulation of interest in combinatorics? Let ${\bf c} \in \RR^d$ with $\langle {\bf a}_j, {\bf c} \rangle = 1$ for each $j$ and ${\mathcal H} \subset \RR^d$ the hyperplane $\{ {\bf a} \in \RR^d : \langle {\bf a}, {\bf c} \rangle = 1 \}$. One has ${\mathcal P}_A \subset {\mathcal H}$. Fix an invertible affine transformation $\varrho : {\mathcal H} \to \RR^{d-1}$ with $\varrho(\ZZ^d \cap {\mathcal H}) = \ZZ^{d-1}$. The image $\varrho({\mathcal P}_A)$ of ${\mathcal P}_A$ under $\varrho$ is a convex polytope in $\RR^{d-1}$ of dimension $d - 1$. Hence the volume (Lebesgue measure) $\vol(\varrho({\mathcal P}_A))$ of $\varrho({\mathcal P}_A)$ is positive and is independent of the particular choice of $\varrho$. We call the positive integer $(d - 1)! \vol(\varrho({\mathcal P}_A))$ the {\em normalized volume} of ${\mathcal P}_A$. If $\Delta$ is a triangulation of ${\mathcal P}_A$, then it follows that the number of the facets of $\Delta$ is at most the normalized volume of ${\mathcal P}_A$ and is equal to the normalized volume of ${\mathcal P}_A$ if and only if $\Delta$ is unimodular. %Christian: In consequence, Consequently, the existence of a unimodular triangulation of ${\mathcal P}_A$ makes it easy to compute the normalized volume of ${\mathcal P}_A$. \begin{Remark} {\em A combinatorial way to see the reason why $\vol(\varrho({\mathcal P}_A))$ is independent of the particular choice of $\varrho$ is to show that the {\em Ehrhart polynomial} \cite[p.~80]{HibiRedBook} of ${\mathcal P}_A$ coincides with that of $\varrho({\mathcal P}_A)$. It is well known, e.g., \cite[Theorem~10.3, p.~45]{StanleyGreenBook} and \cite[Proposition (28.5)]{HibiRedBook} that the leading coefficient of the Ehrhart polynomial of $\varrho({\mathcal P}_A)$ is $\vol(\varrho({\mathcal P}_A))$. } \end{Remark} Why is a flag triangulation of interest in combinatorics? Given a triangulation $\Delta$ of ${\mathcal P}_A$, we write $G_\Delta$ for the finite graph on $[n] = \{ 1, \ldots, n \}$ whose edges, $E(G_\Delta)$, are those $\{ i, j \}$, where $i \neq j$, with $\{ {\bf a}_i, {\bf a}_j \} \in \Delta$. We call % the finite graph $G_\Delta$ the {\em skeleton} of $\Delta$, %Christian: and we denote the set of edges by $E(G_\Delta)$, as usual. A {\em clique} of $G_\Delta$ is a subset $C \subset [n]$ such that $\{ i, j \} \in E(G_\Delta)$ for all $i, j \in C$ with $i \neq j$. Let ${\mathcal C}(G_\Delta)$ denote the set of cliques of $G_\Delta$. It then follows that $\Delta \subset \{ \{ {\bf a}_{i} : i \in C \} : C \in {\mathcal C}(G_\Delta) \}$ and that $\Delta = \{ \{ {\bf a}_{i} : i \in C \} : C \in {\mathcal C}(G_\Delta) \}$ if and only if $\Delta$ is flag. %Christian: In consequence, Consequently, when $\Delta$ is flag, we can discuss the combinatorics on $\Delta$ (for example, the number of faces of $\Delta$) in terms of the combinatorics on the skeleton $G_\Delta$ of $\Delta$. \begin{Example} \label{unimodularflag} {\em Let $A$ be the configuration discussed in Example~\ref{asusual}. The simplices belonging to $A$ are \begin{gather*} F_1 = \{ {\bf a}_1, {\bf a}_2, {\bf a}_3, {\bf a}_4 \},\quad F_2 = \{ {\bf a}_2, {\bf a}_3, {\bf a}_4, {\bf a}_5 \}, \\ F_3 = \{ {\bf a}_1, {\bf a}_5, {\bf a}_2, {\bf a}_3 \},\quad F_4 = \{ {\bf a}_1, {\bf a}_5, {\bf a}_2, {\bf a}_4 \},\quad F_5 = \{ {\bf a}_1, {\bf a}_5, {\bf a}_3, {\bf a}_4 \}, \end{gather*} together with their subsets. Since $\{ {\bf a}_1, {\bf a}_2, {\bf a}_3, {\bf a}_4 \}$ cannot be a $\ZZ$-basis of $\ZZ^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 $\Delta_1$ be the triangulation of ${\mathcal P}_A$ with the facets $F_1, F_2$, and let $\Delta_2$ be the triangulation of ${\mathcal P}_A$ with the facets $F_3, F_4, F_5$. Then $\Delta_1$ is flag and $\Delta_2$ is unimodular. Since $F_1 \in \Delta_1$, it follows that $\Delta_1$ is not unimodular. Since $\{ {\bf a}_2, {\bf a}_3, {\bf a}_4 \}$ is a minimal nonface of $\Delta_2$, it follows that $\Delta_2$ is not flag. } \end{Example} Let $A \in \ZZ^{d \times n}$ be a configuration with ${\bf a}_{1}, \ldots, {\bf a}_{n}$ its columns and ${\mathcal P}_A \subset \RR^d$ the convex polytope arising from $A$. Let $I_A \subset S$ be the toric ideal of $A$ and $\initial_{<}(I_A)$ the initial ideal of $I_A$ with respect to a monomial order $<$ on $S$. For a monomial $u = x_1^{a_1} \cdots x_n^{a_n}$, the notation $\sqrt{u}$ stands for the squarefree monomial $\prod_{ \, i \, : \, a_i > 0 \, } x_i$. For example, if $u = x_1x_3^5x_4^2$, then $\sqrt{u} = x_1x_3x_4$. Moreover, when $\initial_{<}(I_A)$ is generated by monomials $u_1, \ldots, u_s$, the notation $\sqrt{\initial_{<}(I_A)}$ stands for the ideal of $S$ which is generated by the squarefree monomials $\sqrt{u_1}, \ldots, \sqrt{u_s}$. Since a monomial ideal possesses a unique minimal system of monomial generators, it follows that $\sqrt{\initial_{<}(I_A)}$ is independent of the particular choice of a system of monomial generators of $I_A$. \begin{Lemma} \label{simplex} Let $F$ be a subset of $\{ {\bf a}_{1}, \ldots, {\bf a}_{n} \}$ and suppose that \begin{eqnarray} \label{equation} \prod_{{\bf a}_{i} \in F} x_i \not\in \sqrt{\initial_{<}(I_A)}. \end{eqnarray} Then $F$ is a simplex belonging to $A$. \end{Lemma} \begin{Theorem}[\sc Sturmfels \cite{Sturmfels}] \label{regular} Write $\Delta(\initial_{<}(I_A))$ for the set of those simplices $F$ of $A$ satisfying $(\ref{equation})$. Then $\Delta(\initial_{<}(I_A))$ is a triangulation of ${\mathcal P}_A$. \end{Theorem} Such a triangulation $\Delta(\initial_{<}(I_A))$ of ${\mathcal P}_A$ is called a {\em regular} triangulation of ${\mathcal P}_A$. A typical example of a {\em nonregular} triangulation appears in, say, \cite{Sturmfels}. Now, it is natural to ask when a regular triangulation $\Delta(\initial_{<}(I_A))$ is unimodular or flag. \begin{Theorem}[\sc \cite{Sturmfels}] \label{regularunimodular} % {\em (a)} A regular triangulation $\Delta(\initial_{<}(I_A))$ of ${\mathcal P}_A$ is unimodular if and only if $\initial_{<}(I_A)$ is generated by squarefree monomials, i.e., $\initial_{<}(I_A) = \sqrt{\initial_{<}(I_A)}$. \end{Theorem} \begin{Lemma} \label{regularflag} A regular triangulation $\Delta(\initial_{<}(I_A))$ of ${\mathcal P}_A$ is flag if and only if\break $\sqrt{\initial_{<}(I_A)}$ is generated by quadratic monomials. \end{Lemma} \begin{Corollary} \label{reguniflag} A regular triangulation $\Delta(\initial_{<}(I_A))$ of ${\mathcal P}_A$ is unimodular and flag if and only if $\initial_{<}(I_A)$ is generated by squarefree quadratic monomials. \end{Corollary} \begin{Example} \label{regulaunimodularflag} {\em Let $\Delta_1$ and $\Delta_2$ be the triangulations of ${\mathcal P}_A$ discussed in Example~\ref{unimodularflag}. Recall from Example~\ref{asusual} that one has either $\initial_<(I_A) = (x_1x_5^2)$ or $\initial_<(I_A) = (x_2x_3x_4)$. When $\initial_<(I_A) = (x_1x_5^2)$, its regular triangulation $\Delta(\initial_<(I_A))$ coincides with the flag nonunimodular triangulation $\Delta_1$. When $\initial_<(I_A) = (x_2x_3x_4)$, then its regular triangulation $\Delta(\initial_<(I_A))$ coincides with the unimodular nonflag triangulation $\Delta_2$. } \end{Example} In \cite{OhHiunimodular} 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 ${\mathcal P}_A$ possesses a (nonregular) unimodular triangulation. Corollary~\ref{reguniflag} 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, %Christian: such such an existence is useful to show that the {\em toric ring} of a configuration is normal and Koszul. % We refer the reader to, % e.g., \cite{} and \cite{} for the background % in commutative algebra. We now discuss initial ideals generated by squarefree quadratic monomials arising in combinatorics. We refer the reader to \cite{Snowbird} for the fundamental techniques behind the proof of each of Theorems~\ref{nice}, \ref{OHHIROOT} and \ref{BIPARTITE}. \bigskip \begin{center} {\bf (a) Finite distributive lattices} \end{center} Let $L = \{ \alpha_1, \ldots, \alpha_n \}$ be a finite distributive lattice \cite[p.~118]{HibiRedBook}, where $i < j$ if $\alpha_i < \alpha_j$ in $L$, and $\beta_1, \ldots, \beta_d$ the join-irreducible elements \cite[p.~119]{HibiRedBook} 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})_{\genfrac{}{}{0pt}{}{1 \leq i \leq d} {1 \leq j \leq n}} \in \ZZ^{d \times n}$ by setting $a_{ij} = 1$ if $\beta_i \leq \alpha_j$ and $a_{ij} = 0$ if $\beta_i \not\leq \alpha_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. \begin{Example} \label{distributivelattice} {\em Let $L$ be the finite distribute lattice % with the Hasse diagram drawn below. \begin{center} \unitlength=0.5mm \begin{picture}(108,88)(0,5) \put(54,88){\makebox(0,0){\circle*{3}}} \put(47,88){\makebox(0,0){$\alpha_8$}} \put(68,67){\makebox(0,0){\circle*{3}}} \put(73,67){\makebox(0,0){$\alpha_7$}} \put(40,67){\makebox(0,0){\circle*{3}}} \put(33,67){\makebox(0,0){$\alpha_6$}} \put(82,46){\makebox(0,0){\circle*{3}}} \put(87,46){\makebox(0,0){$\alpha_5$}} \put(54,46){\makebox(0,0){\circle*{3}}} \put(47,46){\makebox(0,0){$\alpha_4$}} \put(68,25){\makebox(0,0){\circle*{3}}} \put(73,25){\makebox(0,0){$\alpha_3$}} \put(40,25){\makebox(0,0){\circle*{3}}} \put(33,25){\makebox(0,0){$\alpha_2$}} \put(54,4){\makebox(0,0){\circle*{3}}} \put(47,4){\makebox(0,0){$\alpha_1$}} % \put(53,4){\line(2,3){28}} \put(53,4){\line(-2,3){14}} \put(39,25){\line(2,3){28}} \put(67,25){\line(-2,3){28}} \put(81,46){\line(-2,3){28}} \put(39,67){\line(2,3){14}} \end{picture} \end{center} \smallskip \begin{center} {\small {\bf Figure 2.1.} A finite distributive lattice } \end{center} \medskip \noindent Its join-irreducible elements are $\alpha_1, \alpha_2, \alpha_3, \alpha_5$ and $\alpha_6$. The configuration $A_L$ is \begin{eqnarray*} \left[ \begin{array}{cccccccc} 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{array} \right]. \end{eqnarray*} } \end{Example} Let $S =K[x_1, \ldots, x_n]$ and $I_{A(L)} \subset S$ the toric ideal of $A(L)$. For each pair $(\alpha_i, \alpha_j)$ with $i < j$ such that $\alpha_i$ and $\alpha_j$ are incomparable in $L$, we introduce the binomial $f_{i,j} = x_ix_j - x_kx_\ell$, where $\alpha_k = \alpha_i \wedge \alpha_j$ and $\alpha_\ell = \alpha_i \vee \alpha_j$. One has $f_{i,j} \in I_{A(L)}$. Write ${\mathcal 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 > \cdots > x_n$ of the variables. \begin{Theorem}[\cite{Hibidistributivelattice}] \label{nice} Working with the same notation as above, ${\mathcal G}$ is a Gr\"obner basis of $I_{A(L)}$ with respect to $<_{\rev}$. \end{Theorem} For example, in the finite distributive lattice of Figure $2.1$, the Gr\"obner basis ${\mathcal G}$ consists of the quadratic binomials \begin{center} $x_2x_3-x_1x_4, \, \, \, x_2x_5-x_1x_7, \, \, \, x_4x_5-x_3x_7,$ $x_5x_6-x_3x_8, \, \, \, x_6x_7-x_4x_8.$ \end{center} \bigskip \begin{center} {\bf (b) Classical root systems} \end{center} Let $\Phi \subset \ZZ^n$ be one of the classical irreducible root systems ${\bf A}_{n-1}, {\bf B}_n, {\bf C}_n$ and ${\bf D_n}$ (\cite[pp.~64--65]{Hum}) and write $\Phi^{(+)}$ for the matrix whose column vectors are all positive roots of $\Phi$ together with the origin of $\RR^n$. Let ${\tilde \Phi^{(+)}}$ be the configuration obtained by adding the row vector $(1, 1, , \ldots, 1)$ to $\Phi^{(+)}$. For example, \begin{eqnarray*} {\tilde {\bf A}_2^{(+)}} = \left[ \begin{array}{cccc} 0& 1& 1& 0\\ 0&-1& 0& 1\\ 0& 0&-1&-1\\ 1& 1& 1& 1 \end{array} \right], \, \, \, \, \, \, \, \, \, \, % \end{eqnarray*} % \begin{eqnarray*} {\tilde {\bf D}_3^{(+)}} = \left[ \begin{array}{ccccccc} 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{array} \right], \end{eqnarray*} \begin{eqnarray*} {\tilde {\bf B}_3^{(+)}} = \left[ \begin{array}{cccccccccc} 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{array} \right], \end{eqnarray*} \begin{eqnarray*} {\tilde {\bf C}_3^{(+)}} = \left[ \begin{array}{cccccccccc} 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{array} \right]. \end{eqnarray*} \smallskip \begin{Theorem}[\cite{GGP}] The toric ideal of the configurations ${\tilde {\bf A}_{n-1}^{(+)}}$ possesses an initial ideal generated by squarefree quadratic monomials. \end{Theorem} \begin{Theorem}[\cite{OhHirootsystem}] \label{OHHIROOT} The toric ideal of each of the configurations ${\tilde {\bf B}_n^{(+)}}, {\tilde {\bf C}_n^{(+)}}$ and ${\tilde {\bf D}_n^{(+)}}$ possesses an initial ideal generated by squarefree quadratic monomials. \end{Theorem} \medskip \begin{center} {\bf (c) Finite bipartite graphs} \end{center} Let $G$ be a finite graph on the vertex set $[d] = \{ 1, \ldots, d \}$ and $e_1, \ldots, e_n$ its edges. The {\em incidence matrix} of $G$ is the configuration $A_G = \{ a_{ij} \}_{\genfrac{}{}{0pt}{}{1 \leq i \leq d} { 1 \leq j \leq n}}$, where $a_{ij} = 1$ if $i \in e_j$ and $a_{ij} = 0$ if $i \not\in 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{eqnarray*} \left[ \begin{array}{ccccccc} 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{array} \right]. \end{eqnarray*} \begin{Theorem}[\cite{OhHibipartite}] \label{BIPARTITE} 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: \begin{enumerate} \item[(i)] $I_{A_G}$ is generated by quadratic binomials; \item[(ii)] $I_{A_G}$ possesses an initial ideal generated by squarefree quadratic monomials; \item[(iii)] Every cycle of $G$ of length $> 4$ has a chord. \end{enumerate} \end{Theorem} Finally, we refer the reader to, e.g., \cite{AHOT} for initial ideals generated by squarefree quadratic monomials arising in algebraic statistics. \section{Generic initial ideals and algebraic shifting} % a field of characteristic $0$; in other words, % none of the finite sum of the form % $1 + \cdots + 1$ is equal to $0$ in $K$. Let $S = K[x_1, \ldots, x_n]$ denote the polynomial ring in $n$ variables over an {\em infinite} field $K$ with %Christian: each $\deg x_i = 1$ for $i=1,2,\dots,n$. Write $\GL_n(K)$ for % the general linear group, that is, the group of all invertible $n \times n$ matrices with entries in $K$. For each $\varphi = (a_{ij})_{\genfrac{}{}{0pt}{}{1 \leq i \leq n} { 1 \leq j \leq n}} \in \GL_n(K)$ and for each $f = f(x_1, \ldots, x_n) \in S$, one defines \[ \varphi(f) = f\left(\sum_{i=1}^na_{i1}x_i,\ldots, \sum_{i=1}^na_{in}x_i\right). \] If $I$ is a homogeneous ideal of $S$, i.e., an ideal of $S$ generated by homogeneous polynomials, and if $\varphi = (a_{ij})_{\genfrac{}{}{0pt}{}{1 \leq i \leq n} { 1 \leq j \leq n}} \in \GL_n(K)$, then $\varphi(I) = \{ \varphi(f) : f \in I \}$ is again a homogeneous ideal of $S$. \begin{Theorem}[\sc Galligo, Bayer--Stillman] \label{gin} Work with the reverse lexicographic order $<_{\rev}$ on $S$ induced by $x_1 > \cdots > x_n$. Let $I$ be a homogeneous ideal of $S$. If $\varphi, \varphi' \in \GL_n(K)$ are ``generic,'' then $\initial_{<_{\rev}}(\varphi(I)) = \initial_{<_{\rev}}(\varphi'(I))$. \end{Theorem} To understand the precise definition that $\varphi, \varphi' \in \GL_n(K)$ are ``generic,'' the language of algebraic geometry will be required. What Theorem~\ref{gin} guarantees is that, whenever we choose the entries of $\varphi$ and $\varphi'$ ``randomly,'' one has $\initial_{<_{\rev}}(\varphi(I)) = \initial_{<_{\rev}}(\varphi'(I))$. We write \[ \Gin(I) = \initial_{<_{\rev}}(\varphi(I)), \] where $\varphi \in \GL_n(K)$ is generic, and call $\Gin(I)$ the {\em generic initial ideal} of $I$. We refer the reader who is familiar with commutative algebra and algebraic geometry to \cite{Green} for the foundations of generic initial ideals. \begin{Example} \label{example(3a)} {\em Let $n = 2$ and write $x$ and $y$ instead of $x_1$ and $x_2$ respectively. Let $I = (x^2, y^2) \subset K[x, y]$ and \begin{eqnarray*} \varphi = \left[ \begin{array}{cc} a & b \\ c & d \\ \end{array} \right]. \end{eqnarray*} Thus $\varphi(I) = ((ax+by)^2, (cx+dy)^2$. Suppose that $ad - bc \neq 0$ and $ac \neq 0$. We compute $\initial_{<_{\rev}}(\varphi(I))$. Let $f = (ax+by)^2$ and $g = (cx+dy)^2)$. \begin{itemize} \item Since $a \neq 0$, one has $\initial_{<_{\rev}}(f) = x^2 \in \initial_{<_{\rev}}(\varphi(I))$. Since $c^2 f - a^2 g \in I$ and $ad - bc \neq 0$, it follows that $h_0 = 2acxy + (ad + bc)y^2 \in I$. Since $ac \neq 0$, one has $\initial_{<_{\rev}}(h_0) = xy \in \initial_{<_{\rev}}(\varphi(I))$. \item One has $y^2 \not\in \initial_{<_{\rev}}(\varphi(I))$. In fact, if $y^2 \in \initial_{<_{\rev}}(\varphi(I))$, then $y^2 \in I$. Thus $Cy^2 = Af + Bg$, where $A, B, C \in K$ with $C \neq 0$. Hence $a^2A + c^2B = 0$ and $abA + cdB = 0$. However, since $ad -bc \neq 0$ and $ac \neq 0$, one has $A = B = 0$. \item Let $h_1 = 2cyf - axh_0 = a(3bc - ad)xy^2 + 2b^2cy^3 \in I$. Since $$2ch_1 - (3bc - ad)yh_0 = (ad - bc)^2y^3 \in I$$ and $ad - bc \neq 0$, one has $y^3 \in I$. Thus $y^3 \in \initial_{<_{\rev}}(\varphi(I))$. \item Consequently, since $(x^2, xy, y^3) \subset \initial_{<_{\rev}}(\varphi(I))$, it follows that all monomials in $K[x, y]$ except for $x, y$ and $y^2$ must belong to $\initial_{<_{\rev}}(\varphi(I))$. Since $\deg f = \deg g = 2$, it is clear that none of $x$ and $y$ belongs to $\initial_{<_{\rev}}(\varphi(I))$. Finally, since $y^2 \not\in \initial_{<_{\rev}}(\varphi(I))$, it follows that $\initial_{<_{\rev}}(\varphi(I)) = (x^2, xy, y^3)$. \end{itemize} If we choose the entries $a, b, c$ and $d$ of $\varphi$ ``randomly,'' then we could expect $ad - bc \neq 0$ and $ac \neq 0$. Hence if $\varphi$ is ``generic,'' then one has $\initial_{<_{\rev}}(\varphi(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)$. } \end{Example} Let ${\mathcal M}_n$ denote the set of monomials in the variables $x_1, \ldots, x_n,$ and ${\mathcal M}_n^{(sq)}$ the subset of ${\mathcal M}_n$ consisting of all squarefree monomials belonging to ${\mathcal M}_n$. Let ${\mathcal M} = \bigcup_{n=1}^{\infty} {\mathcal M}_n$ and ${\mathcal M}^{(sq)} = \bigcup_{n=1}^{\infty} {\mathcal M}_n^{(sq)}$. Given a monomial \[ u = x_{i_1} x_{i_2} \cdots x_{i_j} \cdots x_{i_r} \] of ${\mathcal M}$, where \[ 1 \leq i_1 \leq i_2 \leq \cdots \leq i_j \leq \cdots \leq i_r, \] we introduce the squarefree monomial $u^\sigma \in {\mathcal M}^{(sq)}$ by setting \[ u^\sigma = x_{i_1} x_{i_2 + 1} \cdots x_{i_j + (j - 1)} \cdots x_{i_r + (r - 1)}. \] For example, \[ (x_1^3x_2x_3^2x_5)^\sigma =(x_1x_1x_1x_2x_3x_3x_5)^\sigma = x_1x_2x_3x_5x_7x_8x_{11}. \] The operator $\sigma : {\mathcal M} \to {\mathcal M}^{(sq)}$ is called the {\em squarefree operator} on ${\mathcal M}$. \begin{Example} {\em Let ${\mathcal M}_n(d)$ denote the set of monomials of degree $d$ belonging to ${\mathcal M}_n$ and ${\mathcal M}_n^{(sq)}(d)$ the set of squarefree monomials of degree $d$ belonging to ${\mathcal M}_n^{(sq)}$. Since $(x_1^d)^\sigma = x_1 x_2 \cdots x_{d}$ and $(x_n^d)^\sigma = x_n x_{n+1} \cdots x_{n+d-1}$, it follows that $\sigma$ induces a bijection between ${\mathcal M}_n(d)$ and ${\mathcal M}_{n+d-1}^{(sq)}(d)$. } \end{Example} We summarize fundamental materials on simplicial complexes from, e.g., \cite{HibiRedBook} and \cite{StanleyGreenBook}. Let $[n] = \{ 1, 2, \ldots, n \}$ be the vertex set and $\Delta$ a simplicial complex on $[n]$. Thus $\Delta$ is a collection of subsets of $[n]$ satisfying that $($i$)$ $\{ i \} \in \Delta$ for all $i \in [n]$ and $($ii$)$ if $F \in \Delta$ and $F' \subset [n]$ with $F' \subset F$, then $F' \in \Delta$. Each element $F \in \Delta$ is called a {\em face} of $\Delta$. The dimension of a face $F$ is $|F| - 1$, where the notation $|F|$ stands for the cardinality of $F$. The {\em dimension} of $\Delta$ is $\dim \Delta = d - 1$, where $d = \max \{ |F| : F \in \Delta \}$. % An {\em edge} is a face of dimension $1$. A {\em facet} of $\Delta$ is a maximal face of $\Delta$ (with respect to inclusion). We say that $\Delta$ is {\em pure} if all facets of $\Delta$ have the same cardinality. For each $ i = 0, 1, \ldots, d - 1$, we write $f_i = f_i(\Delta)$ for the number of faces of $\Delta$ of dimension $i$. The sequence $f(\Delta) = (f_0, f_1, \ldots, f_{d-1})$ is called the {\em $f$-vector} of $\Delta$. The {\em $h$-vector} $h(\Delta) = (h_0, h_1, \ldots, h_d)$ is defined by the formula \[ \sum_{i=0}^d{} f_{i-1} (x - 1)^{d-i} = \sum_{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 + \cdots + h_d = f_{d-1}$. In order to visualize a simplicial complex $\Delta$ we often identify $\Delta$ with its {\em geometric realization} $|\Delta|$. For example, Figure 3.1 illustrates the simplicial complex $\Delta$ on $[5]$ of dimension $2$ whose facets are $\{1,2,4\}, \{1,2,5\}, \{2,3\}$ and $\{3,4\}$. Its $f$-vector is $f(\Delta) = (5,7,2)$ and its $h$-vector is $h(\Delta) = (1,2,0,-1)$. \begin{center} \unitlength=1mm \begin{picture}(120,50)(0,5) \put(54.9,46){\makebox(0,0){\circle*{12}}} \put(48,46){\makebox(0,0){$5$}} \put(42,25){\makebox(0,0){\circle*{12}}} \put(34,25){\makebox(0,0){$1$}} \put(68,25){\makebox(0,0){\circle*{12}}} \put(70,25){\makebox(0,0){$2$}} \put(54.7,4){\makebox(0,0){\circle*{12}}} \put(48,4){\makebox(0,0){$4$}} \put(82,4){\makebox(0,0){\circle*{12}}} \put(84,4){\makebox(0,0){$3$}} % \put(39.7,26.2){\line(2,3){13}} \put(39.8,26.2){\line(2,3){13}} \put(39.9,26.2){\line(2,3){13}} \put(40,26.2){\line(2,3){13}} \put(40.1,26.2){\line(2,3){13}} % \put(65.5,26.5){\line(-2,3){12}} \put(65.4,26.5){\line(-2,3){12}} \put(65.3,26.5){\line(-2,3){12}} \put(65.2,26.5){\line(-2,3){12}} \put(65.1,26.5){\line(-2,3){12}} % \put(40,23.5){\line(2,-3){12}} \put(40.1,23.5){\line(2,-3){12}} \put(40.2,23.5){\line(2,-3){12}} \put(40.3,23.5){\line(2,-3){12}} \put(40.4,23.5){\line(2,-3){12}} % \put(53,5.5){\line(2,3){12}} \put(53.1,5.5){\line(2,3){12}} \put(53.2,5.5){\line(2,3){12}} \put(53.3,5.5){\line(2,3){12}} \put(53.4,5.5){\line(2,3){12}} % \put(40,24.8){\line(1,0){24.7}} \put(40,24.9){\line(1,0){24.7}} \put(40,25){\line(1,0){24.7}} \put(40,25.1){\line(1,0){24.7}} \put(40,25.2){\line(1,0){24.7}} % \put(67.5,23.5){\line(2,-3){12}} \put(67.6,23.5){\line(2,-3){12}} \put(67.7,23.5){\line(2,-3){12}} \put(67.8,23.5){\line(2,-3){12}} \put(67.9,23.5){\line(2,-3){12}} % \put(54,3.9){\line(1,0){24.7}} \put(54,3.9){\line(1,0){24.7}} \put(54,4){\line(1,0){24.7}} \put(54,4.1){\line(1,0){24.7}} \put(54,4.2){\line(1,0){24.7}} % % % \put(40,25){\line(1,0){25}} \put(40.3,25.5){\line(1,0){25}} \put(40.3,26){\line(1,0){25}} \put(40.6,26.5){\line(1,0){25}} \put(40.9,27){\line(1,0){25}} \put(41.2,27.5){\line(1,0){25}} \put(41.5,28){\line(1,0){22}} \put(41.8,28.5){\line(1,0){22}} \put(42.1,29){\line(1,0){21.5}} \put(42.4,29.5){\line(1,0){21}} \put(42.7,30){\line(1,0){20}} \put(43,30.5){\line(1,0){19.5}} \put(43.3,31){\line(1,0){19}} \put(43.6,31.5){\line(1,0){18.3}} \put(44,32){\line(1,0){17.8}} \put(44.3,32.5){\line(1,0){17}} \put(44.6,33){\line(1,0){16.3}} \put(45,33.5){\line(1,0){15.8}} \put(45.1,34){\line(1,0){15.3}} \put(45.5,34.5){\line(1,0){14.9}} \put(45.7,35){\line(1,0){14.1}} \put(45.9,35.5){\line(1,0){13.5}} \put(46.3,36){\line(1,0){12.7}} \put(46.6,36.5){\line(1,0){12.1}} \put(46.9,37){\line(1,0){11.5}} \put(47.4,37.5){\line(1,0){10.7}} \put(47.5,38){\line(1,0){10.2}} \put(47.8,38.5){\line(1,0){9.4}} \put(48.1,39){\line(1,0){8.8}} \put(48.4,39.5){\line(1,0){7.8}} \put(48.7,40){\line(1,0){7.5}} \put(49,40.5){\line(1,0){6.9}} \put(49.6,41){\line(1,0){6.2}} \put(49.9,41.5){\line(1,0){5.6}} \put(50.3,42){\line(1,0){5}} \put(50.5,42.5){\line(1,0){4.3}} \put(50.9,43){\line(1,0){4}} \put(51.5,43.5){\line(1,0){3}} % \put(38.5,26.5){\line(1,0){25}} \put(39,26){\line(1,0){25}} \put(39,25.5){\line(1,0){25}} \put(39,25){\line(1,0){25}} \put(39.5,24.5){\line(1,0){25}} \put(39,24){\line(1,0){25}} \put(39,23.5){\line(1,0){25}} \put(39,23){\line(1,0){25}} \put(41,22.5){\line(1,0){23.5}} \put(41,22){\line(1,0){22.7}} \put(42,21.5){\line(1,0){21.8}} \put(42.3,21){\line(1,0){21.3}} \put(42.6,20.5){\line(1,0){20.8}} \put(42.9,20){\line(1,0){20.3}} \put(43.2,19.5){\line(1,0){18.8}} \put(43.5,19){\line(1,0){18.3}} \put(43.8,18.5){\line(1,0){17.8}} \put(44.1,18){\line(1,0){16.8}} \put(44.4,17.5){\line(1,0){16.3}} \put(44.7,17){\line(1,0){15.7}} \put(45,16.5){\line(1,0){15.1}} \put(45.3,16){\line(1,0){14.6}} \put(45.6,15.5){\line(1,0){13.7}} \put(45.9,15){\line(1,0){13}} \put(46.2,14.5){\line(1,0){12.4}} \put(46.5,14){\line(1,0){11.8}} \put(46.8,13.5){\line(1,0){11.2}} \put(47.1,13){\line(1,0){10.6}} \put(47.4,12.5){\line(1,0){10}} \put(47.7,12){\line(1,0){9.5}} \put(48,11.5){\line(1,0){9.2}} \put(48.3,11){\line(1,0){8.6}} \put(48.6,10.5){\line(1,0){7.7}} \put(49,10){\line(1,0){6.8}} \put(50.2,9.5){\line(1,0){5.5}} \put(50.5,9){\line(1,0){4.5}} \put(50.8,8.5){\line(1,0){4}} \put(51.1,8){\line(1,0){4}} \put(51.4,7.5){\line(1,0){3}} \put(51.7,7){\line(1,0){2.5}} \put(51.7,6.5){\line(1,0){2.5}} \end{picture} \end{center} \medskip \begin{center} {\small {\bf Figure 3.1.} A geometric realization of $\Delta$ } \end{center} \medskip % Let, as before, $S = K[x_1, \ldots, x_n]$ % denote the polynomial ring. We associate each subset $F \subset [n]$ with the squarefree monomial $x_F = \prod_{i \in F} x_i$ of $S$. % $S = K[x_1, \ldots, x_n]$. A {\em squarefree ideal} of $S$ is an ideal of $S$ which is generated by squarefree monomials. Given a simplicial complex $\Delta$ on $[n]$, we define its {\em Stanley--Reisner ideal} to be the squarefree ideal \[ I_\Delta = ( \{ x_F : F \subset [n], F \not\in \Delta \} ) \] of $S$. Conversely, it follows easily that, given a squarefree ideal $I$ of $S$ with $x_i \not\in I$ for each $1 \leq i \leq n$, there exists a unique simplicial complex $\Delta$ on $[n]$ with $I = I_\Delta$. \begin{Example} \label{SRideal} {\em Let $\Delta$ be the simplicial complex of Figure 3.1. Its Stanley--Reisner ideal is $I_\Delta = (x_1x_3, x_3x_5, x_4x_5, x_2x_3x_4)$. } \end{Example} Algebraic shifting, introduced by Gil Kalai in 1984, turns out to be one of the powerful techniques in algebraic combinatorics on convex polytopes. In \cite{Kalai} 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 $\Delta$ be a simplicial complex on $[n]$ and $I_\Delta \subset S = K[x_1, \ldots, x_n]$ its Stanley--Reisner ideal. Let $\Gin(I_\Delta)$ denote the generic initial ideal of $I_\Delta$ and $\{ u_1, \ldots, u_q\}$ the (unique) minimal system of monomial generators of $\Gin(I_\Delta)$. \begin{Lemma}[\cite{Herzog}] \label{crucial} Each squarefree monomial $u_i^\sigma$ belongs to $S$. In other words, $(u_1^\sigma, \ldots, u_q^\sigma)$ is a squarefree ideal of $S$. \end{Lemma} \begin{Definition}[\cite{Herzog}] \label{algebraicshifting} {\em The {\em symmetric algebraic shifted complex} of $\Delta$ is the simplicial complex $\Delta^s$ on $[n]$ with $I_{\Delta^s} = (u_1^\sigma, \ldots, u_q^\sigma)$. } \end{Definition} The operator $\Delta \to \Delta^s$ is called {\em symmetric algebraic shifting}. In \cite{Kalai} exterior algebraic shifting as well as symmetric algebraic shifting is introduced. A simplicial complex $\Delta$ on $[n]$ is called {\em shifted} if $F \in \Delta, \, j \in F$ and $i > j$ imply $(F \setminus \{ j \}) \cup \{ i \} \in \Delta$. The shifted complexes played an important role in classical combinatorics on finite sets. \begin{Lemma}[\cite{Herzog} and \cite{Kalai}] Let $\Delta$ and $\Delta'$ be simplicial complexes. \begin{itemize} \item $\Delta^s$ is shifted; \item $f(\Delta^s) = f(\Delta)$; \item If $\Delta$ is shifted, then $\Delta^s = \Delta$; \item If $\Delta \subset \Delta'$, then $\Delta^s \subset (\Delta')^s$. \end{itemize} \end{Lemma} Let ${\mathcal P} \subset \RR^N$ be a simplicial polytope \cite[p.~9]{HibiRedBook} of dimension $d$ with $n$ vertices and $\Delta({\mathcal P})$ its boundary complex \cite[p.~10]{HibiRedBook}. It follows that $\Delta({\mathcal P})$ is a simplicial complex on $[n]$ of dimension $d - 1$ whose geometric realization is homeomorphic to the $(d - 1)$-sphere $\SS^{d-1}$. A {\em simplicial $(d - 1)$-sphere} is a simplicial complex of dimension $d - 1$ whose geometric realization is homeomorphic to the $(d - 1)$-sphere $\SS^{d-1}$. Every boundary complex of a simplicial polytope of dimension $d$ is a simplicial $(d - 1)$-sphere. The $h$-vector $h(\Delta) = (h_0, h_1, \ldots, h_d)$ of a simplicial $(d - 1)$-sphere is nonnegative (\cite[pp.~44--45]{HibiRedBook}) and symmetric (\cite[p.~24]{HibiRedBook}), i.e., each $h_i \geq 0$ and $h_i = h_{d-i}$ for $0 \leq i \leq 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 ${\mathcal M}$ denote the set of monomials in the variables $x_1, x_2, \ldots$ with %Christian: each $\deg x_i = 1$ for $i=1,2,\dots$. A finite subset ${\mathcal B}$ of ${\mathcal M}$ is called an {\em order ideal of monomials} if whenever $u$ and $v$ are monomials with $u \in {\mathcal B}$ and if $v$ divides $u$, then $v \in {\mathcal B}$. A finite sequence $(h_0, h_1, \ldots, h_s)$ of integers is called an {\em $M$-vector} if there exists an order ideal of monomials ${\mathcal B}$ such that $|\{ u \in {\mathcal B} : \deg u = i \}| = h_i$ for $0 \leq i \leq s$. \begin{Theorem} [\sc Billera--Lee, Stanley] \label{thm:BLS} Given a finite sequence $(h_0, h_1, \ldots, h_d)$ of positive integers, there exists a simplicial polytope ${\mathcal P}$ of dimension $d$ with\break $h(\Delta({\mathcal P}) = (h_0, h_1, \ldots, h_d)$ if and only if the following conditions are satisfied: \begin{enumerate} \item[(i)] $h_0 = 1$; \item[(ii)] $h_i = h_{d-i}$ for $0 \leq i \leq d$; \item[(iii)] $(h_0, h_1 - h_0, h_2 - h_1, \ldots, h_{[d/2]} - h_{[d/2]-1})$ is an $M$-vector. \end{enumerate} \end{Theorem} In particular, the $h$-vector $h(\Delta({\mathcal P}) = (h_0, h_1, \ldots, h_d)$ of the boundary complex of a simplicial polytope of dimension $d$ satisfies \[ h_0 \leq h_1 \leq \cdots \leq h_{[d/2]}. \] \begin{Conjecture}[\sc $g$-conjecture] \label{gconjecture} Let $\Delta$ be a simplicial $(d - 1)$-sphere with $h(\Delta) = (h_0, h_1, \ldots, h_d)$. Then $(h_0, h_1 - h_0, h_2 - h_1, \ldots, h_{[d/2]} - h_{[d/2]-1})$ is an $M$-vector. \end{Conjecture} Let $n > d$. We write $C(n,d)$ for the convex hull of $n$ points $a(t_1), \ldots, a(t_n)$, where $t_1 < \cdots < t_n$, in the moment curve $\{ a(t) = (t, t^2, \ldots, t^d) \in \RR^d : t \in \RR \}.$ It is known (\cite[p.~26]{HibiRedBook}) that $C(n,d)$ is a simplicial polytope of dimension $d$ with $\{ a(t_1), \ldots, a(t_n) \}$ its vertex set. We say that $C(n,d)$ is the {\em cyclic polytope of type} $(n,d)$. The combinatorial type \cite[p.~27]{HibiRedBook} of the boundary complex $\Delta(C(n,d))$ is independent of the particular choice of real numbers $t_1 < \cdots < t_n$. Thus in particular the $f$-vector (and $h$-vector) of $\Delta(C(n,d))$ is independent of the particular choice of real numbers $t_1 < \cdots < t_n$. Kalai computed the symmetric algebraic shifted complex of $\Delta(C(n,d))$. The following conjecture due to Kalai and Sarkaria is called the ``Shifting Theoretic Upper Bound Conjecture.'' \begin{Conjecture} \label{KS} Every simplicial $(d - 1)$-sphere $\Delta$ on $[n]$ satisfies \[ \Delta^s \subset \Delta(C(n,d))^s. \] \end{Conjecture} Conjecture~\ref{KS} is much stronger than Conjecture~\ref{gconjecture}. In fact, %Christian: the conclusion in the above conjecture implies the conclusion in Conjecture~\ref{gconjecture}. \begin{Lemma}[\sc Kalai] Let $\Delta$ be a simplicial $(d - 1)$-sphere with $h(\Delta) = (h_0, h_1, \ldots,\break h_d)$. Suppose that $\Delta^s \subset \Delta(C(n,d))^s$. Then $(h_0, h_1 - h_0, h_2 - h_1, \ldots, h_{[d/2]} - h_{[d/2]-1})$ is an $M$-vector. \end{Lemma} From a computational viewpoint of commutative algebra, it is strongly desirable to characterize the symmetric shifted complexes of simplicial $(d - 1)$-spheres. Let ${\mathcal A}_n^d$ denote the set of simplicial complexes $\Sigma$ on $[n]$ of dimension $d - 1$ such that \begin{enumerate} \item[(i)] $\Sigma$ is pure; \item[(ii)] $\Sigma$ is shifted; \item[(iii)] the $h$-vector of $\Sigma$ is symmetric; \item[(iv)] $\Sigma \subset \Delta(C(n,d))^s$. \end{enumerate} \begin{Conjecture} \label{KalaiConj} {\em (a)} Every simplicial $(d - 1)$-sphere $\Delta$ on $[n]$ satisfies $\Delta^s \in {\mathcal A}_n^d$. {\em (b)} Conversely, for each $\Sigma \in {\mathcal A}_n^d$, there exists a simplicial $(d - 1)$-sphere $\Delta$ on $[n]$ with $\Delta^s = \Sigma$. \end{Conjecture} Later, Conjecture~\ref{KalaiConj}~(b) will be proved in Theorem~\ref{wonderful}~(b). In 1988 Gil Kalai \cite{Kalai} introduced the squeezed sphere. The original definition given by Kalai is purely combinatorial. We will follow \cite{Murai} and introduce the squeezed sphere in the language of monomial ideals. A monomial ideal $I$ of $S = K[x_1, \ldots, x_n]$ is called {\em strongly stable} if, for each monomial $u \in I$ and for each $i \in [n]$ such that $x_i$ divides $u$, one has $x_j(u / x_i) \in I$ for all $i < j$. \begin{Example} \label{stable} {\em Each of the monomial ideals $(x_1^3, x_1^2x_2, x_1x_2^2, x_2^3)$ and $(x_1^3, x_1^2x_2, x_1x_2^2)$ of $K[x_1, x_2]$ is strongly stable. However, the monomial ideal $(x_1^3, x_1x_2^2, x_3^3)$ of $K[x_1, x_2]$ is not strongly stable. } \end{Example} Fix $p \geq 0$. Let $T_p = K[x_1, \ldots, x_p]$ denote the polynomial ring in $p$ variables with %Christian: each $\deg x_i = 1$ for $i=1,2,\dots,p$ and $\mm = (x_1, \ldots, x_p)$. An {\em $\mm$-primary ideal} of $T_p$ is an ideal $I$ of $T_p$ for which $\mm^N \subset I$ for $N \gg 0$. Here $\mm^N$ is the ideal of $T_p$ generated by all monomials of $T$ of degree $N$. Given a strongly stable $\mm$-primary ideal $I$ of $T_p$ with $I \subset \mm^2$, we construct the squeezed sphere arising from $I$ as follows: \begin{itemize} \item Let $\delta = \delta(I)$ denote the largest number $i \geq 1$ for which $\mm^i \not\subset I$. \item Fix an integer $n \geq p + 2\delta$. Let $d = n - p - 1$. \item Let $\{ u_1, \ldots, u_q \}$ denote the (unique) minimal system of monomial generators of $I$. \item Since $n \geq p + 2\delta$, it follows that $(u_i^\sigma)^\sigma$ belongs to $S = K[x_1, \ldots, x_n]$ for each $1 \leq i \leq q$. \item Let $(I^\sigma)^\sigma$ denote the squarefree ideal $((u_1^\sigma)^\sigma, \ldots, (u_q^\sigma)^\sigma)$ of $S$. \item Write $B_d(I)$ for the simplicial complex on $[n]$ whose Stanley--Reisner ideal coincides with $(I^\sigma)^\sigma$. \end{itemize} \begin{Lemma}[\cite{Kalaisqueezed}] \label{squeezedball} The geometric realization of the simplicial complex $B_d(I)$ is homeomorphic to the $d$-ball $\BB^d$. \end{Lemma} We say that $B_d(I)$ is the {\em 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 $\SS^{d-1}$. We say that $S_{d-1}(I)$ is the {\em squeezed sphere} arising from $I$. In the above algebraic definition of the squeezed ball, since the maximal ideal $I = \mm$ is excluded, the simplex cannot be a squeezed ball. However, for the sake of convenience, we will regard the simplex as a squeezed ball. \begin{Example} \label{squeezedsphere} {\em Let $p = 2$ and $I = \mm^3 = (x_1^3, x_1^2x_2, x_1x_2^2, x_2^3)$. Thus $\delta = 2$. Let $n = p + 2\delta = 6$. Hence $d = n - p - 1 = 3$. Since $((x_1^3)^\sigma)^\sigma = x_1x_3x_5, (x_1^2x_2)^\sigma)^\sigma = x_1x_3x_6, (x_1x_2^2)^\sigma)^\sigma = x_1x_4x_6$ and $(x_2^3)^\sigma)^\sigma = x_2x_4x_6$, one has \[ (I^\sigma)^\sigma =(x_1x_3x_5, x_1x_3x_6, x_1x_4x_6, x_2x_4x_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$. } \end{Example} \begin{Example} \label{octahedron} {\em The boundary complex of an octahedron cannot be a squeezed sphere. } \end{Example} The $h$-vector of the squeezed sphere arising from $I$ can be computed easily. We write $h_i$, $0 \leq i \leq \delta$, for the number of monomials $u$ of $S_p$ of degree $i$ with $u \not\in I$. Thus in particular $h_0 = 1$, $h_1 = p = n - (d + 1)$ and $h_\delta \neq 0$. It follows that such %Christian: the a sequence $(h_0, h_1, \ldots, h_\delta)$ is an $M$-vector. Lemma~\ref{hvector} below then says immediately that every squeezed sphere satisfies the $g$-conjecture. \begin{Lemma} \label{hvector} {\rm (a)} The $h$-vector % $h(B_d(I)) \in \ZZ_{\geq 0}^{d+2}$ of the squeezed ball $B_d(I)$ is $(h_0, h_1, \ldots, h_\delta, 0, \ldots, 0)$. {\rm (b)} Let $\delta'= \min \{ \delta, [d-1/2] \}$. Then the $h$-vector of the squeezed sphere $S_d(I)$ is \[ ( h_0, h_0+h_1,\dots, \sum_{i=0}^{\delta'-1} h_i, \sum_{i=0}^{\delta'} h_i,\dots, \sum_{i=0}^{\delta'} h_i, \sum_{i=0}^{\delta'-1} h_i, \dots, h_0+h_1, h_0 ).\] \end{Lemma} Murai \cite{Murai} %Christian: did succeed succeeded in giving a complete characterization of the symmetric algebraic shifted complexes of squeezed spheres. \begin{Theorem}[\sc Murai \cite{Murai}] \label{wonderful} {\em (a)} Every squeezed $(d - 1)$-sphere $\Delta$ on $[n]$ satisfies $\Delta^s \in {\mathcal A}_n^d$. {\em (b)} Conversely, for each $\Sigma \in {\mathcal A}_n^d$, there exists a squeezed $(d - 1)$-sphere $\Delta$ on $[n]$ with $\Delta^s = \Sigma$. \end{Theorem} Here is a brief outline of Murai's proof of Theorem~\ref{wonderful}. \begin{itemize} \item Each $\Sigma \in {\mathcal A}_n^d$ is strong Lefschetz. Thus in particular $\Sigma \in {\mathcal A}_n^d$ is determined by its faces of dimension $\leq \lfloor d / 2 \rfloor - 1$. \item Kalai \cite{Kalaisqueezed} constructed for the $(\lfloor d / 2 \rfloor - 1)$-skeleton $\Sigma_{\lfloor d / 2 \rfloor - 1}$ of each $\Sigma \in {\mathcal A}_n^d$ a squeezed sphere $S_{\Sigma}$ and conjectured that $(S_\Sigma^s)_{\lfloor d/2 \rfloor - 1} = \Sigma_{\lfloor d/2 \rfloor - 1}$. \item The above conjecture by Kalai was proved by Murai \cite{MuraiPhD}. Thus in order to complete a proof of Theorem~\ref{wonderful} one must show that every squeezed sphere is strong Lefschetz. \item Murai \cite{Murai} showed that every squeezed sphere is strongly edge decomposable, a notion introduced by Nevo \cite{Nevo}, and that a strongly edge decomposable complex is strong Lefschetz. The last result was essentially proved in Babson and Nevo \cite{BabsonNevo} independently. \end{itemize} Finally, the number of combinatorial types of squeezed spheres is much larger than that of boundary %Christian: complex complexes of simplicial polytopes (Kalai \cite{Kalaisqueezed}). However, it seems difficult to find a strongly stable $\mm$-primary ideal $I$ of $T_p$ for which the squeezed sphere $S_{d-1}(I)$ cannot be the boundary complex of a simplicial polytope. \begin{thebibliography}{99} \bibitem{AL} W. Adams and P. Loustaunau, ``An Introduction to Gr\"obner Bases,'' Amer. Math. Soc., Providence, RI, 1994. \bibitem{AHOT} S. Aoki, T. Hibi, H. Ohsugi and A. Takemura, Gr\"obner bases of nested configurations, {\tt ar$\chi$iv:math.AC/0801.0929}. \bibitem{BabsonNevo} E. Babson and E. Nevo, Lefschetz properties and basic constructions on simplicial spheres, {\tt ar$\chi$iv:0802.1058}. \bibitem{BW} T. Becker and V. Weispfenning, ``Gr\"obner Bases,'' Springer--Verlag, Berlin, Heidelberg, New York, 1993. \bibitem{CLO} D. Cox, J. Little and D. O'Shea, ``Ideals, Varieties and Algorithms,'' Springer--Verlag, Berlin, Heidelberg, New York, 1992. \bibitem{Dobra} A. Dobra, Markov bases for decomposable graphical models, {\em Bernoulli} {\bf 9} (2003), 1093--1108. \bibitem{GGP} I. M. Gelfand, M. I. Graev and A. Postnikov, Combinatorics of hypergeometric functions associated with positive roots, {\em in} ``Arnold--Gelfand Mathematics Seminars, Geometry and Singularity Theory'' (V. I. Arnold, I. M. Gelfand, M. Smirnov and V. S. Retakh, Eds.), Birkh\"auser, Boston, 1997, pp.~205--221. \bibitem{Green} M. Green, Generic initial ideals, {\em in} ``Six Lectures on Commutative Algebra'' (J. Elias, J. M. Giral, R. M. Mir\'o--Roig and S. Zarzuela, Eds.) Birkh\"auser, Boston, 1998, pp.~119--186. \bibitem{Herzog} J. Herzog, Generic initial ideals and graded Betti numbers, {\em in} ``Computational Commutative Algebra and Combinatorics'' (T. Hibi, Ed.), Advanced Studies in Pure Math., Volume 33, 2002, pp.~75--120. \bibitem{HibiRedBook} T. Hibi, ``Algebraic Combinatorics on Convex Polytopes,'' Carslaw Publications, Glebe, N.S.W., Australia, 1992. \bibitem{Hibidistributivelattice} T. Hibi, Distributive lattices, affine semigroup rings and algebras with straightening laws, {\em in} ``Commutative Algebra and Combinatorics'' (M. Nagata and H. Matsumura, Eds.), Advanced Studies in Pure Math., Volume 11, 1987, pp.~93--109. \bibitem{Hum} J. E. Humphreys, ``Introduction to Lie Algebras and Representation Theory,'' Second Printing, Revised, Springer--Verlag, Berlin, Heidelberg, New York, 1972. \bibitem{Kalaisqueezed} G. Kalai, Many triangulated spheres, {\em Discrete Comput. Geom.} {\bf 3} (1988), 1--14. \bibitem{Kalai} G. Kalai, Algebraic shifting, {\em in} ``Computational Commutative Algebra and Combinatorics'' (T. Hibi, Ed.), Advanced Studies in Pure Math., Volume 33, 2002, pp.~121--163. \bibitem{MuraiPhD} S. Murai, Generic initial ideals and squeezed spheres, {\em Advances in Math.} {\bf 214} (2007), 701--729. \bibitem{Murai} S. Murai, Algebraic shifting of strongly edge decomposable spheres, {\tt ar$\chi$iv:0709.4518}. \bibitem{Nevo} E. Nevo, Higher minors and Van Kampen's obstruction, {\em Math. Scandi.} {\bf 101} (2007), 161--176. \bibitem{OhHiquadratic} H. Ohsugi and T. Hibi, Toric ideals generated by quadratic binomials, {\em J. Algebra} {\bf 218} (1999), 509--527. \bibitem{OhHiunimodular} H. Ohsugi and T. Hibi, A normal $(0,1)$-polytope none of whose regular triangulations is unimodular {\em Discrete Comput. Geom.} {\bf 21} (1999), 201--204. \bibitem{OhHibipartite} H. Ohsugi and T. Hibi, Koszul bipartite graphs, {\em Adv. in Appl. Math.} {\bf 22} (1999), 25--28. \bibitem{OhHirootsystem} H. Ohsugi and T. Hibi, Quadratic initial ideals of root systems, {\em Proc. Amer. Math. Soc.} {\bf 130} (2002), 1913--1922. \bibitem{Snowbird} H. Ohsugi and T. Hibi, Quadratic Gr\"obner bases arising from combinatorics, {\em in} ``Integer Points in Polyhedra'' (M. Beck, et al., Eds.), Contemporary Math., Volume 452, 2008, pp.~123--138. \bibitem{StanleyGreenBook} R. Stanley, ``Combinatorics and Commutative Algebra,'' Second Edition, Birkh\"auser, Boston, 1995. \bibitem{Sturmfels} B. Sturmfels, ``Gr\"obner Bases and Convex Polytopes," Amer. Math. Soc., Providence, RI, 1995. \end{thebibliography} \end{document}