Shellable Nonpure Complexes and Posets. I

Björner, Anders; Wachs, Michelle

doi:10.1090/S0002-9947-96-01534-6

Shellable Nonpure Complexes and Posets. I
HTML articles powered by AMS MathViewer

by Anders Björner and Michelle L. Wachs PDF

Trans. Amer. Math. Soc. 348 (1996), 1299-1327 Request permission

Abstract:

The concept of shellability of complexes is generalized by deleting the requirement of purity (i.e., that all maximal faces have the same dimension). The usefulness of this level of generality was suggested by certain examples coming from the theory of subspace arrangements. We develop several of the basic properties of the concept of nonpure shellability. Doubly indexed $f$-vectors and $h$-vectors are introduced, and the latter are shown to be nonnegative in the shellable case. Shellable complexes have the homotopy type of a wedge of spheres of various dimensions, and their Stanley-Reisner rings admit a combinatorially induced direct sum decomposition. The technique of lexicographic shellability for posets is similarly extended from pure posets (all maximal chains of the same length) to the general case. Several examples of nonpure lexicographically shellable posets are given, such as the $k$-equal partition lattice (the intersection lattice of the $k$-equal subspace arrangement) and the Tamari lattices of binary trees. This leads to simplified computation of Betti numbers for the $k$-equal arrangement. It also determines the homotopy type of intervals in a Tamari lattice and in the lattice of number partitions ordered by dominance, thus strengthening some known Möbius function formulas. The extension to regular CW complexes is briefly discussed and shown to be related to the concept of lexicographic shellability.

References

