\documentstyle[12pt]{amsart} \headheight=7pt \topmargin=14pt \textheight=574pt \textwidth=432pt \oddsidemargin=18pt \evensidemargin=18pt \input epsf.sty \sloppy \newcommand{\nl}{\newline} \newcommand{\lb}{\linebreak} \newcommand{\nlb}{\nolinebreak} \newcommand{\be}{\begin{enumerate}} \newcommand{\ee}{\end{enumerate}} \newcommand{\tbe}{(to be extended)} \newcommand{\pr}{{\bf Proof. }} \newcommand{\co}{{\cal C{\it o}}} \newcommand{\cl}{{\cal L}} \newtheorem{thm}{Theorem}[section] \newtheorem{df}[thm]{Definition} \newtheorem{lm}[thm]{Lemma} \newtheorem{crl}[thm]{Corollary} \newtheorem{prop}[thm]{Proposition} \newtheorem{conj}[thm]{Conjecture} \newtheorem{rem}[thm]{Remark} \newtheorem{prob}[thm]{Problem} \numberwithin{equation}{section} \begin{document} \title[Order complexes of noncomplemented lattices are nonevasive] {Order complexes of noncomplemented lattices\\are nonevasive} \author{Dmitry N. Kozlov} \date{\today} \thanks{The author was supported by the Swedish Science Council grant M-PD 11292-303.} \address {Department of Mathematics, Royal Institute of Technology, S-100 44, Stockholm, Sweden} \curraddr{Mathematical Science Research Institute, 1000 Centennial Drive, Berkeley, CA 94720, U.S.A. (until May 1, 1997)} \email{kozlov@@math.kth.se} \begin{abstract} We reprove and generalize in a combinatorial way the result of A.~Bj\"orner, \cite[Theorem 3.3]{Bj81}, that order complexes of noncomplemented lattices are contractible, namely by showing that these simplicial complexes are in fact nonevasive, in particular collapsible. \end{abstract} \maketitle \section{Introduction} The study of topological properties of noncomplemented lattices may be said to have been trigged off by a paper of H.H.~Crapo, \cite{Cr}. Namely, as a trivial corollary of his celebrated complementation formula \cite[Theorem 3]{Cr}, one can derive that the M\"obius function of a noncomplemented lattice is zero. On the other hand, the reduced Euler characteristic of an order complex of a poset, see Definition \ref{ocd}, is equal to the M\"obius function evaluated on that poset. Hence converting Crapo's result into algebraic topology language gives: {\it the reduced Euler characteristic of the order complex of a noncomplemented lattice is zero}. This was later strengthened by K.~Baclawski, who showed in \cite[Corollary 6.3]{Ba} that {\it a finite noncomplemented lattice is $\Bbb Z$-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\"orner, see \cite[Theorem 3.3]{Bj81}, where he succeeded to show that {\it a non\-complemented lattice is contractible.} Also this proof used heavy topology machinery, such as Nerve Lemma. Later in the joint paper of A.~Bj\"orner and J.W.~Walker a more precise result, known as homotopy complementation formula, \cite[Theorem 1.1]{BW}, was given, enlightening the subject considerably. The purpose of this paper is to explain the phenomena discovered in \cite{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\"orner combined with a theorem that can be found in \cite{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. \section{The theorem} Throughout the rest of this note the symbol $\Delta$ will denote an abstract simplicial complex, that is, a subset of the set $2^{[n]}$ such that all one-element subsets of $[n]=\{1,\dots,n\}$ lie in $\Delta$ and if both $X\in\Delta$ and $Y\subset X$ then $Y\in\Delta$. We will adapt the usual notions of the theory of abstract simplicial complexes, such as $\text{lk}_{\Delta}(\sigma), \text{dl}_\Delta(\sigma)$, where $\sigma\in\Delta$. For their description see for example \cite[(9.9)]{Bj95}. 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 $\hat 1$ and $\hat 0$. All the posets in this note are finite and bounded. We write $\bar P=P\setminus\{\hat 0,\hat 1\}$. The main objective of this paper is to study topological objects associated to posets, as given by the following definition. \begin{df} \label{ocd} The {\bf order complex} $\Delta(P)$ of a poset $P$ is the simplicial complex on the vertex set $P$ whose $k$-faces are the $k$-chains in $P$. \end{df} The symbol $\cl$ will always denote a finite bounded lattice. For $x\in\cl$ we write $\co_\cl(x)$ or simply $\co(x)$ for the set of complements of $x$, i.e. the set $\{y\in\cl\,|\,x\land y=\hat 0$ and $x\lor y=\hat 1\}$. \begin{df} A simplicial complex $\Delta$ is called {\bf collapsible} if it can be reduced to a single point by a sequence of elementary collapse steps. An {\bf elementary collapse step} is a replacement of $\Delta$ by another simplicial complex $\Delta'=\Delta\setminus\{\sigma,\tau\}$, where $\sigma,\tau\in\Delta$ and $\sigma$ is a proper face of exactly one simplex, namely $\tau$. \end{df} See for example \cite[Section 11]{Bj95} for a survey of main results on collapsibility. \begin{df} \label{nev} We say that a simplicial complex $\Delta$ on a finite number of vertices is {\bf nonevasive} if either $\Delta$ consists of only one vertex or there exists a vertex $x\in \Delta$ such that both dl$_\Delta(x)$ and lk$_\Delta (x)$ are nonevasive. \end{df} There exist several equivalent definitions of nonevasive simplicial complexes; the one above is taken from \cite[(11.1)]{Bj95}. Originally nonevasive complexes were defined by Kahn, Saks and Sturtevant in \cite{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 \cite[Proposition 1]{KSS} that nonevasiveness implies collapsibilibity and that the implication is strict. % %%%%% \section{The main theorem} % Now we present the main theorem of this note. \begin{thm} \label{main} Let $\cl$ be a finite lattice. Let $x\in \bar\cl$ and let $P=\cl\setminus\co(x)$. Then $\Delta(\bar P)$ is nonevasive, in particular it is collapsible. \end{thm} {\bf Note.} The result of Theorem \ref{main} can be translated to algorithmic language in the following way. Let $\cl$ be a finite lattice, $x\in\bar\cl$, $P=\cl\setminus\co_\cl(x)$. Assume $\cal A$ is a subset of $\bar P$ which is not known in advance. One is allowed to ask questions of type: "{\it Is $y$ in $\cal A$?\,}", where $y\in\bar P$. Then there exists a strategy which in at most $|\bar P|-1$ questions determines whether the set $\cal A$ is a chain in $\bar P$. See \cite[Section 3]{KSS} for more detailed description of the interplay of topological and algorithmic properties of (non-)evasiveness. \smallskip {\bf Proof of Theorem \ref{main}.} We use induction on the number of elements in the poset $\bar P$. Since $x\in \bar P$, we know that $\Delta(\bar P)$ is not empty. Futhermore, if $\bar P$ consists of only one element then $\Delta(\bar P)$ is a simplicial complex consisting of only one point and hence is nonevasive by Definition \ref{nev}. In order to show that $\Delta(\bar P)$ is nonevasive we shall find a suitable atom (or a coatom) $y\in P$ for which we shall prove the following two claims. \smallskip {\bf Claim 1.} {\it $P\setminus \{y\}$ is obtained from some lattice by taking away the complements of a certain element.} \smallskip {\bf Claim 2.} {\it $P_{\geq y}$ (respectively $P_{\leq 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 $\Delta(\,\overline{P_{\geq y}}\,)=\text{lk}_{\Delta(\bar P)} (y)$, if $y$ is an atom, and $\Delta(\,\overline{P\setminus\{y\}})=\text{dl}_{\Delta(\bar P)}(y)$. \smallskip {\bf 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$. \smallskip {\bf Case 1.} {\it There exists $y\in P$ such that \begin{enumerate} \item $y$ is an atom (or a coatom) of $P$; \item $y\not\leq x$ (respectively $x\not\leq y$); \item $y\notin\co_\cl(x)$. \end{enumerate} } \smallskip {\bf Proof of Claim 1.} Since $y$ is an atom $\cl'=\cl\setminus\{y\}$ is a lattice. Also it is clear that $x\in\cl'$. If $z\in\co_{\cl'}(x)$ then $x\lor z=\hat 1$ and $x\land z=\hat 0$ in $\cl'$. However, the identity $x\land z=y$ is impossible in $\cl$, since then it would imply $y\leq x$ which we assumed to be false. Hence $x\land z=\hat 0$ in $\cl$ and so $z\in\co_\cl(x)$. Vice versa, if $z\in\co_\cl(x)$ then obviously $z\in\co_{\cl'}(x)$. So we have shown that $\co_\cl(x)=\co_{\cl'}(x)$ and hence $P\setminus\{y\}=\cl'\setminus\co_{\cl'}(x)$. \smallskip {\bf Proof of Claim 2.} The proof is illustrated on the picture below. $\cl'=[y,\hat 1]$ is a lattice since it is an interval in the lattice $\cl$. Let $z=x\lor y$. Since $y$ is an atom and $y\not\leq x$ we know that $x\land y=\hat 0$. On the other hand $y\notin\co_{\cl}(x)$ so $z\neq \hat 1$. \begin{center} \input{pic1.tex} \end{center} Let us now show that $\co_{\cl'}(z)=\co_{\cl}(x)\cap \cl'$. It is obvious that $\co_{\cl'}(z)\supseteq\co_{\cl}(x)\cap \cl'$. Assume that there exists $t\in\co_{\cl'}(z)\setminus\co_{\cl}(x)$. Then $t\land z=y$ and $t\lor z=\hat 1$. But $$\hat 1=t\lor z=t\lor(x\lor y)=(t\lor y)\lor x=t\lor x.$$ Let $a=t\land x$. Since $t\notin\co_{\cl}(x)$ and $t\lor x=\hat 1$ we conclude that $a\neq \hat 0$. Now clearly $$z=x\lor y\geq x\geq x\land t=a$$ and $$t\geq x\land t=a,$$ hence $$y=t\land z\geq a.$$ But $y$ is an atom and $a\neq\hat 0$, then $a=y$, which contradicts the assumption $y\not\leq x$. Hence $\co_{\cl'}(z)=\co_{\cl}(x)\cap \cl'$ and so $P_{\geq y}=\cl'\setminus\co_{\cl'}(z)$. {\bf Case 2.} {\it For every atom (coatom) $y\in P$ either $x\geq y$ (respectively $x\leq y$) or $y\in\co(x)$.} Let Atom$(P)$ (Coatom$(P)$) be the set of atoms (coatoms) of $P$. Let $A=$ Atom$(P)\cap\co(x)$, $B=$ Coatom$(P)\cap\co(x)$. Assume $A\neq\emptyset$. If $a\in A$, $b\in$ Coatom$(P)$ and $b\geq a$ then $b\in B$. Also, vice versa, if $b\in B$, $a\in$ Atom$(P)$ and $b\geq a$ then $a\in A$. Then it is an easy exercise to see that the poset $\bar{\cal 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\subseteq\co(x)$ and $\cl'=\cl\setminus S$ is still a lattice. Thus $P=\cl'\setminus\co_{\cl'}(x)$ and since $\cl'$ has fewer elements than $\cl$ we are done by induction. So we can assume that $A=B=\emptyset$, i.e. $x$ is comparable to all atoms and coatoms of $\cl$ and $\co_\cl(x)=\emptyset$ (so $P=\cl$). We can assume that $\cl$ has more than one element and hence choose an atom (coatom) $y\in\cl$, such that $y\neq x$. We shall now prove Claims 1 and 2 for this element $y$. {\bf Proof of Claims 1 and 2.} $P\setminus\{y\}$ (respectively $P_{\geq y}$) is obviously a lattice and $x$ belongs to $P\setminus\{y\}$ (resp. $P_{\geq y}$). Moreover $\co_{P\setminus\{y\}}(x)=\co_{P_{\geq y}}(x)= \emptyset$ since $x$ is less than or equal to all coatoms of $P\setminus\{y\}$ (resp. $P_{\geq y}$). \qed {\bf Acknowledgements.} I would like to thank E.-M.~Feichtner and G.M.~Ziegler for the careful reading of this note and A.~Bj\"orner for pointing out the possibility of generalization of my original result. \begin{thebibliography}{KSSll} \bibitem[Ba]{Ba} K. Baclawski, {\em Galois connections and the Leray spectral sequence}, Advances in Math. {\bf 25}, (1977), pp. 191--215. \bibitem[Bj81]{Bj81} A. Bj\"orner, {\em Homotopy type of posets and lattice complementation,} J. Comb. Theory, Series A {\bf 30}, (1981), pp. 90--100. \bibitem[Bj95]{Bj95} A. Bj\"orner, {\em Topological Methods,} in "Handbook of Combinatorics" (eds. R. Graham, M. Gr\"otschel and L. Lov\'asz), North-Holland, 1995, pp. 1819--1872. \bibitem[BW]{BW} A. Bj\"orner, J.W. Walker, {\em A homotopy complementation formula for partially ordered sets,} European J. Combin. {\bf 4}, (1983), pp. 11--19. \bibitem[Co]{Co} M.M. Cohen, {\em A Course in Simple-Homotopy Type,} Springer, New York, 1973. \bibitem[Cr]{Cr} H.H.~Crapo, {\em The M\"obius function of a lattice,} J. Comb. Theory {\bf 1}, (1966), pp. 126--131. \bibitem[KSS]{KSS} J. Kahn, M. Saks and D. Sturtevant, {\em A topological approach to evasiveness,} Combinatorica {\bf 4}, pp. 297--306, 1984. \bibitem[Mu]{Mu} J.R. Munkres, {\em Elements of Algebraic Topology}, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. \end{thebibliography} \end{document}