%----------------------------------cut here--------------------
%\magnification=\magstep1
%\baselineskip=15pt \lineskiplimit = 2pt \lineskip = 5 pt

\input amssym.def 
\hsize 5.9 true in 
\vsize 8.5 true in

\def \Box {\hbox{}\nobreak
 \vrule width 1.6mm height 1.6mm depth 0mm  \par \goodbreak \smallskip}

\def\CalL{{K}}%
\def\L{L}
\def\CalLprop{K^\circ}
\def\Lprop{L^\circ}
\def\Latom{L_{\rm atom}}
\def\Latomprop{L_{\rm atom}^\circ}
\def\Lprim{M}
\def\Lprimprop{M^\circ}
\def\Bool{{\cal B}}
\def\OD{{\rm{OrderDim}}}
\def\HD{{\rm{HomDim}}}
\def\N{{\bf N}}

\font \sm = cmr8

\vglue .3 cm
\centerline{\bf A HOMOLOGICAL LOWER BOUND FOR}
\centerline{\bf ORDER DIMENSION OF LATTICES}
\vglue  .7cm

\centerline{\bf Victor Reiner \qquad Volkmar Welker}

\vglue .2cm

%\centerline{Preprint version, July 1998}


\footnote{}{{\it \hglue -.6cm 1991 Mathematics Subject Classification:} 
{\rm 06A09, 06A06.}
\hfil \break {\it  Keywords and Phrases:} {\rm order dimension, lattices,
order complex, topology of posets}}

\vglue .4 cm

\noindent{\sm ABSTRACT:
We prove that if a finite lattice $\L$ has order dimension at most $d$,
then the homology of the order complex of its proper part $\Lprop$ vanishes
in dimensions $d-1$ and higher. In case $\L$ can be embedded as a
join-sublattice in $\N^d$ then $\Lprop$ actually has the homotopy type 
of a simplicial complex with $d$ vertices.}

\vglue .4 cm

\noindent{\bf 1. Introduction.}

\vglue  .4cm 

The {\it order dimension} $\OD(P)$ of a finite partially ordered set (poset for short) 
$P$ is defined to be
the smallest positive integer $d$ such that  $P$ is isomorphic
to an induced subposet of a Cartesian product of $d$ linear orders.
$\OD(P)$ turns out to be a very subtle and hard-to-compute
invariant of $P$, with an extensive literature (see [Tr]).

Topological invariants of posets have also been
studied extensively in the past few decades (see [Bj] for some
references).  Here the basic object of study
is the {\it order complex} of $P$, the abstract
simplicial complex having the elements of $P$ as its vertex set,
and the linearly ordered subsets of $P$ as its simplices.  In what follows,
we will abuse notation by making no distinction between the poset $P$,
its order complex, and the topological space which is the geometric
realization of this order complex.
Given a finite simplicial complex
$X$, define its {\it homological dimension} $\HD(X)$ as follows:

$$
\HD(X):={\rm min}\{e: \tilde{H}_i(X;k) = 0 \hbox{ for all } i > e,
                                     \hbox{ and for all fields }k \} 
$$

\noindent where here $\tilde{H}_i(X;k)$ refers to reduced simplicial homology
of $X$ with coefficients in $k$. In contrast to usual conventions, we 
set $\tilde{H}_{-1}(X;k) = k$ for arbitrary $X$. We remark that simplicial homology
is effectively computable [Mu, Chap. 1 \S 11], and hence so is $\HD(X)$.

Our main result, Theorem 1, connects these
two points of view in the case where the poset is a {\it lattice},
i.e. any two elements have a {\it meet} (greatest lower bound)
and a {\it join} (least upper bound).
There is some indication that the theory of order dimension
may be better behaved for posets which are {\it lattices} than
for arbitrary posets (see e.g. [Tr, p. 69]).
Our result gives a new lower bound for the order dimension
of a finite lattice $\L$, based on the topology of its {\it proper
part} $\Lprop$, that is, the poset obtained by removing the
bottom element $\hat{0}$ and top element $\hat{1}$ from $\L$. 

\noindent 
\proclaim Theorem~1. 
For a finite lattice $\L$,
$$
\OD(\L) \geq \HD(\Lprop)+2.
$$

The proof of Theorem 1 uses a lemma which is of interest
on its own.  The lemma gives a much stronger conclusion in the special
case that the lattice $\L$ can be embedded into $\N^d$ not just as an
induced subposet, but as a join-sublattice.

