A HOMOLOGICAL LOWER BOUND FOR ORDER DIMENSION OF LATTICES

Victor Reiner Volkmar Welker

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 L^{∘} vanishes in dimensions d − 1 and higher. In case L can be embedded as a joinsublattice in N^{d} then L^{∘} actually has the homotopy type of a simplicial complex with d vertices.

1. Introduction.

The order dimension OrderDim(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. OrderDim(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 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 homological dimension HomDim(X) as follows:

HomDim(X) := min{e : H̃_{i}(X; k) = 0 for all i > e, and for all fields k}

where here H̃_{i}(X; k) refers to reduced simplicial homology of X with coefficients in k. In contrast to usual conventions, we set H̃_{−1}(X; k) = k for arbitrary X. We remark that simplicial homology is effectively computable [Mu, Chap. 1 §11], and hence so is HomDim(X).

Our main result, Theorem 1, connects these two points of view in the case where the poset is a lattice, i.e. any two elements have a meet (greatest lower bound) and a join (least upper bound). There is some indication that the theory of order dimension may be better behaved for posets which are 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 proper part L^{∘}, that is, the poset obtained by removing the bottom element ˆ0 and top element ˆ1 from L.

Theorem 1. For a finite lattice L,

OrderDim(L) ≥ HomDim(L^{∘}) + 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.

Lemma 2. Let L be a join-sublattice of N^{d}. Then L^{∘} has the homotopy type of a simplicial complex with at most d vertices.

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 OrderDim(L) ≥ d + 1 was first proven

1991 Mathematics Subject Classification: 06A09, 06A06. Keywords and Phrases: order dimension, lattices, order complex, topology of posets 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:

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 ˆ0 representing the empty face ∅ and an artificial top element ˆ1 adjoined. If L is a lattice, then OrderDim(L) ≥ d + 2.

Proof. 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 Z/2 coefficients [Mu, p. 262], so HomDim(M) = d. On the other hand, for a regular cell complex M, the poset of proper faces triangulates the barycentric subdivision of M. Therefore, HomDim(L^{∘}) = HomDim(M) = d. Apply Theorem 1. 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}, …, 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 HomDim(P) = n − 1. However it is easy to check that OrderDim(P) = 2. Nevertheless, one can obtain lower bounds on OrderDim(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.

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 L^{∘} 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.

2. Proofs of Theorem 1, Lemma 2.

We recall here the statement of Lemma 2.

Lemma 2. Let L be a join-sublattice of N^{d}. Then L^{∘} has the homotopy type of a simplicial complex with at most d vertices.

Proof. By assumption a typical element of L is a d-tuple n = (n_{1}, …, n_{d}), and the join operation in L is componentwise maximum. We define an order-preserving map f : L^{∘} → B^{d} where B^{d} is the Boolean algebra of subsets of {1, 2, …, d} as follows: If t = (t_{1}, …, t_{d}) is the top element of L, then for a typical element n in L^{∘}, 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 ∨ n′) = f(n) ∪ f(n′). The latter fact implies that f induces a homotopy equivalence onto its image f(L^{∘}) ⊂ B^{d}, using Quillen’s Fiber Lemma [Bj, (10.5)]: Given any subset S in the image f(L^{∘}), the inverse image f^{−1}(B_{⊆S}^{d}) has a greatest element, namely the join of all of its elements taken in L. Here B_{⊆S}^{d} denotes the set of all elements T of B^{d} such that T ⊆ S.

As a consequence, we need only to analyze the homotopy type of the image f(L^{∘}), which is either contractible or the proper part of a join-sublattice in B^{d}. Applying the order antiautomorphism S ↦ [d] − S of the Boolean algebra, we may instead assume it is the proper part of a meet-sublattice K of B^{d}.

For the meet-sublattice K of B^{d}, let Δ_{K} be the order ideal in B^{d} generated by the coatoms in K. This Δ_{K} is a simplicial complex with at most d vertices. Then K is a meet-sublattice of the lattice of faces of Δ_{K} such that all maximal faces of Δ_{K} are contained in K. This implies that an element A of the face lattice of Δ_{K} is a meet of maximal faces if and only if A ∈ K and A is the meet of coatoms in K. Thus the lattices of elements that are the meet of coatoms coincide for K and the face lattice of Δ_{K}. 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 Δ_{K} and K 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.

Proof of Theorem 1. We prove the assertion by induction on the number of atoms of L. If there is no atom then the proper part L^{∘} of L is empty and L is a two-element chain whose order dimension is 1. On the other hand the homology of L^{∘} 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 atomic lattice, i.e. every element in the lattice is the join of atoms of L, if we replace L by the join-sublattice L_{atom} generated by its atoms. L_{atom} is a sublattice of L having the same set of atoms, with OrderDim(L_{atom}) ≤ OrderDim(L), and again by [Bj, (10.12)], L^{∘} is homotopy equivalent to its proper part L_{atom}^{∘}.

For our second reduction, we may now assume that L is atomic. For d := OrderDim(L), there exists an embedding i : L ↪ 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:

(∗) For every x in L, the element j(x) is the join in N^{d} of the j(a) for atoms a ≤ x in L.

Note that for the least element ˆ0 of L this condition is vacuous. Define the map j : L → N^{d} by

j(x) = ⋁_{{atoms a \atop a≤_{L}x}} i(a)

where “⋁” 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) ≤ j(y) implies x ≤ y. To see the latter, note that any atom a ≤_{L} x satisfies

