<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\magnification=\magstephalf
\baselineskip=13pt
\hsize = 6.0 truein
\hoffset = 0.2 truein
\vsize = 8.5 truein
\voffset = -0.2 truein

\tolerance=10000
\overfullrule=0pt

%\font\titlefont=cmbx12 scaled\magstep1
%\font\sectionfont=cmbx12
%\font\labelfont=cmss10

%==========================================================================
% enable illustrations
%==========================================================================

\input epsf

\def\draw#1#2#3{
  \removelastskip
  \vskip 0cm plus #1cm
  \goodbreak
  \vskip 0cm plus -#1cm
  \vskip 0.3cm
  \dimen0=#2 true bp
  \ifdim\dimen0&gt;\hsize\dimen0=\hsize\fi
  \epsfxsize=\dimen0
  \centerline{\epsfbox{#3.eps}}
  \count255=\epsfurx
  \advance\count255 by-\epsfllx
  \message{[#3.eps bp width = \number\count255]}
  \goodbreak
  \vskip 0.3cm
}

% #1 is maximum space to leave at bottom of previous page (in cm)
% #2 is desired width after scaling (in bp, truncated to \hsize)
% #3 is root name of .eps file

% with each use, tex log gives original width of each .eps file, as in
%   [figA.eps bp width = 312]

% for example, using the file figA.eps,
% \draw4{208}{figA} % 2/3 size
% \draw4{999}{figA} % fit to page width

%==========================================================================
% matrices and self-fitting arrows
%==========================================================================

\def\bpad{\kern 0.15em}

\def\bmatrix#1{\left[\,\vcenter{\bpad\halign{
  &amp;\bpad\hfil$##$\bpad\hfil\cr
  #1}\bpad}\,\right]}

\def\rightarrowmat#1{
  \setbox1=\hbox{\bpad$\scriptstyle\bmatrix{#1}$\bpad\bpad}
  \mathop{\hbox to\wd1{\rightarrowfill}}\limits^{\box1}}

\def\leftarrowmat#1{
  \setbox1=\hbox{\bpad\bpad$\scriptstyle\bmatrix{#1}$\bpad}
  \mathop{\hbox to\wd1{\leftarrowfill}}\limits^{\box1}}

%==========================================================================
% body of paper
%==========================================================================

\def\Box{
\hskip 12pt minus 4pt
\vrule height 1.2ex width .9ex depth .1ex
\par \goodbreak \vskip .3 cm
}

\def\Leftbox{
\par\noindent
\vrule height 1.2ex width .9ex depth .1ex
\par \goodbreak \vskip .3 cm
}

\centerline{\bf  MONOMIAL RESOLUTIONS }

\vglue .3cm

\centerline{\bf Dave Bayer \ \  Irena Peeva  \ \   Bernd Sturmfels }

\vglue .75cm


\noindent {\bf  1. Introduction.}%----------------------------
\vglue .2cm


\noindent
Let $M$ be a monomial ideal in  the polynomial ring $S=k[x_1,\dots ,x_n]$
 over a field $k$.
We are interested in the problem, first posed by Kaplansky in the early 1960's,
of finding a minimal free resolution of  $S/M$ over $S$.
The difficulty of this problem is reflected in the fact that the
homology of arbitrary simplicial complexes can be encoded (via the
Stanley-Reisner correspondence [BH,Ho,St]) into the multigraded Betti numbers
of $S/M$.  In particular, the minimal free resolution may
depend on the characteristic of $k$.


We introduce a method  for resolving  $S/M$ by
encoding the entire resolution into a single simplicial complex
(Construction~2.1). This method is different from the way
simplicial complexes are used in the
Stanley-Reisner correspondence to compute Betti numbers.

One of the central ideas in this paper is that there
exists a genericity condition, which
ensures simply structured homological behavior.
The same idea is developed further for toric varieties in [PS].
We call a monomial ideal $M$
{\it generic} if no variable $x_i$ appears with the same
nonzero exponent in two distinct minimal generators of $M$.
Almost all monomial ideals are generic, in the sense that those
which fail to be generic  lie on finitely many hyperplanes
in the matrix space of exponents.
We prove that the minimal
free resolution for any generic monomial ideal $M$
comes (in the sense of Construction~2.1)
from a simplicial complex $\Delta_M$, which we call the
{\it Scarf complex} of $M$.
If $M$ is Artinian, then the Scarf complex is a regular
triangulation of a simplex (Corollary 5.5). In general it
need not be pure (Example 3.4), and it need not be shellable
(Example 5.2),
but it is always contractible (Theorem 5.1).
We also relate
the Scarf complex to the irreducible decomposition of $M$
and to the Cohen-Macaulay property (Theorem~3.7 and Corollary~3.9).

In the literature we found only two general constructions for resolving
arbitrary monomial ideals: Taylor's resolution (cf. [Ei, 17.11])
and Lyubeznik's subcomplex
(see [Ly]). For a large number of generators these resolutions
are very far from minimal and inefficient  for applications.
In Section 4  we obtain a  nonminimal free resolution
which comes from Construction~2.1 and
has length at most the number of variables, so it is much smaller
than Taylor's.
Our construction is based on  {\it deformation of exponents}:
we deform $M$ to a nearby generic monomial ideal
$M'$ by using monomials with real exponents, we compute the
Scarf complex $\Delta_{M'}$ of the generic ideal $M'$, and then
we label the vertices of $\Delta_{M'}$
with the generators of the original ideal $M$. This defines
a nonminimal resolution for $S/M$.

In Section~5  we show that, for generic $M$,
 the Scarf complex $\Delta_M$ appears naturally in the boundary
of a certain polytope $P_M$. As an application, in
Section~6 we show that the Betti numbers of an arbitrary monomial ideal
satisfy the inequalities of the Upper Bound Theorem for Convex Polytopes.
Even sharper bounds can be derived by relating the Scarf complex $\Delta_M$
to the concept of order dimension for partially ordered sets
(Theorem 6.4).





\vskip .75cm
\noindent {\bf  2. Taylor complexes.}%----------------------------
\vglue .2cm

\noindent Let $M=\langle m_1, \dots , m_r\rangle$ be a
monomial ideal in $S=k[x_1,\dots ,x_n]$.
For each subset $I$ of $\{1,\dots ,r\}$ we set
$m_I:=lcm(m_i \  \vert \  i\in I)$. Let
$a_I \in {\bf N}^n$ be the exponent vector of $m_I$ and
let $S(-a_I)$ be the free $S$-module with one generator in multidegree
$a_I$. The {\it   Taylor resolution} of $S/M$ is the ${\bf Z}^n$-graded
module ${\bf F}= {\bigoplus}_{I\subseteq \{1,\dots ,r\} } S(-a_I)$
 with basis denoted by
${\{e_I\}}_{I\subseteq \{1,\dots ,r\} }$
and equipped with the differential
$$d(e_I)\ = \ {\sum }_{i\in I} sign(i,I)\cdot
{m_I \over m_{I \setminus  i}} \cdot e_{I \setminus  i}\ ,\eqno(2.1)$$
where $sign(i,I)$ is $(-1)^{j+1}$ if $i$ is the $j$th element in the
ordering of $ I$. This is a free resolution of $S/M$ over $S$
having length $r$ and $2^r$ terms.
It is very far from minimal if $r\gg n$.
A smaller resolution based on Taylor's
resolution was constructed in  [Ly].

Every simplicial complex $\Delta$ on $\{1,\dots ,r\}$
defines a submodule $\,{\bf F}_{{\Delta}} :=
{\bigoplus}_{I\in {\Delta} } S(-a_I)$ of the Taylor resolution
${\bf F}$ which is closed under the differential (2.1).
This ${\bf N}^n$-graded complex of free $S$-modules is described in
more detail in the next construction.

\vskip .2cm

\noindent {\bf Construction~2.1.}
{\sl (Monomial resolution from a labeled simplicial complex) }
\hfill \break
Let $\Delta $ be a simplicial complex whose vertices are labeled by
the generators of $M$. We label each face of $\Delta$ by the least common
multiple of its vertices. The exponent vectors of these monomials
define an ${\bf N}^n$-grading of $\Delta$.
Let ${\bf F}_{\Delta}$  be the ${\bf N}^n$-graded  chain complex of
$\Delta$ over $S$. It is obtained from the simplicial
chain complex by homogenizing the differential. For example,
if $m_1 = x^3y^4$ and $m_2 = xz^3$ form an edge, then its
boundary is $\, d(e_{12}) =  z^3 e_1 -x^2y^4 e_2 $.
If the complex   ${\bf F}_{\Delta}$ is exact then we call it the
{\it resolution defined by the labeled simplicial complex $\Delta$}.
Such a resolution is characteristic-free and an
associative commutative differential graded algebra.
In this case the ${\bf N}^n$-graded Hilbert series of $S/M$ equals
the ${\bf N}^n$-graded  Euler characteristic of $\Delta $
divided by $(1-x_1)\cdots (1-x_n)$.
\Box

\vskip .1 cm

We  use reduced simplicial
homology to determine when ${\bf F}_\Delta$ is exact.

\proclaim Lemma~2.2. The complex ${\bf F}_{{\Delta}}$ is exact
if and only if for every monomial $m$ the simplicial complex
${\Delta}[m]=\{I\in \Delta  \,\vert\,  m_I \hbox{\ divides\ }m\}$
 is empty or acyclic over $k$.

\noindent {\sl Proof:}
Since ${\bf F}_{{\Delta}}$ is  ${\bf N}^n$-graded
it suffices to check exactness in each multidegree.
The component of ${\bf F}_{{\Delta}}$ in multidegree $m$
is a complex of finite-dimensional $k$-vector spaces, which
can be identified with the
chain complex of ${\Delta}[m]$ over $k$.
\Box

\noindent {\bf Remark~2.3.}
Lemma~2.2 shows that Taylor's complex ${\bf F}$ is exact.
In this case ${\Delta}$ is a full $(r\! - \! 1)$-simplex
and ${\Delta}[m]$
is the subsimplex on the minimal generators which divide $m$.
\Box

\vskip .7cm
\noindent {\bf  3. Generic monomial ideals.}%----------------------------
\vglue .2cm


\noindent For any monomial ideal $ M = \langle m_1, \ldots, m_r \rangle $
we define a simplicial complex:
 $${\Delta}_M \; := \;
 \bigl\{\,I \subseteq \{1,\ldots,r\} \,\,
 \vert \,\,\ m_I\not= m_J \ \,\, \hbox{\rm for all  }\ J \subseteq
\{1,\ldots,r\} \, \hbox{ other than }  \, I \,\bigr\}  \eqno (3.1) $$
In Section 5 we will show that ${\Delta}_M $ equals a
 complex  introduced  by  Herbert~Scarf  in the context
of mathematical economics (see [Sc, \S 2.8]). We call
$\Delta_M$ the {\it Scarf complex} of $M$.

 Taylor's resolution ${\bf F}$
is a direct sum of the minimal free resolution of $S/M$
and trivial complexes
$ 0 \longrightarrow S(-a_I) \longrightarrow S(-a_I) \longrightarrow 0$. On
the other hand, if $I\in {\Delta}_M$ then  ${\bf F}$ has a unique minimal
generator in multidegree $a_I$. Therefore, the minimal free resolution of
$S/M$ always contains the complex  ${\bf F}_{{\Delta}_M}$, but is larger in
general.  More precisely,
for every monomial ideal $M$ and every face $I$ of $\Delta_M$,
the minimal free resolution of $S/M$ has a unique generator
in multidegree $a_I$ and the differential acts on these
generators as in (2.1).

\proclaim Lemma~3.1. If all nonzero Betti numbers of $S/M$ are
concentrated in the multidegrees $a_I$
 of the faces $I$ of ${\Delta}_M$,
then ${\bf F}_{{\Delta}_M}$ is the minimal free resolution of $S/M$.

\noindent {\sl Proof: }
 If the minimal free
resolution  of $S/M$ is strictly larger than  ${\bf F}_{{\Delta}_M}$,
then the Taylor resolution has at least
 two basis elements in some multidegree
$a_I$ for $I \in {\Delta}_M$.
This contradicts the definition of $\Delta_M$.
\Box

\proclaim Theorem~3.2.
Let $M$ be a generic monomial ideal.
Then the complex  ${\bf F}_{{\Delta}_M}$
defined by the Scarf complex $\Delta_M$
is the  minimal free resolution of $S/M$ over $S$.

\noindent {\sl Proof: }
If $ I \in \Delta_M$ and $i \in I$ then
$m_{I \setminus i}$ properly divides $m_I$.
Thus we see directly from (2.1) that ${\bf F}_{{\Delta}_M}$
is minimal. It remains to show that ${\bf F}_{{\Delta}_M}$ is exact.
We will apply Lemma 3.1.
Consider any multidegree $a_I$ with $I \not\in \Delta_M $.
 The $j$th Betti number in multidegree $a_I$ equals the
$k$-dimension of the homology of the Koszul complex at
${\bf K}_j\, :=\wedge^j (S/M)^n$ in degree $a_I$.
The component of ${\bf K}_j$ in degree
$a_I$ is contained in the $S/M$-module
$\displaystyle {m_I \over supp(m_I)}{\bf K}_j$,
where $supp(m_I)$
is the maximal square-free monomial dividing $m_I$.
To prove that this component is zero, it suffices to show that
$\displaystyle {m_I \over supp(m_I)}$ is zero in $S/M$.
Choosing $I$ minimal with respect to inclusion, we
may assume  $\, m_I = m_{I \cup i} \,$ for some
$i \in \{1,\ldots,r\}\backslash I $.
The monomials $m_i$ and $m_I$ have different exponents in any fixed  variable
because $M$ is generic. So
 $m_i$ divides  $\displaystyle {m_I \over supp(m_I)}$,
and we are done.
\Box

\proclaim Corollary~3.3. Let $M$ be a generic monomial ideal.
\item{(1)}
The number of $j$-faces of the Scarf complex $\Delta_M$
equals the total Betti number
$\,\beta_{j+1}(S/M)\, =\, dim_k \,Tor_{j+1}^S ( S/M, k)$.
\item{(2)} The minimal free resolution of $S/M$
is characteristic free.  It is ${\bf N}^n$-graded and in
each multidegree the Betti number is either $0$ or $1$.
\item{(3)}
The ${\bf N}^n$-graded Hilbert series of $S/M$
(i.e.~the sum  of all monomials not in $M$) is
$$ { {\sum}_{ I\in {\Delta}_M }(-1)^{|I|} \cdot {m_I} \over
(1- x_1)\cdots (1-x_n)}, $$
and there are no cancellations in the alternating sum in the numerator.

The multigraded Betti numbers of  any monomial ideal
determine its  Hilbert series, but not conversely.
For a generic monomial ideal, by Corollary 3.3,  the multigraded
Hilbert series determines the
 multigraded Betti numbers, and, by Theorem 3.2,
they determine the Scarf complex and the minimal free resolution.
Thus for a generic monomial ideal,
the multigraded Hilbert series determines
the minimal free resolution;
in particular, these two are computationally equivalent.
We next illustrate our results for a small example.

\vskip .2 cm
\noindent{\bf Example~3.4.}
Let $n=3, r=4$ and consider the generic monomial ideal
$\, M\, =\, \langle \, x^2z^3,\, x^3z^2,\, xyz,\, y^2\, \rangle $.
The Scarf complex $\Delta_M$ is
a triangle connected to an edge:

\draw4{254}{figA} % 381 is original width
%\vskip 3.5cm

\noindent
The triangle is labeled by $x^3yz^3$, the edges of the triangle are
labeled by $\,x^3z^3, \, x^2yz^3, \,x^3yz^2$,
and the other edge by $xy^2z$.
The minimal free resolution  of $S/M$ is the
${\bf N}^3$-graded chain complex of
the simplicial complex depicted above:
 $$
 0 \rightarrow S
 \rightarrowmat{y \cr -x \cr z \cr 0 \cr}
 S^4
 \rightarrowmat{-x &amp; -y &amp; 0 &amp; 0 \cr z &amp; 0 &amp; -y &amp; 0 \cr
 0 &amp; xz^2 &amp; x^2z &amp; -y \cr 0 &amp; 0 &amp; 0 &amp; xz \cr}
 S^4
 \rightarrowmat{x^2z^3 &amp;\, x^3z^2 &amp; \, xyz &amp; \, y^2 \cr}
 S \rightarrow S/M \rightarrow 0.
 $$
The Hilbert series of $S/M$ equals
$$\sum \{ \, x^a y^b z^c \,: \,x^a y^b z^c \not\in M \,\}
\quad =  \quad {P(x,y,z)\over (1-x)(1-y)(1-z)}, \qquad \hbox{ where}$$
$$ P(x,y,z) \; = \;
 1-x^2z^3-x^3z^2-xyz-y^2+x^3z^3+x^2yz^3+x^3yz^2+xy^2z-x^3yz^3
 .$$
This polynomial is the ${\bf N}^3$-graded
Euler characteristic of the Scarf complex.
\Box
\vskip .2cm

A resolution $F$ of a cyclic module $S/L$ is a {\it DG-algebra} 
if it admits an associative, graded (by homological degree),
skew commutative product $*$ satisfying the Leibnitz rule  $d(\alpha
*\beta)=d(\alpha)*\beta +(-1)^{deg(\alpha )}\alpha *d(\beta)$. The
prototypical example of a DG-algebra is a Koszul complex, with product
given by exterior multiplication. See [Ku] for motivation and further
examples, where quotient DG-algebras are also considered.
The minimal free resolution of a monomial ideal need not be a
DG-algebra:

\vskip .2cm

\noindent {\bf Example~3.5.} {\sl (Avramov, Backelin)} \
There is no DG-algebra structure on
the minimal free resolution of $S/ \langle x^2,xy^2z,y^2z^2,yz^2w,w^2\rangle $.
This is proved in [Av, 5.2.3]. \Box

\vskip .1 cm

On the other hand, the Taylor resolution of a monomial ideal is always a
DG-algebra, and Theorem 3.2 has the following corollary:

\proclaim Corollary~3.6.
If $M$ is a generic monomial ideal, then the minimal
free resolution of $S/M$ is a quotient DG-algebra of
the Taylor resolution.

\noindent {\sl Proof: } We prove that any complex $F_\Delta$ given by
Construction 2.1 is a quotient DG-algebra of
the Taylor resolution. The Taylor resolution $F$ can be
understood as a divided Koszul complex, and a product modeled after
exterior multiplication gives it a DG-algebra structure: Define $$
e_I*e_J\ :=\  \left\{
\eqalign {
{\ sign (I,J) \cdot {m_Im_J \over m_{I\cup J}}\cdot
 e_{I\cup J}} \ &amp;\quad{\rm if}\ I\cap J=\emptyset ,\ \cr
\ 0\quad \quad &amp;\quad{\rm otherwise.}
}
\right.
$$
Here, if $I=\{i_1 \! &lt; \! \dots
\! &lt; \! i_q\}$ and $J=\{j_1\! &lt; \! \dots \! &lt; \! j_p\}$,
then $sign(I,J)$ is the sign of the permutation
which makes $\, i_1,\dots ,i_q,
j_1,\dots ,j_p \! $ an increasing sequence.
This product is multigraded, and like exterior multiplication it is
associative, skew commutative, and satisfies Leibniz's rule.
For a simplicial complex $\Delta$ the kernel of the map $F \rightarrow
F_\Delta$ is a DG-ideal of $F$, so $F_\Delta$ is a quotient DG-algebra
of $F$. \Box

In the rest of this section we  describe the irreducible
decomposition of a generic monomial ideal
$M$, that is, the unique minimal
expression of $M$ as an intersection of ideals of the form
$\, \langle x_{i_1}^{d_1}, x_{i_2}^{d_2}, \ldots, x_{i_j}^{d_j} \rangle $.
Choose an integer $D$ larger than the degree of any minimal
generator of $M$. We replace $M$ by the Artinian ideal
$$ M^* \quad := \quad M \,\, + \,\, \langle
\, x_1^D, \, \, x_2^D, \, \ldots, \,
\, x_n^D\,\rangle. $$
Let $\Delta_{M^*}$ be the Scarf complex of $M^*$.
This is a simplicial complex on
$\{1,2,\ldots,r,r \!+ \! 1,\ldots,r \! + \! n\}$, where the index
$\,r \!+\!i \,$ is associated with the generator $x_i^D$.
By Corollary 5.5 below, $\Delta_{M^*}$ pure $(n \! - \! 1)$-dimensional.
For each facet $I$ of $\Delta_{M^*}$ we form the irreducible ideal
$$ M_I \quad := \quad \langle \,\, x_s^{p_s} \,\,:\,\,\,
 p_s = deg_{x_s}(m_I) \,\hbox{  and  }\, p_s &lt; D \,\rangle. $$
Note that $M_I$ is independent of the choice of $D$ and
may have less than $n$ generators.

\proclaim Theorem~3.7. A generic monomial ideal $M$ is the
intersection of the irreducible ideals $M_I$,
where $I$ runs over all facets of the Scarf complex
$\Delta_{M^*}$. This intersection is irredundant.

\noindent {\sl Proof: }
We first show that $M$ is contained in $M_I$ for every
facet $I $ of $\Delta_{M^*}$. Let $m_j$ be any minimal
generator of $M$. If $j \in I $ then there exists a variable $x_s$
with $\, deg_{x_s}(m_I)  \, = \, deg_{x_s}(m_j) \, &lt; \, D$.
This implies $m_j  \in M_I$.
If $j \not\in I $ then there is a variable $x_s$
with $ \, deg_{x_s}(m_I) \, &lt; \, deg_{x_s}(m_j) \, &lt; \, D $,
which implies $m_j  \in M_I$ as well.

For the reverse inclusion $\,\bigcap_I M_I \subseteq M$,
we shall prove that every
monomial $m $, which is not in $M$ is not in
$M_I$ for some facet $I$ of $\Delta_{M^*}$.
Let  $m \not\in M$.
We  choose a $D \gg 0$ so that $m \not\in M^*$. Next we select
a monomial $\tilde m$ such that $\,m \cdot \tilde m \not\in M^*$
but $\,x_i \cdot m \cdot \tilde m \in M^* \,$ for $i = 1,2,\ldots,n$.
There exist unique (and necessarily distinct) minimal
generators $\,m_{j_1},\ldots,m_{j_n}$ of $M^*$ with the property
that $m_{j_i} $ divides $\,x_i \cdot m \cdot \tilde m $.
Setting $\, I \, := \, \{ j_1,\ldots,j_n \}$, we have
$\,x_1 x_2 \cdots x_n \cdot  m \cdot \tilde m  \, = m_I $.
This implies $\,m \not\in M_I $.

Finally, we must show that the intersection $\cap M_I$ over
all facets $I$ of $\Delta_{M^*}$ is irredundant.
Fix a facet $I$ and consider the monomial
$\,m \,:= \, m_I/(x_1 x_2 \cdots x_n)$.
Clearly, $m \not\in M_I$. It suffices to show that
$m \in M_J$ for all other facets $J$ of $\Delta_{M^*}$.
Fix another facet $J$. There exists an index $i \in I \backslash J $
and a variable $x_s$ such that
$ \,  deg_{x_s}(m_I) \geq  deg_{x_s}(m_i) \, &gt; \,
deg_{x_s}(m_J) $. This implies
$ \, D \geq deg_{x_s}(m_I)
&gt;  deg_{x_s}(m) \geq deg_{x_s}(m_J) \,$
and therefore $\,m \in M_J$. \Box

\proclaim Example 3.8. \rm
The seven irreducible components of the generic monomial ideal
$$ \langle \,
x y^2 z^3 , \, x^3 y z^2 , \, x^2 y^3 z  \, \rangle
\; = \;
\langle x \rangle \,\cap \,
\langle y \rangle \,\cap \,
\langle z \rangle \,\cap \,
\langle x^3, y^2 \rangle \,\cap \,
\langle y^3, z^2 \rangle \,\cap \,
\langle z^3, x^2 \rangle \,\cap \,
\langle x^3, y^3, z^3 \rangle  $$
 correspond to the seven triangles in the Scarf complex of
the Artinian ideal
$ \,\langle x^4,\, y^4,\,\allowbreak z^4,\,\allowbreak x y^2
z^3,\,\allowbreak x^3 y z^2,\,\allowbreak x^2 y^3 z \,\rangle $. This Scarf
complex is depicted in Example 5.6. \Box

\proclaim Corollary 3.9.
Let $M$ be a generic monomial ideal and $M=\, {\cap}_{I\in \Delta_{M^*}}M_I$
its irreducible irredundant decomposition. Then
$$depth(S/M)\ = \ {min}_{I\in \Delta_{M^*}} \biggl\{\, dim(M_I)\, \biggr\}\,.$$
In particular, $M$ is Cohen-Macaulay if and only if it
is pure-dimensional.

\noindent {\sl Proof: }
Each facet $I$ of $\Delta_{M^*}$
defines a component $M_I$ with
$$ dim(M_I) \quad = \quad  | \, I \cap \{r+1,\ldots,r+n\} \, | . $$
To compute the depth of $S/M$ we consider the
Scarf complex $\Delta_M$. Note that $\Delta_M$
is a subcomplex of $\Delta_{M^*}$
which may have dimension less than $n-1$ and is generally not pure.
The depth of $S/M$ equals the minimum of the numbers
$\,n - | J | \,$ where $J$ runs over all
facets of  $\Delta_{M}$. Every facet $J$ of
$\Delta_{M}$ extends to a facet $I$ of $\Delta_{M^*}$,
and, conversely, if $I$ is a facet of $\Delta_{M^*}$
then $\,I \cap \{1,\ldots,n\}$ is a face of $\Delta_{M}$. Therefore
$$ depth(S/M) \quad = \quad min \biggl\{
 | \, I \cap \{r+1,\ldots,r+n\} \, | \,\, : \,\,
\hbox{$I$ facet of $\Delta_{M^*}$} \,\,\biggr\}. $$
The ideal $M$ being pure-dimensional means that all irreducible components
$M_I$ have the same dimension.
So $M$ is pure-dimensional if and only if $dim(M) = depth(S/M)$. \Box


\vskip .75cm
\noindent {\bf   4. Deformation of exponents.}%----------------------------
\vglue .2cm



\noindent Let $M = \langle m_1,\ldots,m_r \rangle $ be an arbitrary
monomial ideal;
say, $M$ is not generic. In this section we construct a
(typically nonminimal) free resolution of $S/M$
by deforming the exponent vectors of the generators of $M$.
This approach has the following advantages:
\item{$\bullet$} The resolution by deformation of exponents
has length at most the number of variables; thus
in general it is much smaller and shorter than   Taylor's resolution.
\item{$\bullet$} This resolution is a DG-algebra \
(by the proof of Corollary 3.6).
\item{$\bullet$} Section 5
relates the Betti numbers to the $f$-vector of a polytope $P_M$.

\vskip .2cm

\noindent {\bf Construction~4.1.}
Let $\,\{\ a_i=(a_{i1},\dots ,a_{in})\ \vert \ 1\le i\le r\ \}$ be the
exponent vectors of the minimal generators of $M$. Choose vectors
$\,\epsilon_i = (\epsilon_{i1},\ldots, \epsilon_{in}) \in {\bf R}^n \,$
for $1 \leq i \leq r$  such that, for all $i$ and all $s \not= t$, the numbers
$a_{is} + \epsilon_{is}$ and $a_{it} + \epsilon_{it}$ are distinct,
and  $$a_{is} + \epsilon_{is} &lt; a_{it} + \epsilon_{it}
\quad \hbox{implies } \quad a_{is} \leq a_{it}.$$
The last condition is satisfied for all sufficiently small
positive $\epsilon_i$.
Each vector $\epsilon_i$
defines a monomial $\,{\bf x}^{\epsilon_i}
\,= \, x_1^{\epsilon_{i1}} \cdots x_n^{\epsilon_{in}}\,$ with
real exponents. Abbreviate $\,\epsilon := (\epsilon_1, \ldots,\epsilon_r)$.
 We formally introduce the generic
monomial ideal (in a polynomial ring with real exponents):
$$\, M_\epsilon \quad := \quad \langle
\, m_1 \cdot {\bf x}^{\epsilon_1},\,
m_2 \cdot {\bf x}^{\epsilon_2},\, \ldots ,
m_r \cdot {\bf x}^{\epsilon_r}\, \rangle . $$
We call $M_{\epsilon}$ a {\it generic deformation} of $M$.
Let  ${\Delta}_{M_{\epsilon}}$ be the Scarf complex of $M_{\epsilon}$.
We now label the vertex of ${\Delta}_{M_{\epsilon}}$
corresponding to $m_i \cdot {\bf x}^{\epsilon_i}$
with the original monomial $m_i$.
Let ${\bf F}_\epsilon$ be the complex of
$S$-modules defined by this labeling of $\Delta_{M_\epsilon}$
as in Construction 2.1. \Box

\vskip .1cm

\noindent {\bf Example~4.2.}
A simple way of deforming $M$ is to
pick an integer $\nu \! &gt; \! r$ and  set
$\, M_\epsilon \, := \,
\langle \, m_i^\nu \cdot (x_1 x_2 \cdots x_n)^{i}\,\,: \,\,
i = 1,\ldots, r \, \rangle $.
This amounts to choosing $\, \epsilon_{ij} = i/\nu $
in Construction 4.1 since the ideals $ M_\epsilon$ and
$\langle \, m_i \cdot (x_1 x_2 \cdots x_n)^{{i\over \nu}}\,\,: \,\,
i = 1,\ldots, r \, \rangle $ have the same Scarf complex.
If $M$ is square-free then
$\langle m_1,m_2^2,\dots ,m_r^{r} \rangle $
is a generic deformation of $M$. \Box


\proclaim Theorem~4.3.
The complex ${\bf F}_{\epsilon}$ is a free
resolution of $S/M$ over $S$.

\noindent {\sl Proof: } Fix a monomial $m$.
Let $J$ be the largest subset of  $\{1,\dots ,r\}$
such that $m_J$ divides $m$.
The following conditions are equivalent
for a subset $I$ of $\{1,\ldots,r\}$:
$$ m_I \,\,\hbox{divides} \,\, m  \,\,\, \iff \,\,\,
 I \subseteq J \,\,\, \iff \,\,\,
 m_I \,\,\hbox{divides} \,\, m_J  \,\,\, \iff \,\,\,
 m_{I}(\epsilon) \,\,\hbox{divides} \,\, m_{J}(\epsilon). $$
Here $\,m_{I}(\epsilon) := lcm \bigl(
m_i {\bf x}^{\epsilon_i} : i \in I \bigr) $.
The last equivalence follows from our choice of the $\epsilon_{ij}$.
The  set of all faces of $\Delta_{M_\epsilon}$ which satisfy
the four equivalent conditions above
is an acyclic simplicial complex, by Theorem 3.2 and Lemma 2.2
applied to $M_\epsilon [m_{J}(\epsilon)]$.
Now apply Lemma 2.2 to $M$ and $m$
with $\Delta = \Delta_{M_\epsilon}$.  \Box

\proclaim Corollary~4.4. The Betti numbers of $M$ are
less than or equal to those of any deformation $M_\epsilon$,
that is, less than or equal to the face numbers of the Scarf complex
$\Delta_{M_\epsilon}$.

\vskip .2cm

We emphasize that the Betti numbers of $M_{\epsilon}$ depend
on the choice of the generic deformation.
There are finitely many complexes $\Delta_{M_\epsilon}$
which can be obtained by Construction 4.1
and each of them corresponds to an $\epsilon$ lying in an
open convex polyhedral cone in ${\bf R}^{r\cdot n}$.

\vskip .2cm

\noindent {\bf Example~4.5.} Consider the ideal
$M=\langle x^2,xy^2z,y^2z^2,yz^2w,w^2\rangle$
in Example~3.5. A generic deformation is
$M_\epsilon=\langle x^2,xy^2z,y^3z^3,yz^2w,w^2\rangle$.
Label the generators as $1,2,3,4,5$ in the given order.
The Scarf complex  of $M_\epsilon$
consists of the tetrahedron $\{1,2,4,5\}$ and the triangle $\{2,3,4\}$.
Applying Construction~4.1
we obtain a nonminimal free resolution ${\bf F}_{\epsilon}$ of $S/M$.
The Betti numbers of $S/M$ are $1,5,7,4,1$ while
the Betti numbers of $S/M_\epsilon$ are $1,5,8,5,1$.
Thus  ${\bf F}_\epsilon$ differs from the minimal resolution by a single
summand  $\, 0\, \rightarrow \, S\, \rightarrow \, S\, \rightarrow \, 0,$
placed in homological degrees $2$ and $3$.
However, this makes a big difference structurally: by Corollary~3.6,
the resolution
${\bf F}_{\epsilon}$ is a DG-algebra (with a simple multiplication rule)
while the minimal free resolution admits no DG-algebra structure at all.
Note that Taylor's resolution is one step longer than
${\bf F}_\epsilon$. It has Betti numbers $1,5,10,10,5,1$. \Box

\noindent {\bf Remarks~4.6.}
{ \bf (a)}
In deforming monomial ideals we are guided
by the intuition of continuously varying real exponents.
However, no algebra in
a polynomial ring with real exponents is used.
The Scarf complex of a generic monomial ideal depends
only on the coordinatewise order of the exponents
of the generators. If the exponents are real numbers,
then we can replace them by integers while preserving their
order coordinatewise.  We will obtain a
monomial ideal  with integer exponents and the same Scarf complex.

{\bf (b)} The irreducible decomposition of any
monomial ideal $M$ can be computed
by applying Theorem 3.7 to a generic deformation
$M_\epsilon$ and then setting $\epsilon = 0$.

{ \bf (c)}
 Let $W$ be a homogeneous ideal in $S$.
If $u$ is a non-zero-divisor in $S/W$ and $\bf G$ is a resolution of
 $S/W$ over $S$, then ${\bf G} \otimes S/\langle u \rangle$ is a resolution of
 $S/W \,+ \, \langle u \rangle$ over $S/\langle u \rangle$.
This is sometimes called ``deforming the resolution"
and is very useful in Gr\"obner basis theory
and for polarizing monomial ideals into square-free monomial ideals.
We emphasize that it
 is very different from Construction 4.1.
When ``deforming the resolution", one just sets $u=0$ in the matrices
of the differentials in $\bf G$, while Construction 4.1
changes the entries in these matrices in accordance
with the changes of the degrees of the generators.  \Box

\vskip .75cm
\noindent {\bf  5. Convexity}%----------------------------
\vglue .2cm

\noindent
Polytopes are a powerful tool for structuring
combinatorial data appearing in algebra and algebraic
geometry. For example, Newton polytopes play a
significant role in computer algebra,
singularity theory and toric geometry.
In this section we present the polytope
underlying the minimal free resolution of a generic monomial ideal $M$.

Let $M[m]$ be the subideal of $M$
generated by the generators of $M$ which
divide a given monomial $m$.  Then $M[m]$ is a generic
monomial ideal as well, and its Scarf complex equals
$$ {\Delta}_{M[m]} \quad = \quad {\Delta}_M[m]. \eqno (5.1) $$
Lemma~2.1 and  (5.1) imply that the exactness of
${\bf F}_{{\Delta}_M}$ for all $M$
is equivalent to the acyclicity of ${\Delta}_M$
for all $M$. In fact, the following stronger result holds.

\proclaim Theorem~5.1. The  Scarf complex ${\Delta}_M$
of a generic monomial ideal $M$  is contractible.


The Scarf complex need not be pure, and
it need not be shellable either:

\vskip .2cm

\noindent
{\bf Example~5.2.}
Let
$ \, M \, := \,
\langle \,
xyz, \,
x^4y^3, \,
x^3y^5, \,
y^4z^3, \,
y^2z^4, \,
x^2z^2 \,
\rangle $.
The Scarf complex of this generic monomial ideal
consists of two triangles and an edge meeting
at a vertex.

\draw4{357}{figB} % 535 is original width
%\vskip 3.5cm

\noindent
Here $\Delta_M$ is contractible, but not shellable,
even in the nonpure sense of [BW].
\Box

Theorem~5.1 will be derived from Proposition~5.3,
which is an extension  of Theorem 2.8.4 in [Sc, \S 2.8].
In Scarf's book the faces of $\Delta_M$ are called ``primitive sets''.
Scarf's original definition of ``primitive sets''
in [Sc, \S 2.8] is as follows:
$$  I \in \Delta_M \quad \iff \quad
 \forall \,i \in \{1,\ldots,r\} \,\, \exists \, j \in \{1,\ldots,n \} \,:
\,\,\,   a_{I j} \leq a_{ij} \eqno (5.2) $$
where $a_{Ij} = max \{\, a_{ij} \,| \, i \in I  \,\}$.
We will prove  that this is equivalent to our definition  (3.1).

\proclaim Proposition~5.3.
Let $M$ be a generic monomial ideal. There exists a
polytope $P_M$ in ${\bf R}^n$ such that
${\Delta}_M$ is isomorphic to
the subcomplex of the boundary of $P_M$ consisting of all
faces supported by a strictly positive inner normal vector.

\noindent {\bf Construction~5.4.~[Sc]} One possible choice
of a polytope $P_M$ satisfying Proposition 5.3 is as follows.
Let $a_i = (a_{i1}, a_{i2}, \ldots,a_{in}) \in {\bf N}^n$ be
the exponent vector of the $i$-th minimal generator of $M$.
We fix a sufficiently large real number $t \gg 0$ and define
$P_M$ as the convex hull of the point set
$$ \{\, ( a_{i1}^t, a_{i2}^t,\dots ,
a_{in}^t )\  \, \vert \,\, \ 1\le i\le r\ \}
\quad \subset \quad {\bf R}^n . \eqno (5.3) $$
The combinatorial type of $P_M$ is independent of $t$ for  large $t$.
\Box

\noindent {\sl Proof of Proposition 5.3: }
We identify each face of $P_M$ with a subset
$I \subseteq \{1,\ldots,r \}$, namely, the
indices of vertices  which lie on that face.
Let $I$ be a face of $P_M$ with
inner normal vector $(w_1,\ldots,w_n) $ where
$w_j &gt; 0$ for $ j=1,\ldots,n$.
We may assume $$ \forall \, i \in
\{1,\ldots,r \} \,: \,\,\,\, w_1 \cdot a_{i1}^t \, +\,
\cdots \, +\,  w_n \cdot
a_{in}^t \,\, \geq \,\, 1  , \eqno (5.4) $$
and equality holds in (5.4) if and only if $i \in I $.
This implies $\, a_{Ij}\, \leq \, w_j^{- 1/t} \,$
for all $\, j \in \{1,\ldots,n\} $.
At least one of the summands in (5.4)  is greater or equal to $1/n$.
Consequently,
$$ \forall \,i \in \{1,\ldots,r \}
\,\,\,\exists \,j \in \{1,\ldots,n \} \,: \quad
a_{ij} \,\geq\,
w_j^{-1/t} \cdot n^{- 1/t} \,
\geq \,
a_{Ij} \cdot n^{- 1/t} . $$
Now let $t \rightarrow \infty$.
Then we can erase the factor
$\,n^{- 1/t} \rightarrow 1 $, and (5.2) is satisfied.

\vskip .2cm

For the converse we consider the special case where $M$ is Artinian.
We first show that $\Delta_M$ is pure of dimension $n-1$.
We may assume that
$ \,a_{ij} = 0 \,$ for
$1 \leq i \not= j \leq n$ and
$\, a_{li} &lt; a_{ii} \,$
for $1 \leq i \leq n &lt; l \leq r $.
Consider any $I \in \Delta_M$ with $| I | &lt; n$.
Then there exists $i \in I$ such that
$a_i$ and $a_I$ agree in at least two coordinates,
say $j$ and $j'$.
Consider the set
$$ {\cal S} \quad := \quad \bigl\{
\, l \in \{1,\ldots,r\} \,\,\,| \,\,\,
\,a_{lj} &gt; a_{ij} = a_{Ij} \,\, \hbox{and} \,\,
\,\forall i \in I \,\, \exists s \,: a_{is} &gt; a_{ls}\, \bigr\}. $$
It is nonempty since $j \in {\cal S}$.
Select $l \in {\cal S}$ with $a_{lj}$ smallest.
Then $\,I \, \cup \, \{l\} \,\in \,\Delta_M$.


We next consider the
{\it oriented matroid} [BLSWZ] of the configuration
in (5.3) plus the origin. Set
$\,a_{0j} := 0\,$ for all $j\,$ and define for $0 \leq i_0 &lt;  \ldots &lt; i_n
\leq  r$
 $$ [ i_0,i_1,\ldots,i_n ] \,\,\, := \,\,\,
  sign \bigl( det  \pmatrix{
  1 &amp;  a_{i_0 1}^t &amp;  a_{i_0 2}^t &amp; \cdots &amp;  a_{i_0 n}^t \cr
  1 &amp;  a_{i_1 1}^t &amp;  a_{i_1 2}^t &amp; \cdots &amp;  a_{i_1 n}^t \cr
  \vdots &amp;   \vdots &amp;   \vdots &amp; \ddots &amp; \vdots \cr
  1 &amp;  a_{i_n 1}^t &amp;  a_{i_n 2}^t &amp; \cdots &amp;  a_{i_n n}^t \cr} \bigr). $$
Let $I = \{i_1,\dots,i_n\}$ be a maximal face of $\Delta_M$.
There exists a unique permutation
$\sigma = (\sigma_1,\ldots,\sigma_n)$  of $\,I \,$
such that $\, a_{Ij} = a_{\sigma_j j} \, $ for all $j$.
Since $t \gg 0$, we have
$$ sign(\sigma)  \,\,= \,\,    [\, 0, i_1,\ldots,i_n ]. $$
For $j \not\in I$ there exists an $s$ with
$a_{js} &gt; a_{\sigma_j s}$. Laplace expansion
along the $s$-th column gives
$$ [\, j, i_1,\ldots,i_n ] \,\,= \,\, -sign(\sigma)  \quad
\hbox{for all} \,\, j \not\in I  . $$
This shows that $I$ is a facet of $P_M$ which is visible from the
origin. Since $P_M$ intersects each coordinate axis,
the normal vector of $I$ is strictly positive.

Now drop the assumption that $M$ is Artinian
and let $I$ be a maximal face of $\Delta_M$.
Let $M'$ be an Artinian ideal obtained from $M$
by adding large powers of the variables.
Then $I$ lies in $\Delta_{M'}$ as well.
Therefore $I$ is a face of $P_{M'}$  having a
positive inner normal vector, and since $P_{M} \subseteq P_{M'}$,
that same positive vector is minimized over $P_M$ at $I$.
\Box

It follows from our discussion that
the Scarf complex $\Delta_M$ is pure and shellable when
$M$ is Artinian, that is, when every
variable $x_i$ appears to some power in $M$.

\proclaim Corollary~5.5. If $M$ is Artinian and generic,
then ${\Delta}_M$ is a regular triangulation of the $(n-1)$-simplex.

\noindent {\sl Proof: }
See [Zi] for the definition
and basic properties of {\it regular triangulations}. The polytope
 $P_M$ lies in the positive orthant
and intersects each coordinate axis.
Each face of $P_M$ visible from the origin
is a simplex. The set of these faces is $\Delta_M$.
\Box

\vskip .2cm

\noindent
{\bf Example~5.6. } Consider the ideal
$ M\, =\,\langle \, x^4, \, y^4, \,\allowbreak z^4, \,\allowbreak x y^2
z^3, \,\allowbreak x^3 y z^2, \,\allowbreak x^2 y^3 z \rangle $.
 This ideal is Artinian and generic.
The Scarf complex $\Delta_M$ of $M$ is a regular triangulation of a triangle:

\draw4{314}{figC} % 471 is original width
%\vskip 3.5cm

\noindent
Note that $P_M$ is an octahedron.
The minimal free resolution of $S/M$ equals
${\bf F}_{\Delta_M}$. \Box

\vskip .2cm

\noindent {\sl Proof of Theorem~5.1: }
Let $I$ be a face of $P_M$ and
let $\,{\cal N}(I) \,$ denote the inner normal
cone of $P_M$ at $I$.
By Proposition 5.3, the Scarf complex $\Delta_M$ consists of all
faces $I$ such that ${\cal N}(I)$ intersects the open positive
orthant. Choose an $\epsilon &gt; 0 $ such that
$I \in \Delta_M $ if and only if
the closed cone $\,\overline{{\cal N}(I)}\, = \,
 \bigcap_{i \in I }  \overline{{\cal N}(\{i\})}\,$ intersects the
$(n-1)$-simplex
$$ T \quad :=\quad
\bigl\{ \, (u_1,\ldots,u_n) \in {\bf R}^n \,:\,
u_1 + \cdots + u_n =1 \,, \, u_i \geq \epsilon \, \,\,
\hbox{for all $i$} \,\,\bigr\}. $$
Then $\,\, \bigcap_{i \in I } \bigl(\, \overline{{\cal N}(i)} \,\cap \,
T \, \bigr)  \,$ is nonempty if and only if $I \in \Delta_M$.
Thus $\, \bigl\{
\overline{{\cal N}(i)} \,\cap \, T \,  \bigr\}_{1 \leq i \leq r} \,$
is a cover of $T$ by polytopes. The nerve
of this cover equals $\Delta_M$. Using
Borsuk's Nerve Lemma,
we see that $\Delta_M$ is homotopy equivalent to $T$.
%\hfil\break\hbox{}\hfill
\Box




\vskip .75cm
\noindent {\bf    6. Extremal combinatorics}

\vglue .2cm

\noindent In this section we provide upper bounds for the Betti numbers of
an arbitrary monomial ideal, and we explore further connections
to extremal combinatorics.
Set  $\beta_i(n,r) \, := \, max \, \{ \beta_i(M)\}$ where the
maximum is taken over  all
monomial ideals $M$ with $r$ minimal generators in $k[x_1,\ldots,x_n]$.
It follows from Corollary 5.3 that  $\beta_i(n,r)$ is
attained by a monomial ideal $M$ which is generic.
We may assume that $M$ is Artinian, by the
following easy lemma:

\proclaim Lemma 6.1.
Let $\,M \, = \, \langle m_1,m_2,\ldots,m_r \rangle \,$ be a
generic monomial ideal where $\,m_1 \, =\,
x_1^{i_1} x_2^{i_2} \cdots x_n^{i_n} \,$
and $i_1 &gt; deg_{x_1}(m_j)$ for $j \geq 2$.
If $\,M' \, = \, \langle x_1^{i_1},m_2,\ldots,m_r \rangle \,$
then the Scarf complex $\,\Delta_M \,$ is a subcomplex of
the Scarf complex $\,\Delta_{M'} $.


\proclaim Corollary 6.2.
$\beta_i(n,r)$ equals the maximal number of $i$-faces of any Scarf complex
$\Delta_M$, where $M$ runs over all Artinian
generic monomial ideals $M$ with $r$ generators
in $n$ variables.

\noindent {\sl Proof: }
Apply Lemma 6.1 repeatedly until all variables appear to some power.
Take the resulting generic Artinian monomial ideal $M$
and apply Corollary 3.3 (1).
\Box

Each Scarf complex $\Delta_M$ considered in Corollary 6.2 is
the boundary of a simplicial $n$-polytope with
at least one facet removed, by Corollary 5.5.
The {\it Upper Bound Theorem for Convex Polytopes}
(cf.~[Zi, Thm.~8.23]) implies the following result:

\proclaim  Theorem~6.3. The Betti numbers of monomial
ideals satisfy the inequalities of the Upper Bound Theorem for
Convex Polytopes.
More precisely, if
 $c_{i}(n,r)$ denotes the number of $i$-dimensional faces of
the  cyclic $n$-polytope with $r$ vertices, then
$$  \eqalign{ \beta_{i}(n,r) \quad &amp; \leq \quad c_{i}(n,r)
\qquad \qquad \hbox{for $1 \leq i \leq n-2,$} \cr
\hbox{and} \,\,\, \quad  \beta_{n-1}(n,r) \quad &amp; \leq
\quad c_{n-1}(n,r) -1 . }  $$

An explicit formula for $ c_{i}(n,r)$
is given in [Zi, \S 8]. For instance,
$ c_1(3,r) =  3r-6  , \,
   c_2(3,r)  = 2r-4\,\,$ and $ \,
 c_1(4,r) = { r \choose 2 } ,\,
c_2(4,r)  = r (r - 3) , \,
c_3(4,r)  =  r (r-3) /2  $.
For $n\le 3$ all simplicial polytopes with $r$ vertices
have the same $f$-vector, so
the inequalities in Theorem~6.3 are
equalities.
The results in [Ag] show that the inequalities  can be
equalities for $n=4,r\le 12$, but they are always strict inequalities for
$n=4,r=13.$ Agnarson proved that
 $\,\beta_1 (4,13) = 77$ while $\,c_1(4,13) = 78$;
this also implies $ \,\beta_2(4,13) &lt;  c_2(4,13) \,$ and
$\,\beta_3(4,13) &lt;  c_3(4,13) -1 \,$ by the Euler and
Dehn-Sommerville equations.

We next relate Scarf complexes
to the dimension theory of partially ordered sets (see [Tr]).
Recall that the {\it order dimension} $odim({\cal P})$
of a finite poset ${\cal P}$ is the
smallest number $s$ of linear extensions $L_1,\ldots,L_s$ of ${\cal P}$
such that $\,L_1 \cap \dots \cap L_s \,= \,{\cal P} $.
If $\Delta$ is a  simplicial complex then  $odim(\Delta)$
denotes the order dimension of its face poset.
It is well-known that $\, odim(\Delta) \geq dim(\Delta) + 1$.
The case of equality is of special interest for us:

\proclaim Theorem 6.4.
\item{(a)} A simplicial complex $\Delta$ satisfies
$\,odim(\Delta) \leq n \,$ if and only if $\Delta$
is a subcomplex of the Scarf complex $\Delta_M$
for some generic monomial ideal $M$ in $k[x_1,\ldots,x_n]$.
\item{(b)} Let $\Delta $ be a triangulation of
the $n$-ball whose boundary equals the boundary of an $(n-1)$-simplex.
Then $\,odim(\Delta)= n \, $ if and only if
$\Delta$ equals the Scarf complex $\Delta_M$ of a generic Artinian monomial
ideal $M$ in $k[x_1,\ldots,x_n]$.

\noindent {\sl Proof: }
The if-direction in both (a) and (b) is seen as follows:
For $i=1,\ldots,n \,$ let $\, L_i$ denote the
linear extension of the face poset of $\Delta_M$ defined by
$\,\, \Delta_M \rightarrow {\bf R}, \,\, I \,\mapsto \,deg_{x_i}(m_I)
+ \epsilon {|I|} \,$, where $\epsilon $ is a small positive real.
The face poset of $\Delta_M$ coincides with   $\,L_1 \cap \dots \cap L_n$.

We next prove the only-if direction in (a).
Let $\Delta$ be a simplicial complex on $\{1,\ldots,r\}$
of order dimension at most $n$. Fix an embedding of
posets $\,\phi : \Delta \rightarrow {\bf N}^n \,$ such that
each coordinate of $\phi$ is a linear extension of $\Delta$.
We define the monomial ideal
$\, M \, = \, \langle m_1, m_2, \ldots,m_r \rangle \,$
where $\,m_i \, := \, {\bf x}^{\phi( \{ i \} )} $.
Let $I$ be any face of $\Delta$.  Note that
$\,m_I = lcm( m_i : i\in I)\,$ divides ${\bf x}^{\phi(I)}$.
We must show that
$I$ is a face of $\Delta_M$. Suppose not. Then there
exists a subset $J $ of $\{1,\ldots,r\}$
with $I \not= J$ but $m_I = m_J $.
If $J$ is not a subset of $I$ then
pick any $\,j \in J \backslash I $.
Then  $m_j = {\bf x}^{\phi({j})}$ does not divide
${\bf x}^{\phi(I)}$ (since $\phi$ is a poset embedding),
but $m_j$ does divide $m_I = m_J$, a contradiction.
If $J$ is a subset of $I$ then
$J$ is a proper face of $I$ in $\Delta$.
In this case we pick any $\,i \in I \backslash J $.
Now  $m_i$ does not divide
${\bf x}^{\phi(J)}$ (since $\phi$ is a poset embedding),
but $m_i$ does divide $m_I = m_J$, a contradiction.

We finally prove only-if in (b).
By part (a) there is a generic monomial ideal $M$
such that $\Delta$ is a subcomplex of $\Delta_{M}$.
We may assume that $\Delta $ and $\Delta_{M}$
have the same vertices. Applying Lemma 6.1
to the vertex labels of the $(n-1)$-simplex triangulated
by $\Delta$, we may also assume that $M$ is Artinian.
Both $\Delta$ and $\Delta_M$ are triangulations
of the same $(n-1)$-simplex and $\Delta \subseteq \Delta_M$.
Hence $\Delta = \Delta_M$ . \Box

\proclaim Corollary 6.5.
 $\beta_{i-1}(n,r)$ equals
the largest cardinality of a family ${\cal F}$
of $i$-sets in $\{1,\ldots,r\}$ such that
the simplicial complex spanned by ${\cal F}$
has order dimension $n$.

It was shown in [Sp] (see also Theorem 2.13 in [Tr, \S 7]) that
the complete graph on $r$ vertices has order dimension at least
$\, 2 + log_2 \bigl( log_2 ( r-1 ) \bigr) $.
Therefore  $$ \beta_1 (n,r) \ \leq \ { r \choose 2 } - 1 \quad \hbox{ for }
r \gg n \ . \eqno (6.1) $$

A central topic in discrete geometry
is the {\sl Steinitz Problem} of characterizing
the face lattices of  all convex polytopes.
While this problem has a beautiful solution
due to Steinitz in dimension $3\,$ [Zi, Theorem 4.1],
recent work of Richter-Gebert [Ri] shows that
the Steinitz Problem for $4$-dimensional polytopes
is essentially equivalent to classifying all semialgebraic
varieties (and hence intractible).
We propose the following variant for monomial ideals:

\item{(a)}
Classify all simplicial complexes which are Scarf
complexes of generic (Artinian) monomial ideals
with $r$ minimal generators in $k[x_1,\ldots,x_n]$.
\item{(b)} $ \!$
Classify all triangulations of the $(n \! - \! 1)$-simplex
whose face poset has order dimension~$n$.

\vskip .1cm

Theorem 6.4 implies that (a) and (b) are equivalent.
This realizability problem is trivial for $n \leq 2$ variables.
In three variables it is nontrivial but
solved by a theorem of Schnyder (see [Tr]):
for any triangulation  $\Delta$ of a triangle
there exists a generic Artinian monomial ideal
$M \subset k[x,y,z]$ such that $\Delta = \Delta_M$.
The analogous result does not hold for $n=4$:

\vskip .1cm

\proclaim Theorem 6.6.
There exists a triangulation of the tetrahedron
with seven vertices which is not the Scarf complex
of any monomial ideal in four variables.

For the proof
we need one lemma.
Let $\Delta$ be any simplicial complex on
$\{1,\ldots,n, \ldots,r \}$
which is a triangulation of the $(n \!- \!1)$-simplex
$\{1,\ldots,n\}$.
A {\it labeling of $\Delta$} is a family of bijections
$\,\bigl\{ \,\phi_I \,: \, I  \rightarrow
\{x_1,\ldots,x_n\}  \bigr\}_{I \,
{\rm facet} \,{\rm of} \,\Delta }\,$ which satisfies the following two axioms:
\item{(A)} If $I$ is a facet of $\Delta \,$ and
$\, i \in I \,\cap \,\{1,\ldots,n\}$ then
$\phi_I (i) = x_i$.
\item{(B)}
If $\,I\,$ and $\,J \,$ are facets of $\Delta$
which share a common ridge, i.e.~$ I \cap J$ has
cardinality $n-1$, then  $\,\{ \,j \in I \cap  J \,: \,
\phi_I (j) \, =\,\phi_{J'} (j)  \}\,$
has cardinality $n-2$.

\proclaim Lemma 6.7.
The Scarf complex $\Delta_M$ of any
generic artinian monomial ideal $M$ possesses a
labeling $\phi^M$. We call the labelings
of the form $\phi^M$ {\it realizable}.

\noindent {\sl Proof:}
The labeling $\phi^M = \{ \phi^M_I \}_{I \, {\rm facet}}$
of $\Delta_M$ is defined as follows:
If $I $ is a facet of $\Delta_M$ and $j \in I $
then $\,\phi^M_I (j) \,$ is the unique variable
missing in $\,m_I /m_j $. The map
$\,\phi^M_I  : I \rightarrow \{x_1,\ldots,x_n\} \,$ is
a bijection, and it is straightforward to check the axioms (A) and (B).
\Box

\noindent {\sl Proof of Theorem 6.6: } Consider the following
triangulation of a tetrahedron $1234$:
$$ \Delta \,\, = \,\, \bigl\{  1237, 1245, 1256, 1267, 1347,
1457, 1567, 2345, 2356, 2367, 3456, 3467, 4567  \bigr\}.  $$
The complex $\Delta$ is the boundary of the
cyclic polytope $C_4(7) $ minus the facet $1234$.

By Lemma 6.7 it suffices to prove
that $\Delta$ does not admit any labeling.
Suppose on the contrary that $\Delta$ possesses a labeling.
Writing $a,b,c,d$ for the four variables, the following labels are
forced by the axioms:
$$
\vcenter{\halign{
&amp;\hfil$#$\hfil\cr
\left[\matrix{ 2 \, 3 \, 4 \, 5 \cr b \, c \, d \, a \cr}\right]
&amp;
\longrightarrow
&amp;
\left[\matrix{ 3 \, 4 \, 5 \, 6 \cr c \, d \, b \, a \cr}\right]
&amp;
\longrightarrow
&amp;
\left[\matrix{ 3 \, 4 \, 6 \, 7 \cr c \, d \, b \, a \cr}\right]
\cr
&amp; &amp; &amp; \searrow &amp; \downarrow \cr
&amp; &amp; &amp; &amp;
\left[\matrix{ 4 \, 5 \, 6 \, 7 \cr d \, b \, c \, a \cr}\right]
&amp;
\longrightarrow
&amp;
\left[\matrix{ 1 \, 5 \, 6 \, 7 \cr a \, b \, c \, d \cr}\right]
\cr
}}
$$
$2345$ is labeled by axiom (A), and $3456$ and $3467$ successively by axioms
(A) and the ``ridge axiom'' (B). These last two tetrahedra each allow two
labelings of $4567$; the one shown is the common allowable labeling,
forcing the labeling shown on $1567$.


On the other hand, the following labels are also forced:
$$
\vcenter{\halign{
&amp; $#$ \cr
\left[\matrix{ 1 \, 2 \, 3 \, 7 \cr a \, b \, c \, d \cr}\right]
&amp;
\longrightarrow
&amp;
\left[\matrix{ 1 \, 2 \, 6 \, 7 \cr a \, b \, d \, c \cr}\right]
\cr
}}
$$
Now, there is a contradiction to axiom (B) in the labelings
of $1267$ and $1567$. \Box

\vskip 1cm

\noindent{\bf Acknowledgments.} We are  grateful to H. Scarf for
inspiring discussions during his visit to Berkeley in April 1996;
they got us started on this project. Many thanks to G. Ziegler
for helpful suggestions on Section~6 and to
 D. Eisenbud for suggestions on the exposition.
All authors are partially supported by the National Science Foundation.
I. Peeva and B. Sturmfels are partially supported
by the David and Lucile Packard Foundation.

\vfil\break

{\baselineskip = 12pt

\centerline{\bf References}

\vskip .1cm
{

\item{[Ag]} G.~Agnarsson: On the number of outside corners
of monomial ideals, {\sl J.~Pure and Applied Algebra},
{\bf 117} (1997) 3--22.

\item{[Av]} L. Avramov: Obstructions to the existence of multiplicative
structures on minimal free resolutions,
{\sl American J. Math.} {\bf 103} (1981) 1--31.

\item{[BH]} W.~Bruns and J.~Herzog: Semigroup rings and simplicial complexes,
preprint, to appear in {\sl J. Pure  Appl. Algebra}.

\item{[BLSWZ]} A.~Bj\"orner, M.~Las Vergnas,
B.~Sturmfels, N.~White, G.~Ziegler:
{\sl Oriented Matroids}, Cambridge University Press, 1993.

\item{[BW]} A. Bj\"orner and M. Wachs:
A.~Bj\"orner and M.~Wachs:
 Shellable nonpure complexes and posets, I.
 {\sl Trans. Amer. Math. Soc.} {\bf 348} (1996) 1299-1327.

 \item{[Ei]} D. Eisenbud:
{\sl Introduction to Commutative Algebra with a View towards
Algebraic Geometry},
Springer Verlag, New York, 1995.

\item{[Ri]} J.~Richter-Gebert:
{\sl Realization Spaces of Polytopes},
Lecture Notes in Mathematics {\bf 1643}, Springer, Berlin, 1996.

\item{[Ho]} M. Hochster:
Cohen-Macaulay rings, combinatorics and simplicial complexes,
in {\sl Ring Theory II}
(B.R.~McDonald and R.~Morris, eds.),
Lecture Notes in Pure and Appl.~Math., No.~26,
Dekker, New York, (1977) 171--223.

\item{[Ku]} A. Kustin: The minimal resolution of a codimension four
almost complete intersection is a DG-algebra,
{\sl J.~Algebra}
{\bf 168} (1994) 371-399.

 \item{[Ly]} G. Lyubeznik:
A new explicit finite free resolution of ideals generated by monomials
in an $R$-sequence,
{\sl J.~Pure  Appl. Algebra}
{\bf 51} (1988) 193-195.

\item{[PS]} I.~Peeva and B.~Sturmfels:
Generic lattice ideals,
preprint, (1997).

\item{[Sc]} H. Scarf: {\sl The Computation of Economic Equilibria},
Cowles Foundation Monograph {\bf 24}, Yale University Press, 1973.

\item{[Sp]} J. Spencer:
Minimal scrambling sets of simple orders,
{\sl Acta Math.~Acad.~Scient.~Hungaricae}
{\bf 22} (1971) 349--353.


\item{[St]} R.~Stanley:
{\sl Combinatorics and Commutative Algebra}, Birkh\"auser, Boston, 1996.

\item{[Tr]} W.~Trotter:
{\sl Combinatorics and Partially Ordered Sets. Dimension Theory},
The Johns Hopkins University Press, Baltimore, 1992.

\item{[Zi]} G. Ziegler:
{\sl Lectures on Polytopes}, Springer Verlag, New York, 1994.

}


\vskip .8cm

 Dave Bayer, Department of Mathematics,
Barnard College, Columbia University,
New York, NY 10027, USA,
{\tt bayer@math.columbia.edu}.

\vskip ,1cm

Irena Peeva,
2-277 Department of Mathematics,
Massachusetts Institut of Technology,
Cambridge, MA 02139, USA,
{\tt irena@math.mit.edu}.

\vskip ,1cm

 Bernd Sturmfels,
Department of Mathematics,
University of California,
Berkeley, CA 94720, USA,
{\tt bernd@math.berkeley.edu}.
}
\bye
</pre></body></html>