Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.