ORDER COMPLEXES OF NONCOMPLEMENTED LATTICES ARE NONEVASIVE

DMITRY N. KOZLOV

Abstract. We reprove and generalize in a combinatorial way the result of A. Björner, [Bj81, Theorem 3.3], that order complexes of noncomplemented lattices are contractible, namely by showing that these simplicial complexes are in fact nonevasive, in particular collapsible.

1. Introduction

The study of topological properties of noncomplemented lattices may be said to have been trigged off by a paper of H.H. Crapo, [Cr]. Namely, as a trivial corollary of his celebrated complementation formula [Cr, Theorem 3], one can derive that the Möbius function of a noncomplemented lattice is zero. On the other hand, the reduced Euler characteristic of an order complex of a poset, see Definition 2.1, is equal to the Möbius function evaluated on that poset. Hence converting Crapo’s result into algebraic topology language gives: the reduced Euler characteristic of the order complex of a noncomplemented lattice is zero.

This was later strengthened by K. Baclawski, who showed in [Ba, Corollary 6.3] that a finite noncomplemented lattice is ℤ-acyclic (here and in the rest of the note we often identify the poset itself with its order complex). However, Baclawski’s proof made use of the Leray spectral sequence in an intricate way and was far from being combinatorial.

A further improvement was made by A. Björner, see [Bj81, Theorem 3.3], where he succeeded to show that a noncomplemented lattice is contractible. Also this proof used heavy topology machinery, such as Nerve Lemma. Later in the joint paper of A. Björner and J.W. Walker a more precise result, known as homotopy complementation formula, [BW, Theorem 1.1], was given, enlightening the subject considerably.

The purpose of this paper is to explain the phenomena discovered in [Bj81] in a purely combinatorial way. Namely, we shall prove that the simplicial complex associated to a noncomplemented lattice is nonevasive, in particular collapsible.

The above mentioned result of A. Björner combined with a theorem that can be found in [Co], allowed one to conclude that order complexes of noncomplemented lattices can be reduced to a point by a sequence of collapses and anticollapses. The new fact, which can be retrieved from the result that we prove in this note, is that actually this reduction can be performed avoiding anticollapses.

Date: April 29, 1997.

The author was supported by the Swedish Science Council grant M-PD 11292-303.

2. The theorem

Throughout the rest of this note the symbol Δ will denote an abstract simplicial complex, that is, a subset of the set 2^{[n]} such that all one-element subsets of [n] = {1, …, n} lie in Δ and if both X ∈ Δ and Y ⊂ X then Y ∈ Δ. We will adapt the usual notions of the theory of abstract simplicial complexes, such as lk_{Δ}(σ), dl_{Δ}(σ), where σ ∈ Δ. For their description see for example [Bj95, (9.9)].

Let P be a finite partially ordered set, shortly poset. We say that P is bounded if it contains largest and smallest elements, which we denote ˆ1 and ˆ0. All the posets in this note are finite and bounded. We write P̄ = P \ {ˆ0, ˆ1}.

The main objective of this paper is to study topological objects associated to posets, as given by the following definition.

Definition 2.1. The order complex Δ(P) of a poset P is the simplicial complex on the vertex set P whose k-faces are the k-chains in P.

The symbol L will always denote a finite bounded lattice. For x ∈ L we write Co_{L}(x) or simply Co(x) for the set of complements of x, i.e. the set {y ∈ L | x∧y = ˆ0 and x ∨ y = ˆ1}.

Definition 2.2. A simplicial complex Δ is called collapsible if it can be reduced to a single point by a sequence of elementary collapse steps. An elementary collapse step is a replacement of Δ by another simplicial complex Δ′ = Δ \ {σ, τ}, where σ, τ ∈ Δ and σ is a proper face of exactly one simplex, namely τ.

See for example [Bj95, Section 11] for a survey of main results on collapsibility.

