\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}



