Shellability of Chessboard Complexes.
Please always quote using this URN: urn:nbn:de:0297-zib-890
- The matchings in a complete bipartite graph form a simplicial complex, which in many cases has strong structural properties. We use an equivalent description as chessboard complexes: the complexes of all non-taking rook positions on chessboards of various shapes. In this paper we construct `certificate $k$-shapes' $\Sigma(m,n,k)$ such that if the shape $A$ contains some $\Sigma(m,n,k)$, then the $(k{-}1)$-skeleton of the chessboard complex $\Delta(A)$ is vertex decomposable in the sense of Provan & Billera. This covers, in particular, the case of rectangular chessboards $A=[m]{\times}[n]$, for which $\Delta(A)$ is vertex decomposable if $n\ge 2m{-}1$, and the $(\lfloor{m+n+1\over3}\rfloor{-}1)$-skeleton is vertex decomposable in general. The notion of vertex decomposability is a very convenient tool to prove shellability of such combinatorially defined simplicial complexes. We establish a relation between vertex decomposability and the CL-shellability technique (for posets) of Björner & Wachs.
Author: | Günter M. Ziegler |
---|---|
Document Type: | ZIB-Report |
Date of first Publication: | 1992/09/23 |
Series (Serial Number): | ZIB-Report (SC-92-19) |
ZIB-Reportnumber: | SC-92-19 |
Published in: | Appeared in: Israel J. Mathematics 87 (1994) pp. 97-110 |