Definition 2.3. We say that a simplicial complex Δ on a finite number of vertices is nonevasive if either Δ consists of only one vertex or there exists a vertex x ∈ Δ such that both dl_{Δ}(x) and lk_{Δ}(x) are nonevasive.

There exist several equivalent definitions of nonevasive simplicial complexes; the one above is taken from [Bj95, (11.1)]. Originally nonevasive complexes were defined by Kahn, Saks and Sturtevant in [KSS], in order to model the notion of argument complexity. A good survey on the properties of nonevasiveness can be also found there. For example it is proved in [KSS, Proposition 1] that nonevasiveness implies collapsibilibity and that the implication is strict.

Now we present the main theorem of this note.

Theorem 2.4. Let L be a finite lattice. Let x ∈ L̄ and let P = L \ Co(x). Then Δ(P̄) is nonevasive, in particular it is collapsible.

Note. The result of Theorem 2.4 can be translated to algorithmic language in the following way.

Let L be a finite lattice, x ∈ L̄, P = L \ Co_{L}(x). Assume A is a subset of P̄ which is not known in advance. One is allowed to ask questions of type: ”Is y in A? ”, where y ∈ P̄. Then there exists a strategy which in at most |P̄| − 1 questions determines whether the set A is a chain in P̄.

See [KSS, Section 3] for more detailed description of the interplay of topological and algorithmic properties of (non-)evasiveness.

Proof of Theorem 2.4. We use induction on the number of elements in the poset P̄. Since x ∈ P̄, we know that Δ(P̄) is not empty. Futhermore, if P̄ consists of only one element then Δ(P̄) is a simplicial complex consisting of only one point and hence is nonevasive by Definition 2.3.

In order to show that Δ(P̄) is nonevasive we shall find a suitable atom (or a coatom) y ∈ P for which we shall prove the following two claims.

Claim 1. P \ {y} is obtained from some lattice by taking away the complements of a certain element.

Claim 2. P_{≥y} (respectively P_{≤y}, when y is a coatom) is obtained from some lattice by taking away the complements of some element.

To conclude the result by induction we make use of the identities Δ( \overline{P_{≥y}}) = lk_{Δ(P̄)}(y), if y is an atom, and Δ( \overline{P \ \{y\}}) = dl_{Δ(P̄)}(y).

Note. In the rest of the proof we will always consider the case when y is an atom. The case where, y is a coatom, is identical once the lattice is turned upside down.

We divide the main part of the proof into two cases, depending on the choice of y. Case 1. There exists y ∈ P such that

1. y is an atom (or a coatom) of P;

2. y ≰ x (respectively x ≰ y);

3. y ∉ Co_{L}(x).

Proof of Claim 1. Since y is an atom L′ = L \ {y} is a lattice. Also it is clear that x ∈ L′.

If z ∈ Co_{L′}(x) then x ∨ z = ˆ1 and x ∧ z = ˆ0 in L′. However, the identity x ∧ z = y is impossible in L, since then it would imply y ≤ x which we assumed to be false. Hence x ∧ z = ˆ0 in L and so z ∈ Co_{L}(x). Vice versa, if z ∈ Co_{L}(x) then obviously z ∈ Co_{L′}(x).

So we have shown that Co_{L}(x) = Co_{L′}(x) and hence P \ {y} = L′ \ Co_{L′}(x). Proof of Claim 2. The proof is illustrated on the picture below. L′ = [y, ˆ1] is a lattice since it is an interval in the lattice L. Let z = x ∨ y. Since

y is an atom and y ≰ x we know that x ∧ y = ˆ0. On the other hand y ∉ Co_{L}(x) so z ≠ ˆ1.

t ∧ z = y  ˆ1 = t ∨ z = t ∨ x a = x ∧ t x z = x ∨ y t  ˆ0 = x ∧ y

Let us now show that Co_{L′}(z) = Co_{L}(x)∩L′. It is obvious that Co_{L′}(z) ⊇ Co_{L}(x)∩ L′. Assume that there exists t ∈ Co_{L′}(z) \ Co_{L}(x). Then t ∧ z = y and t ∨ z = ˆ1. But