i(a) ≤_{N^{d}} j(x) ≤ j(y) ≤_{N^{d}} i(y),

where the last inequality above follows from the fact that i(a) ≤_{N^{d}} i(y) for any a ≤_{L} y because i was order-preserving. Since i was an embedding as an induced subposet, we conclude a ≤_{L} y for any atom a ≤_{L} x, and this implies x ≤_{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 ↪ N^{d} satisfies (∗). Let K 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 K 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 HomDim(K^{∘}) ≤ 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 (K^{∘}, L^{∘}), in which we suppress the arbitrary coefficient ring for ease of notation:

⋯ → H̃_{i}(K^{∘}, L^{∘}) → H̃_{i−1}(L^{∘}) → H̃_{i−1}(K^{∘}) → ⋯

Since H̃_{i}(K^{∘}) = 0 for i ≥ d − 1, it suffices to show that H̃_{i}(K^{∘}, L^{∘}) = 0 for i ≥ d. We will show this by induction on |K \ L|.

If |K \ L| = 0 then H̃_{i}(K^{∘}, L^{∘}) = 0 for all i. Assume |K \ L| ≥ 1. Let x be a minimal element of K \ L. We claim that M := L ∪ {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 M is a lattice. Assume not, i.e., assume there exist two elements u, v in M 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 ∨_{N^{d}} v has

u ∨_{N^{d}} v <_{N^{d}} q, p(= x)

and by minimality of x in K \ L, it must lie in L (and hence in M). This contradicts the fact that p, q were minimal upper bounds for u, v in M. If x = u, then since x lies in K, we can choose some u_{1}, u_{2} in L with u_{1} ∨_{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 M satisfies the same hypotheses as L, so by induction we may assume that

H̃_{i}(K^{∘}, M^{∘}) = 0 for i ≥ d.

Our final goal will be to show H̃_{i}(M^{∘}, L^{∘}) = 0 for i ≥ d. Once this is achieved, the theorem follows from the long exact sequence of the triple (K^{∘}, M^{∘}, L^{∘})

⋯ → H̃_{i}(M^{∘}, L^{∘}) → H̃_{i}(K^{∘}, L^{∘}) → H̃_{i}(K^{∘}, M^{∘}) → ⋯

which implies H̃_{i}(K^{∘}, L^{∘}) = 0 for i ≥ 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 H̃_{i}(X/Y) = H̃_{i}(X, Y). Recall that we identify a partially ordered set with its order complex, so we can consider the quotient M^{∘}/L^{∘}, and it then suffices to show H̃_{i}(M^{∘}/L^{∘}) = 0 for i ≥ d. We claim that the space M^{∘}/L^{∘} is homotopy equivalent to the suspension of the join of L_{<x}^{∘} := {y ∈ L^{∘} | y < x} and L_{>x}^{∘} := {y ∈ L^{∘} | y > x}. To see this, note that the quotient M^{∘}/L^{∘} can be identified with the image of the link of x in L^{∘} suspended over the two points x and L^{∘} in M^{∘}/L^{∘}, and the link of x in L^{∘} is the join of L_{<x}^{∘} and L_{>x}^{∘}. We now have two cases:

• Assume L_{>x}^{∘} is non-empty. Let y, z be two elements in L_{>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 L_{>x}^{∘} has a minimal element – the meet of all elements of L_{>x}^{∘} in L. But then L_{>x}^{∘} is contractible and thus so is M^{∘}/L^{∘}.

• Assume L_{>x}^{∘} is empty. Then M^{∘}/L^{∘} is the suspension of L_{<x}^{∘}. Again L_{<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 H̃_{i}(L_{<x}^{∘}) = 0 for all i ≥ d − 1. But then the homology of M^{∘}/L^{∘} vanishes in dimension d and higher by the suspension isomorphism. In either case we deduce that the homology of M^{∘}/L^{∘} vanishes in dimension d and higher, as desired. This completes the proof of both induction steps.

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ünter 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).

References

[Bj] A. Björner: Topological methods, in Handbook of Combinatorics (R. Graham, M. Grötschel,

L. Lovász eds.), p. 1819-1872, North-Holland, Amsterdam 1994.

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

[BEKZ] L. Billera, P. Edelman, J. Kahn, G.M. Ziegler: Unpublished notes, 1986. [Mu] J. Munkres: Elements of Algebraic Topology, Benjamin/Cummings, Menlo Park CA, 1984.

[Re] K. Reuter: On the order dimension of convex polytopes, Europ. J. Combin. 11 (1990), 57-63.

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

Vic Reiner, Department of Mathematics, University of Minnesota, Minneapolis, MN 55455,

USA, reiner@math.umn.edu.

Volkmar Welker, Fachbereich Mathematik, MA 7-1, Technische Universität Berlin, 10623

Berlin, Germany, welker@math.tu-berlin.de.