Kenneth Baclawski and Adriano M. Garsia, Combinatorial decompositions of a class of rings, Adv. in Math. 39 (1981), no. 2, 155–184. MR 609203, DOI 10.1016/0001-8708(81)90027-X
C. Berge, Principles of combinatorics, Mathematics in Science and Engineering, Vol. 72, Academic Press, New York-London, 1971. Translated from the French. MR 0270922
L.J. Billera and B. Sturmfels, Iterated fiber polytopes, Mathematika 41 (1994), 348–363.
Anders Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), no. 1, 159–183. MR 570784, DOI 10.1090/S0002-9947-1980-0570784-2
A. Björner, Posets, regular CW complexes and Bruhat order, European J. Combin. 5 (1984), no. 1, 7–16. MR 746039, DOI 10.1016/S0195-6698(84)80012-8
Anders Björner, Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings, Adv. in Math. 52 (1984), no. 3, 173–212. MR 744856, DOI 10.1016/0001-8708(84)90021-5
Anders Björner, The homology and shellability of matroids and geometric lattices, Matroid applications, Encyclopedia Math. Appl., vol. 40, Cambridge Univ. Press, Cambridge, 1992, pp. 226–283. MR 1165544, DOI 10.1017/CBO9780511662041.008
—, Subspace arrangements, First European Congress of Mathematics, Paris 1992 (A. Joseph et al., eds.), Progress in Math., vol. 119, Birkhäuser, 1994, pp. 321-370.
—, Topological Methods, Handbook of Combinatorics (R. Graham, M. Grötschel and L. Lovász, eds.), North-Holland, 1995, pp. 1819–1872.
—, Face numbers, Betti numbers and depth, in preparation.
Anders Björner and Gil Kalai, On $f$-vectors and homology, Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985) Ann. New York Acad. Sci., vol. 555, New York Acad. Sci., New York, 1989, pp. 63–80. MR 1018610, DOI 10.1111/j.1749-6632.1989.tb22438.x
Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler, Oriented matroids, Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge University Press, Cambridge, 1993. MR 1226888
Anders Björner and László Lovász, Linear decision trees, subspace arrangements and Möbius functions, J. Amer. Math. Soc. 7 (1994), no. 3, 677–706. MR 1243770, DOI 10.1090/S0894-0347-1994-1243770-0
A. Björner, L. Lovász and A. Yao, Linear decision trees: volume estimates and topological bounds, Proc. 24th ACM Symp. on Theory of Computing (May 1992), ACM Press, New York, 1992, pp. 170–177.
A. Björner and B. Sagan, Subspace arrangements of type $B_{n}$ and $D_{n}$, preprint 1994, J. Algebraic Combinatorics (to appear).
Anders Björner and Michelle Wachs, Bruhat order of Coxeter groups and shellability, Adv. in Math. 43 (1982), no. 1, 87–100. MR 644668, DOI 10.1016/0001-8708(82)90029-9
Anders Björner and Michelle Wachs, On lexicographically shellable posets, Trans. Amer. Math. Soc. 277 (1983), no. 1, 323–341. MR 690055, DOI 10.1090/S0002-9947-1983-0690055-6
Anders Björner and Michelle L. Wachs, Generalized quotients in Coxeter groups, Trans. Amer. Math. Soc. 308 (1988), no. 1, 1–37. MR 946427, DOI 10.1090/S0002-9947-1988-0946427-X
Anders Björner and Michelle L. Wachs, Permutation statistics and linear extensions of posets, J. Combin. Theory Ser. A 58 (1991), no. 1, 85–114. MR 1119703, DOI 10.1016/0097-3165(91)90075-R
Anders Björner and James W. Walker, A homotopy complementation formula for partially ordered sets, European J. Combin. 4 (1983), no. 1, 11–19. MR 694463, DOI 10.1016/S0195-6698(83)80003-1
A. Björner and V. Welker, The homology of “$k$-equal” manifolds and related partition lattices, Advances in Math. 110 (1995), 277–313.
K. Bogart, The Möbius function of the domination lattice, unpublished manuscript, 1972.
Thomas Brylawski, The lattice of integer partitions, Discrete Math. 6 (1973), 201–219. MR 325405, DOI 10.1016/0012-365X(73)90094-0
Manoj K. Chari, Steiner complexes, matroid ports, and shellability, J. Combin. Theory Ser. B 59 (1993), no. 1, 41–68. MR 1234382, DOI 10.1006/jctb.1993.1053
Adriano M. Garsia, Combinatorial methods in the theory of Cohen-Macaulay rings, Adv. in Math. 38 (1980), no. 3, 229–266. MR 597728, DOI 10.1016/0001-8708(80)90006-7
Curtis Greene, A class of lattices with Möbius function $\pm 1,0$, European J. Combin. 9 (1988), no. 3, 225–240. MR 947024, DOI 10.1016/S0195-6698(88)80013-1
Samuel Huang and Dov Tamari, Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law, J. Combinatorial Theory Ser. A 13 (1972), 7–13. MR 306064, DOI 10.1016/0097-3165(72)90003-9
Bernd Kind and Peter Kleinschmidt, Schälbare Cohen-Macauley-Komplexe und ihre Parametrisierung, Math. Z. 167 (1979), no. 2, 173–179 (German). MR 534824, DOI 10.1007/BF01215121
D.E. Knuth, Computer Musings: The associative law, or The anatomy of rotations in binary trees, Distinguished Lecture Series VII (Stanford, CA: University Video Communications, 1993), 68 minutes (videotape).
S. Linusson, Partitions with restricted block sizes, Möbius functions and the $k$-of-each problem, preprint 1994.
—, A class of lattices whose intervals are spherical or contractible, preprint, 1995.
P. McMullen, The maximum numbers of faces of a convex polytope, Mathematika 17 (1970), 179–184. MR 283691, DOI 10.1112/S0025579300002850
James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006
J.M. Pallo, Enumerating, ranking and unranking binary trees, Computer J. 29 (1986), 171–175.
J. Pallo, Some properties of the rotation lattice of binary trees, Comput. J. 31 (1988), no. 6, 564–565. MR 974656, DOI 10.1093/comjnl/31.6.564
J. M. Pallo, An algorithm to compute the Möbius function of the rotation lattice of binary trees, RAIRO Inform. Théor. Appl. 27 (1993), no. 4, 341–348 (English, with English and French summaries). MR 1238055, DOI 10.1051/ita/1993270403411
J. Scott Provan and Louis J. Billera, Decompositions of simplicial complexes related to diameters of convex polyhedra, Math. Oper. Res. 5 (1980), no. 4, 576–594. MR 593648, DOI 10.1287/moor.5.4.576
Daniel Quillen, Homotopy properties of the poset of nontrivial $p$-subgroups of a group, Adv. in Math. 28 (1978), no. 2, 101–128. MR 493916, DOI 10.1016/0001-8708(78)90058-0
Saunders MacLane, Steinitz field towers for modular fields, Trans. Amer. Math. Soc. 46 (1939), 23–45. MR 17, DOI 10.1090/S0002-9947-1939-0000017-3
Bruce E. Sagan, Shellability of exponential structures, Order 3 (1986), no. 1, 47–54. MR 850397, DOI 10.1007/BF00403409
A. Sanders and M.L Wachs, The (co)homology of the lattice of partitions with lower bounded block size, in preparation.
Edwin H. Spanier, Algebraic topology, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0210112
R. P. Stanley, Supersolvable lattices, Algebra Universalis 2 (1972), 197–217. MR 309815, DOI 10.1007/BF02945028
Richard P. Stanley, Finite lattices and Jordan-Hölder sets, Algebra Universalis 4 (1974), 361–371. MR 354473, DOI 10.1007/BF02485748
Richard P. Stanley, Cohen-Macaulay complexes, Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976) NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., vol. 31, Reidel, Dordrecht, 1977, pp. 51–62. MR 0572989
Richard P. Stanley, Balanced Cohen-Macaulay complexes, Trans. Amer. Math. Soc. 249 (1979), no. 1, 139–157. MR 526314, DOI 10.1090/S0002-9947-1979-0526314-6
Richard P. Stanley, Combinatorics and commutative algebra, Progress in Mathematics, vol. 41, Birkhäuser Boston, Inc., Boston, MA, 1983. MR 725505, DOI 10.1007/978-1-4899-6752-7
S. Sundaram, Applications of the Hopf trace formula to computing homology representations, Proceedings of Jerusalem Combinatorics Conference, 1993 (H. Barcelo and G. Kalai, eds.), Contemporary Math., vol. 178, Amer. Math. Soc., 1994, pp. 277-309.
S. Sundaram and M.L. Wachs, The homology representations of the $k$-equal partition lattice, preprint 1994.
S. Sundaram and V. Welker, Group actions on arrangements of linear subspaces and applications to configuration spaces, preprint 1994.
M.L. Wachs, A basis for the homology of the $d$-divisible partition lattice, preprint 1992, Advances in Math. (to appear).
James W. Walker, Canonical homeomorphisms of posets, European J. Combin. 9 (1988), no. 2, 97–107. MR 939858, DOI 10.1016/S0195-6698(88)80033-7
V. Welker, Shellability in the lattice of subgroups of a finite group, Proceedings Jerusalem Combinatorics Conference, 1993 (H. Barcelo and G. Kalai, eds.), Contemporary Math., vol. 178, Amer. Math. Soc., Providence, RI, 1994, pp. 335–360.
Takemi Yanagimoto and Masashi Okamoto, Partial orderings of permutations and monotonicity of a rank correlation statistic, Ann. Inst. Statist. Math. 21 (1969), 489–506. MR 258209, DOI 10.1007/BF02532273
Günter M. Ziegler, On the poset of partitions of an integer, J. Combin. Theory Ser. A 42 (1986), no. 2, 215–222. MR 847552, DOI 10.1016/0097-3165(86)90092-0
Günter M. Ziegler, Shellability of chessboard complexes, Israel J. Math. 87 (1994), no. 1-3, 97–110. MR 1286818, DOI 10.1007/BF02772986