\vglue .25 cm
\noindent 
\proclaim Lemma~2. 
Let $\L$ be a join-sublattice of $\N^d$. 
Then $\Lprop$ has the homotopy type of a simplicial complex with
at most $d$ vertices.

\vglue .25cm
\noindent 

To place Theorem 1 in context, we compare it with a result
from the literature. The fact that the face lattice $\L$ of a
$d$-dimensional convex polytope has $\OD(\L) \allowbreak \geq d+1$
was first proven by Reuter [Re].
This is immediate from Theorem 1, since the proper part
of the face lattice of a $d$-dimensional polytope triangulates a $(d-1)$-sphere.
More generally, we have the following:

\proclaim Corollary~3.
Let $\L$ be the poset of faces of a regular cell complex whose
geometric realization is a $d$-dimensional pseudomanifold without
boundary, with $\hat{0}$ representing the empty face $\emptyset$
and an artificial top element $\hat{1}$ adjoined.
If $\L$ is a lattice, then $\OD(\L) \geq d+2$.

\vglue .25cm
\noindent
{\sl Proof.}

\vglue .1cm

\noindent In a $d$-dimensional pseudomanifold $M$ without boundary, the formal sum
of all the $d$-faces gives a non-trivial $d$-dimensional
homology cycle with ${\bf Z}/2$ coefficients [Mu, p. 262], so $\HD(M) = d$.
On the other hand, for a regular cell complex $M$,
the poset of proper faces triangulates the barycentric subdivision
of $M$. Therefore, $\HD(\Lprop) = \HD(M) = d$.  Apply Theorem~1.
\Box

\noindent
Note that the hypotheses of Corollary~3 are satisfied,
for example, by the face poset $\L$ of any triangulated manifold.


We also note that the assumption that $\L$ is a lattice cannot
be removed from Theorem~1, Lemma~2 or Corollary~3,
as illustrated by the following example.  Let $P$ be the poset
on $2n$ elements $x_1, y_1,\ldots,x_n,y_n$ with order relations
$x_i, y_i <_P x_j, y_j$ whenever $i < j$. Then $P$ is the poset
of non-empty faces in a well-known cell decomposition of the
$(n-1)$-sphere, and hence $\HD(P) = n-1$. 
However it is easy to check that $\OD(P) = 2$.
Nevertheless, one can obtain lower bounds on $\OD(P)$
for general posets $P$ by studying
the intersection lattice of a covering of $P$ by order ideals.
We do note make this explicit here, since the bounds seem to be too
week to yield any interesting consequence.

\vglue .25cm

As a historical point, Lemma 2 is related to some work on
minimal free resolutions of monomial ideals in
polynomial rings [GPW], and in fact this work motivated
its discovery, and subsequently Theorem 1.  In [GPW], it is shown that for
join-sublattices $\L$ of $\N^d$, the homology of $\Lprop$
measures, in a certain sense, the syzygies of a particular multidegree
in a minimal resolution of a monomial ideal related
to $L$.  The Hilbert syzygy theorem can then be used to
deduce the homological consequence of Lemma~2. Later the authors
found out that Theorem 1 had been conjectured in handwritten notes
[BEKZ] around 1986.

\vglue  .4cm
\noindent{\bf 2. Proofs of Theorem 1, Lemma 2.}

\vglue  .25cm
\noindent
We recall here the statement of Lemma 2.
 
\vglue .1cm
\noindent 
\proclaim Lemma~2. 
Let $\L$ be a join-sublattice of $\N^d$. 
Then $\Lprop$ has the homotopy type of a simplicial complex
with at most $d$ vertices.

\vglue .25cm
\noindent
{\sl Proof.}

\vglue .1cm

% Now we may assume $\L$ is an atomic join-sublattice of $\N^d$,
\noindent
By assumption a typical element of $\L$ is a $d$-tuple $n=(n_1,\ldots,n_d)$,
and the join operation in $\L$ is componentwise maximum.  We define
an order-preserving map $f:\Lprop \rightarrow \Bool^d$ where $\Bool^d$
is the Boolean algebra of subsets of $\{1,2,\ldots,d\}$ as follows:
If $t=(t_1,\ldots,t_d)$ is the top element of $\L$, then for
a typical element $n$ in $\Lprop$, let $f(n) = \{i:n_i = t_i\}$.
It is easy to see that $f$ is order-preserving, and in fact
join-preserving, i.e. $f(n \vee n') = f(n) \cup f(n')$.
The latter fact implies that $f$ induces a homotopy equivalence
onto its image $f(\Lprop) \subset \Bool^d$,
using Quillen's Fiber Lemma [Bj, (10.5)]:
Given any subset $S$ in the image $f(\Lprop)$, the inverse
image $f^{-1}(\Bool^d_{\subseteq S})$ has a greatest element,
namely the join of all of its elements taken in $L$. Here
$\Bool^d_{\subseteq S}$ denotes the set of all elements $T$ of
$\Bool^d$ such that $T \subseteq S$. 

