Annals of Combinatorics 4 (2000) 199-226

Flags and Shelings of Eulerian Cubical Posets

Richard Ehrenborg and Gábor Hetyei

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

Mathematics Department, 405 Snow Hall, University of Kansas, Lawrence, KS 66045-2142, USA

Received May 18, 1999

AMS Subject Classification: 05E99, 52B05, 52B22

Abstract. A cubical analog of Stanley's theorem expressing the cd-index of an Eulerian simplicial poset in terms of its h-vector is presented. This result implies that the cd-index conjecture for Gorenstein cubical posets follows from Ron Adin's conjecture on the non-negativity of his cubical h-vector for Cohen-Macaulay cubical posets. For cubical spheres, the standard definition of shelling is shown to be equivalent to the spherical one. A cubical analog of Stanley's conjecture about the connection between the cd-index of semisuspended simplicial shelling components and the reduced variation polynomials of certain subclasses of André permutations is established. The notion of signed André permutations used in this result is a common generalization of two earlier definitions of signed André permutations.

Keywords: Eulerian cubical posets, spherical shellability, Adin's cubical h-vector, signed André permutations


1.  R.M. Adin, A new cubical h-vector, In: Conference Proceedings at the 6th International Conference on Formal Power Series and Algebraic Combinatorics, DIMACS/Rutgers 1994.

2.  R.M. Adin, A new cubical h-vector, Discrete Math. 157 (1996) 3–14.

3.  E.K. Babson, L.J. Billera, and C.S. Chan, Neighborly cubics and a cubical lower bound conjecture, Israel J. Math. 102 (1997) 297–315.

4.  E.K. Babson and C.S. Chan, Counting faces of cubical spheres modulo two, Discrete Math. 212 (2000) 169–183.

5.  M. Bayer and L. Billera, Generalized Dehn–Sommerville relations for polytopes, spheres and Eulerian partially ordered sets, Inv. Math. 79 (1985) 143–157.

6.  M. Bayer and A. Klapper, A new index for polytopes, Discrete Comput. Geom. 6 (1991) 33–47.

7.  L.J. Billera and R. Ehrenborg, Monotonicity of the cd-index for polytopes, Math. Z., to appear.

8.  L.J. Billera, R. Ehrenborg, and M. Readdy, The cd-index of zonotopes and arrangements, In: Mathematical Essays in Honor of Gian-Carlo Rota, B.E. Sagan and R.P. Stanley, Eds., Birkhäuser, Boston, 1998, pp. 23–40.

9.  L.J. Billera, R. Ehrenborg, and M. Readdy, The c-2d-index of oriented matroids, J. Combin. Theory Ser. A 80 (1997) 79–105.

10.  A. Björner, Posets, regular CW-complexes and Bruhat order, Europ. J. Combin. 5 (1984) 7–16.

11.  H. Bruggesser and P. Mani, Shellable decompositions of cells and spheres, Math. Scand. 29 (1971) 197–205.

12.  C. Chan, Plane trees and H-vectors of shellable cubical complexes, SIAM J. Discrete Math. 4 (1991) 568–574.

13.  R. Ehrenborg and M. Readdy, The r-cubical lattice and a generalization of the cd-index, Europ. J. Combin. 17 (1996) 709–725.

14.  R. Ehrenborg and M. Readdy, Coproducts and the cd-index, J. Alg. Combin. 8 (1998) 273– 299.

15.  D. Foata and M.P. Schützenberger, Nombres d’Euler et permutations alternantes, In: A Survey of Combinatorial Theory, J.N. Srivastava et al., Eds., Amsterdam, North–Holland, 1973, pp. 173–187.

16.  B. Grünbaum, Convex Polytopes, John Wiley & Sons, Interscience Division, 1967.

17.  G. Hetyei, Simplicial and cubical complexes: Analogies and differences, Ph.D. Dissertation, Massachusetts Institute of Technology, 1994.

18.  G. Hetyei, On the Stanley ring of a cubical complex, Discrete Comput. Geom. 14 (1995) 305–330.

19.  G. Hetyei, On the cd-variation polynomials of André and simsun permutations, Discrete Comput. Geom. 16 (1996) 259–276.

20.  G. Hetyei, Invariants des complexes cubiques, Ann. Sci. Math. Qu´ebec 20 (1996) 35–52.

21.  N. Metropolis and G.-C. Rota, Combinatorial structure of the faces of the n-cube, SIAM J. Appl. Math. 35 (1978) 689–694.

22.  M. Purtill, André permutations, lexicographic shellability and the cd-index of a convex polytope, Trans. Amer. Math. Soc. 338 (1993) 77–104.

23.  R. Stanley, Enumerative Combinatorics, Vol. I,Wadsworth and Brooks/Cole, Pacific Grove, 1986.

24.  R. Stanley, Generalized h-vectors, intersection cohomology of toric varieties, and related results, In: Commutative Algebra and Combinatorics, M. Nagata and H. Matsumura, Eds., Advanced Studies in Pure Mathematics, Vol. 11, North-Holland, New York, 1987, pp. 187– 213.

25.  R. Stanley, f -vectors and h-vectors of simplicial posets, J. Pure Appl. Alg. 71 (1991) 319– 331.

26.  R. Stanley, Flag f -vectors and the cd-index, Math. Z. 216 (1994) 483–499.

27.  R. Stanley, A survey of Eulerian posets, In: Polytopes: Abstract, Convex, and Computational, T. Bisztriczky, P. McMullen, R. Schneider, and A.I. Weiss, Eds., NATO ASI Series C, Vol. 440, Kluwer Academic Publishers, 1994.

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