Shellability of chessboard complexes. (English) Zbl 0828.57017
The chessboard complex \(\Delta_{m,n}\) is the abstract simplicial complex consisting of the set of all non-taking rook configurations (that is, no two rooks on the same row or column) on a fixed chessboard of arbitrary size \(m \times n\). This complex appears in several interesting combinatorial situations as described in the introduction to the paper. In the paper, the author considers not only rectangular chessboards but also chessboards of various other shapes. He obtains new results on vertex decomposability of such combinatorially defined simplicial complexes. Vertex decomposability implies strong consequences for a simplicial complex like shellability, which again implies that it is homotopy Cohen-Macaulay and (at least in principle) that a distinguished homology basis can be constructed.
Reviewer: V.L.Hansen (Lyngby)
Keywords:
chessboard complex; abstract simplicial complex; vertex decomposability; shellability; homotopy Cohen-Macaulay; homology basisReferences:
| [1] | Billera, L. J.; Provan, J. S., A decomposition property for simplicial complexes and its relation to diameters and shellings, Ann. NY Acad. Sci., 319, 82-85 (1979) · Zbl 0484.52006 · doi:10.1111/j.1749-6632.1979.tb32776.x |
| [2] | Björner, A., Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings, Advances in Math., 52, 173-212 (1984) · Zbl 0546.06001 · doi:10.1016/0001-8708(84)90021-5 |
| [3] | A. Björner,Homology and shellability of matroids and geometric lattices, inMatroid Applications (N. White, ed.), Cambridge University Press, 1992, pp. 226-283. · Zbl 0772.05027 |
| [4] | A. Björner,topological Methods, inHandbook of Combinatorics (R. Graham, M. Grötschel and L. Lovász, eds.), North-Holland, Amsterdam, to appear. |
| [5] | A. Björner, personal communication. |
| [6] | A. Björner, L. Lovász, S. T. Vrećica and R. T. Živaljević,Chessboard complexes and matching complexes, J. London Math. Soc., to appear. · Zbl 0790.57014 |
| [7] | Björner, A.; Wachs, M., On lexicographically shellable posets, Trans. Amer. Math. Soc., 277, 323-341 (1983) · Zbl 0514.05009 · doi:10.2307/1999359 |
| [8] | P. F. Garst,Cohen-Macaulay Complexes and Group Actions, Ph.D. Thesis, University of Wisconsin-Madison, 1979, 130 pp. |
| [9] | Klee, V.; Kleinschmidt, P., The d-step conjecture and its relatives, Math. Operations Research, 12, 718-755 (1987) · Zbl 0632.52007 · doi:10.1287/moor.12.4.718 |
| [10] | Lovász, L.; Plummer, M. D., Matching Theory (1986), Amsterdam: Akadémiai Kiadó, Budapest, and North-Holland, Amsterdam · Zbl 0618.05001 |
| [11] | Provan, J. S.; Billera, L. J., Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Operations Research, 5, 576-594 (1980) · Zbl 0457.52005 |
| [12] | Sarkaria, K. S., A generalized van Kampen-Flores theorem, Proc. Amer. Math. Soc., 111, 559-565 (1991) · Zbl 0722.57007 · doi:10.2307/2048349 |
| [13] | Vrećica, S. T.; Živaljević, R. T., The colored Tverberg’s problem and complexes of injective functions, J. Combinatorial Theory, Ser. A, 61, 309-318 (1992) · Zbl 0782.52003 · doi:10.1016/0097-3165(92)90028-S |
| [14] | Wachs, M. L.; Walker, J. W., On geometric semilattices, Order, 2, 367-385 (1986) · Zbl 0589.06005 · doi:10.1007/BF00367425 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