As a consequence, we need only to analyze the homotopy type
of the image $f(\Lprop)$, which is either contractible or
the proper part of a join-sublattice in $\Bool^d$.
Applying the order anti-automorphism $S \mapsto [d]-S$ of
the Boolean algebra, we may instead assume it is the
proper part of a meet-sublattice $\CalL$ of $\Bool^d$.

For the meet-sublattice $\CalL$ of $\Bool^d$, let $\Delta_\CalL$
be the order ideal in $\Bool^d$ generated by the coatoms in 
$\CalL$. This $\Delta_\CalL$ is a simplicial complex with at
most $d$ vertices.  Then $\CalL$ is a meet-sublattice of the lattice of faces
of $\Delta_\CalL$ such that all maximal faces of $\Delta_\CalL$
are contained in $\CalL$. This implies that an element $A$ of the
face lattice of $\Delta_\CalL$ is a meet of maximal faces 
if and only if $A \in \CalL$ and $A$ is the meet of coatoms 
in $\CalL$. Thus the lattices of elements that are the meet
of coatoms coincide for $\CalL$ and the face lattice of
$\Delta_\CalL$. By [Bj, (10.12)], the proper part of a lattice
is homotopy equivalent to the proper part of the sublattice
of elements that are the meet of coatoms. Thus the proper parts of
the face lattice of $\Delta_\CalL$ and $\CalL$ are homotopy equivalent.
The fact that the order complex of the proper part of the face lattice of a 
simplicial complex is homeomorphic to the complex itself completes the proof.
\Box

\vglue .25cm

\noindent
{\sl Proof of Theorem 1.}

\vglue 0.1cm

\noindent We prove the assertion by induction on the number of atoms of $\L$.
If there is no atom then the proper part $\Lprop$ of $\L$ is empty and
$\L$ is a two-element chain whose order dimension is $1$. On the other hand
the homology of $\Lprop$ is concentrated in dimension $-1$. 

Assume that the number of atoms of $\L$ is greater than $0$.
We can assume without loss of generality that
$\L$ is an {\it atomic} lattice, i.e. every element in the
lattice is the join of atoms of $\L$, if we replace $\L$ by
the join-sublattice $\Latom$ generated by its atoms.
$\Latom$ is a sublattice of $\L$ having the same set of atoms,
with $\OD(\Latom) \leq \OD(L)$, and again by [Bj, (10.12)],
$\Lprop$ is homotopy equivalent to its proper part $\Latomprop$.
 
For our second reduction, we may now assume that $\L$ is atomic.
For $d := \OD(\L)$, there exists an
embedding $i: \L \hookrightarrow \N^d$ as an induced subposet
of $\N^d$.  We will now proceed to alter the embedding $i$ into
a new embedding $j$ having the following property:

\vglue.4cm

\noindent ($*$)~For every $x$ in $\L$, the element $j(x)$ is the
join in $\N^d$ of the $j(a)$ for atoms $a \leq x$ in $L$. 

\vglue.4cm
\noindent
Note that for the least element $\hat{0}$ of $\L$ this condition is vacuous.
Define the map $j: \L \rightarrow \N^d$ by
$$
j(x) = \displaystyle{\bigvee_{{{\rm atoms}~a} \atop {a \leq_\L x}} i(a)}
$$
where ``$\bigvee$'' denotes the join operation in $\N^d$.
To check that $j$ is still an embedding, it suffices to show both that
$j$ is order-preserving (which is clear), and that $j(x) \leq j(y)$
implies $x \leq y$.  To see the latter, note that any atom $a \leq_\L x$
satisfies
$$
i(a) \leq_{\N^d} j(x) \leq j(y) \leq_{\N^d} i(y),
$$
where the last inequality above follows from the fact that
$i(a) \leq_{\N^d} i(y)$ for any $a \leq_\L y$ because $i$ was
order-preserving.  Since $i$ was an embedding as an induced
subposet, we conclude $a \leq_\L y$ for any atom $a \leq_\L x$,
and this implies $x \leq_L y$ since $L$ is atomic.
By definition of $j$, the image $j(L)$ satisfies the
property ($*$).