ˆ1 = t ∨ z = t ∨ (x ∨ y) = (t ∨ y) ∨ x = t ∨ x.

Let a = t ∧ x. Since t ∉ Co_{L}(x) and t ∨ x = ˆ1 we conclude that a ≠ ˆ0. Now clearly

z = x ∨ y ≥ x ≥ x ∧ t = a

and

t ≥ x ∧ t = a,

hence

y = t ∧ z ≥ a.

But y is an atom and a ≠ ˆ0, then a = y, which contradicts the assumption y ≰ x. Hence Co_{L′}(z) = Co_{L}(x) ∩ L′ and so P_{≥y} = L′ \ Co_{L′}(z).

Case 2. For every atom (coatom) y ∈ P either x ≥ y (respectively x ≤ y) or y ∈ Co(x).

Let Atom(P) (Coatom(P)) be the set of atoms (coatoms) of P. Let A = Atom(P)∩ Co(x), B = Coatom(P) ∩ Co(x). Assume A ≠ ∅. If a ∈ A, b ∈ Coatom(P) and b ≥ a then b ∈ B. Also, vice versa, if b ∈ B, a ∈ Atom(P) and b ≥ a then a ∈ A. Then it is an easy exercise to see that the poset L̄ splits into two disjoint (though not necessarily themselves connected) parts. The first one contains x and the second one, called S, contains A, B and all the elements comparable to the elements from these two sets. Then S ⊆ Co(x) and L′ = L \ S is still a lattice. Thus P = L′ \ Co_{L′}(x) and since L′ has fewer elements than L we are done by induction.

So we can assume that A = B = ∅, i.e. x is comparable to all atoms and coatoms of L and Co_{L}(x) = ∅ (so P = L).

We can assume that L has more than one element and hence choose an atom (coatom) y ∈ L, such that y ≠ x. We shall now prove Claims 1 and 2 for this element y.

Proof of Claims 1 and 2. P \ {y} (respectively P_{≥y}) is obviously a lattice and x belongs to P \ {y} (resp. P_{≥y}). Moreover Co_{P \{y}}(x) = Co_{P_{≥y}}(x) = ∅ since x is less than or equal to all coatoms of P \ {y} (resp. P_{≥y}).

Acknowledgements. I would like to thank E.-M. Feichtner and G.M. Ziegler for the careful reading of this note and A. Björner for pointing out the possibility of generalization of my original result.

References

[Ba] K. Baclawski, Galois connections and the Leray spectral sequence, Advances in Math. 25, (1977), pp. 191–215.

[Bj81] A. Björner, Homotopy type of posets and lattice complementation, J. Comb. Theory, Series A 30, (1981), pp. 90–100.

[Bj95] A. Björner, Topological Methods, in ”Handbook of Combinatorics” (eds. R. Graham, M. Grötschel and L. Lovász), North-Holland, 1995, pp. 1819–1872.

[BW] A. Björner, J.W. Walker, A homotopy complementation formula for partially ordered sets, European J. Combin. 4, (1983), pp. 11–19.

[Co] M.M. Cohen, A Course in Simple-Homotopy Type, Springer, New York, 1973.

[Cr] H.H. Crapo, The Möbius function of a lattice, J. Comb. Theory 1, (1966), pp. 126–131.

[KSS] J. Kahn, M. Saks and D. Sturtevant, A topological approach to evasiveness, Combinatorica 4, pp. 297–306, 1984.

[Mu] J.R. Munkres, Elements of Algebraic Topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984.

Department of Mathematics, Royal Institute of Technology, S-100 44, Stockholm, Sweden

Current address: Mathematical Science Research Institute, 1000 Centennial Drive, Berkeley, CA 94720, U.S.A. (until May 1, 1997)

  E-mail address: kozlov@math.kth.se