Annals of Combinatorics 1 (1997) 67-90

General Lexicographic Shellability and Orbit Arrangements

Dmitry N. Kozlov

Department of Mathematics, Royal Institute of Technology, S-100 44, Stockholm, Sweden

Received May 20, 1996

AMS Subject Classification: 52B30, 05A17, 06A10

Abstract. We introduce a new poset property which we call EC-shellability. It is more general than the more stablished concept of EL-shellability, but it still implies shellability. Because of Theorem 3.10, EC-shellability is entitled to be called general lexicographic shellability.
       As an application of our new concept, we prove that intersection lattices Πλ of orbit arrangements ${\cal A}_\lambda$ are EC-shellable for a very large class of partitions λ. This allows us to compute the topology of the link and the complement for these arrangements. In particular, for this class of λs, we are able to settle a conjecture of Björner [B94, Conjecture 13.3.2], stating that the cohomology groups of the complement of the orbit arrangements are torsion-free.
       We also present a class of partitions for which Πλ is not shellable, along with other issues scattered throughout the paper.

Keywords: subspace arrangement, hyperplane arrangement, poset, shellability, intersection lattice, homology groups, number partition, labeling, Möbius function, k-equal arrangement


1.  A. Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980) 159–183.

2.  A. Björner, Topological Methods, In: Handbook of Combinatorics, R. Graham, M. Grötschel and L. Lovàsz, Eds., North-Holland, 1995, pp. 1819–1872.

3.  A. Björner, Subspace arrangements, In: First European Congress of Mathematics, Paris 1992, A. Joseph et al., Eds, Progress in Math. 119, Birkhäuser, 1994, pp. 321–370.

4.  A. Björner, Nonpure shellability, f-vectors, subspace arrangements and complexity, In: Formal Power Series and Algebraic Combinatorics, New Brunswik, NJ 1994, pp. 25–53.

5.  A. Björner, A.M. Garsia, and R.P. Stanley, An introduction to Cohen-Macaulay partially ordered sets, In: Ordered Sets, I. Rival, Ed., Reidel, Dordrecht/Boston, 1982, pp. 583–615.

6.  A. Björner and L. Lovàsz, Linear decision trees, subspace arrangements and Möbius functions, J. Amer. Math. Soc. 7 (1994) 677–706.

7.  A. Björner, L. Lovàsz, and A. Yao, Linear decision trees: volume estimates and topological bounds, In: Proc. 24th ACM Symp. on Theory of Computing, ACM Press, New York, 1992, pp. 170–177.

8.  A. Björner and B. Sagan, Subspace arrangements of type Bn and Dn, J. Algebraic Combin., to appear.

9.  A. Björner and M.~Wachs, Bruhat order of Coxeter groups and shellability, Adv. Math. 43 (1982) 87–100.

10.  A. Björner and M. Wachs, On lexicographically shellable posets, Trans. Amer. Math. Soc. 277 (1983) 323–341.

11.  A. Björner and M. Wachs, Shellable non-pure complexes and posets I, Trans. Amer. Math. Soc. 348(4) (1996) 1299–1327.

12.  A. Björner and V. Welker, The homology of "k-equal" manifolds and related partition lattices, Adv. Math. 110 (1995) 277–313.

13.  P. Diaconis, R. Graham, and B. Sturmfels, Primitive partition identities, In: Paul Erdös is 80, Vol. II, Bolyai Soc., to appear.

14.  E.M. Feichtner and D.N. Kozlov, On subspace arrangements of type D, Technische Universität, Berlin, preprint 489/1995.

15.  M. Goresky and R. MacPherson, Stratified Morse Theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, Vol. 14, Springer-Verlag, Berlin/Heidelberg/New York, 1988.

16.  D.N. Kozlov, Poset homology via spectral sequences, in preparation.

17.  D.N. Kozlov, On shellability of hypergraph arrangements, J. Combin. Theory, submitted.

18.  J.R. Munkres, Elements of Algebraic Topology, Addison-Wesley, Menlo Park, CA, 1984.

19.  R.P. Stanley, Enumerative Combinatorics, Vol. I, Wadsworth, Belmont, CA, 1986.

20.  B. Sturmfels, Gröbner bases and convex polytopes, Extended Lecture Notes from the Holiday Symposium at New Mexico State Univ., Las Cruces, 1994.

21.  S. Sundaram and M. Wachs, The homology representations of the k-equal partition lattice, Trans. Amer. Math. Soc., to appear.

22.  A. Vince, A non-shellable 3-sphere, Europ. J. Combin. 6 (1985) 91–100.

23.  A. Vince and M. Wachs, A shellable poset, that is not lexicographically shellable, Combinatorica 5 (1985) 257–260.

24.  M. Wachs, A basis for the homology of d-divisible partition lattices, Adv. Math. 117(2) (1996) 294–318.

25.  J.W. Walker, A poset which is Shellable, but not Lexicographically Shellable, Europ. J. Combin. 6 (1985) 287–288.

26.  G.M. Ziegler and R. \v{Z}ivaljevic, Homotopy types of subspace arrangements via diagrams of spaces, Math. Ann. 295 (1993) 527–548.

Get the LaTeX | DVI | PS file of this abstract.