We may now assume that the atomic lattice $\L$ is a subposet of $\N^d$ for which
the inclusion map $\L \hookrightarrow \N^d$ satisfies ($*$).
Let $\CalL$ be the subposet of $\N^d$ that is obtained from $\L$ by
adding all elements of $\N^d$ that are the join in $\N^d$ of atoms 
of $\L$. Then $\CalL$ is a easily seen to be a join-sublattice of
$\N^d$ which contains $\L$ as an induced subposet. 
In particular, Lemma  2 applies and demonstrates 
$\HD(\CalLprop) \leq d-2$. Note that a subcomplex of the $(d-1)$-simplex
is either contractible or of dimension at most $d-2$. In either case
all homology in dimension $d-1$ or higher vanishes.

Consider the long exact sequence in homology for the pair
$(\CalLprop,\Lprop)$, in which we suppress the arbitrary coefficient
ring for ease of notation: 

$$\cdots  \rightarrow \widetilde{H}_i(\CalLprop,\Lprop) \rightarrow \widetilde{H}_{i-1}(\Lprop)
\rightarrow \widetilde{H}_{i-1}(\CalLprop) \rightarrow \cdots$$

\noindent
Since $\widetilde{H}_i(\CalLprop)=0$ for $i \geq d-1$,
it suffices to show that $\widetilde{H}_i
(\CalLprop,\Lprop) = 0$ for $i \geq d$. We will show this by
induction on $|\CalL \setminus \L|$.

If $|\CalL \setminus \L| = 0$ then $\widetilde{H}_i(\CalLprop,\Lprop) =
0$ for all $i$. Assume $|\CalL \setminus \L| \geq 1$. 
Let $x$ be a minimal element of $\CalL \setminus \L$. 
We claim that $\Lprim := \L \cup \{ x \}$ is a lattice which
has the same set of atoms as $\L$, and satisfies the same hypotheses
as $\L$ did (atomic, embedded in $\N^d$, with property (*)).  The other
properties are immediate once we check that $\Lprim$ is a lattice.
Assume not, i.e., assume there exist two elements $u,v$ in $\Lprim$
with two distinct minimal upper bounds $p,q$.  Since $\L$ was a lattice,
we may assume without loss of generality that either $x=p$ or $x=u$.
If $x=p$, then the element $u \vee_{\N^d} v$ has
$$
u \vee_{\N^d} v \quad <_{\N^d} \quad  q, \, p(=x)
$$
and by minimality of $x$ in $\CalL \setminus \L$, it must lie
in $\L$ (and hence in $\Lprim$).
This contradicts the fact that $p,q$ were minimal upper bounds
for $u,v$ in $\Lprim$.  If $x=u$, then since $x$ lies in $\CalL$, we can
choose some $u_1,u_2$ in $\L$ with $u_1 \vee_{\N^d} u_2 = u (=x)$.
But then $u_1,u_2,v$ would have the two minimal upper bounds $p,q$ in
$\L$, contradicting the fact that $\L$ is a lattice.


Therefore  $\Lprim$ satisfies the same hypotheses as $\L$, so by
induction we may assume that 
$$
\widetilde{H}_i(\CalLprop,\Lprimprop) =0 \quad \hbox{ for } \quad i \geq d.
$$
Our final goal will be to show 
$\widetilde{H}_i(\Lprimprop, \Lprop) = 0$ for $i \geq d$.
Once this is achieved, the theorem follows from
the long exact sequence of the triple $(\CalLprop,\Lprimprop, \Lprop)$

$$\cdots \rightarrow \widetilde{H}_i(\Lprimprop,\Lprop)
\rightarrow \widetilde{H}_i(\CalLprop,\Lprop) \rightarrow
\widetilde{H}_i(\CalLprop,\Lprimprop)
\rightarrow \cdots$$

\noindent
which implies $\widetilde{H}_i(\CalLprop,\Lprop) = 0$ for $i \geq d$.
 
For any pair of finite simplicial complexes $(X,Y)$ with $Y$ a subcomplex
of $X$, one can form the quotient space $X/Y$, which identifies
$Y$ with a single point, and one has 
$\widetilde{H}_i(X/Y) = \widetilde{H}_i(X,Y)$.
Recall that we identify a partially ordered set with its
order complex, so we can consider the quotient $\Lprimprop/\Lprop$,
and it then suffices to show 
$\widetilde{H}_i(\Lprimprop/\Lprop) = 0$ for $i \geq d$.
We claim that the space $\Lprimprop/\Lprop$ is homotopy
equivalent to the suspension of the 
join of $\Lprop_{< x} := \{ y \in \Lprop~|~
y < x \}$ and $\Lprop_{> x} := \{ y \in \Lprop~|~y > x\}$.
To see this, note that the quotient $\Lprimprop/\Lprop$
can be identified with the image of the link of $x$ in
$\Lprop$ suspended over the two points $x$ and $\Lprop$ in $\Lprimprop/\Lprop$,
and the link of $x$ in $\Lprop$ is the join of $\Lprop_{< x}$ and
$\Lprop_{> x}$.  We now have two cases:

\vglue0.1cm
\noindent $\bullet$ Assume $\Lprop_{> x}$ is non-empty. Let $y,z$ be two elements
in $\Lprop_{> x}$. Then by construction all atoms of $\L$
below $x$ are also below $y$ and $z$. Since elements of $\L$ are
the join of the atoms below them it follows that the meet of
$y$ and $z$ in $\L$ is above $x$. But this implies that $\Lprop_{> x}$
has a minimal element -- the meet of all elements of $\Lprop_{ > x}$ 
in $\L$. But then $\Lprop_{> x}$ is contractible and thus so is
$\Lprimprop/\Lprop$. 

\vglue0.1cm
\noindent $\bullet$ Assume $\Lprop_{> x}$ is empty. Then $\Lprimprop/\Lprop$
is the suspension of $\Lprop_{< x}$. Again $\Lprop_{< x}$ is the proper
part of an atomic lattice embedded in $\N^d$ with property (*).
By atomicity of $L$, $x$ is not the largest element of $\L$, 
so there must be an atom of $\L$ not below $x$. Hence by the first induction
on the number of atoms, it follows that $\widetilde{H}_i(\Lprop_{<x})=0$
for all $i \geq d-1$. But then the homology of $\Lprimprop/\Lprop$
vanishes in dimension $d$ and higher by the suspension isomorphism. 

\vglue0.1cm
\noindent
In either case we deduce that the homology of $\Lprimprop/\Lprop$
vanishes in dimension $d$ and higher, as desired.
This completes the proof of both induction steps. \Box

%------------------------------------------------------------------------------
\vglue .5cm

\noindent{\bf Acknowledgments.}
The authors thank Irena Peeva for the initial conversations
leading to this work and to [GPW], and the Mathematisches 
Forschungsinstitut Oberwolfach for their hospitality.  They also thank
G\"unter M. Ziegler for helpful conversations and edits.
Vic Reiner was supported by a University of
Minnesota McKnight-Land Grant Fellowship and a Sloan Fellowship, and
Volkmar Welker was supported by Deutsche Forschungsgemeinschaft (DFG).

%------------------------------------------------------------------------------
\vskip .5cm 
\centerline {\bf References}

\vglue .5cm 
{ \frenchspacing

\item{[Bj]} A.~Bj\"orner:
Topological methods, in {\sl Handbook of Combinatorics}
(R. Graham, M. Gr\"otschel, L. Lov\'asz eds.),
p. 1819-1872, North-Holland, Amsterdam 1994.

\item{[GPW]} V. Gasharov, I. Peeva, V. Welker:
The role of the lcm lattice in resolutions of monomial ideals,
in preparation, 1998.

\item{[BEKZ]} L. Billera, P. Edelman, J. Kahn, G.M. Ziegler:
Unpublished notes, 1986.

\item{[Mu]} J.~Munkres: 
{\sl Elements of Algebraic Topology},
Benjamin/Cummings, Menlo Park CA, 1984.

\item{[Re]} K.~Reuter:
On the order dimension of convex polytopes,
{\sl Europ. J. Combin.} {\bf 11} (1990), 57-63. 

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

}

%--------------------------------------------------------------------

\vglue .5cm
Vic Reiner,
Department of Mathematics,
University of Minnesota,
Minneapolis, MN 55455,
USA,
{\tt reiner@math.umn.edu}.

\vglue .5cm
Volkmar Welker,
Fachbereich Mathematik, MA 7-1,
Technische Universit\"at Berlin,
10623 Berlin,
Germany,
{\tt welker@math.tu-berlin.de}.


\end






