# Euler flag enumeration of Whitney stratified spaces†

Richard Ehrenborg<fnref n="1" />‡

Mark Goresky<fnref n="2" />§

Margaret Readdy<fnref n="1" />¶

**Abstract.** We show the cd-index exists for Whitney stratified manifolds by extending the notion of a graded poset to that of a quasi-graded poset. This is a poset endowed with an order-preserving rank function and a weighted zeta function. This allows us to generalize the classical notion of Eulerianness, and obtain a cd-index in the quasi-graded poset arena. We also extend the semi-suspension operation to that of embedding a complex in the boundary of a higher dimensional ball and study the shelling components of the simplex.

**Résumé.** Nous montrons le cd-index existe pour les manifolds de Whitney stratifiées en élargissant la notion d'un poset gradué à celle que un poset quasi-gradué. C'est un poset doté avec une fonction de rang que préservant l'ordre du poset et une fonction de zêta qu'est pondérée. Ceci nous permet de généraliser la notion classique de “Eulerianness”, et obtenir un cd-index dans l'arène des posets quasi-gradués. Nous tenons également à l'opération de semi-suspension pour que d'intégrer une complexe dans la frontière d'une balle de dimension supérieur et étudions les composants des shelling d'un simplex.

**Keywords:** Eulerian condition, quasi-graded poset, semisuspension, weighted zeta function, Whitney's conditions A and B.

## 1 Introduction

In this paper we extend the theory of face incidence enumeration of polytopes, and more generally, chain enumeration in graded Eulerian posets, to that of Whitney stratified spaces and quasi-graded posets.

The idea of enumeration using the Euler characteristic was suggested throughout Rota's work and influenced by Schanuel's categorical viewpoint [20, 23, 23, 25]. In order to carry out such a program that

<footnote n="1">¹Department of Mathematics, University of Kentucky, Lexington, KY 40506, USA</footnote>

<footnote n="2">²School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA</footnote>

<footnote>†The full version of this manuscript may be found at arXiv:1201.3377 [math.CO].</footnote>

<footnote>‡Partially supported by National Science Foundation grants DMS 0902063, DMS-0835373 and CCF-0832797.</footnote>

<footnote>§Partially supported by DARPA grant number HR0011-09-1-0010 and by a Bell Companies Fellowship.</footnote>

<footnote>¶This work was partially supported by a grant from the Simons Foundation (#206001 to Margaret Readdy) and NSF grants DMS-0835373 and CCF-0832797.</footnote>
is topologically meaningful and which captures the broadest possible classes of examples, two key insights are required. First, the notion of grading in the face lattice of a polytope must be relaxed. Secondly, the usual zeta function in the incidence algebra must be extended to include the Euler characteristic as an important instance.

The flag $f$-vector of a graded poset counts the number of chains passing through a prescribed set of ranks. In the case of a polytope, it records all of the face incidence data, including that of the $f$-vector. Bayer and Billera proved that the flag $f$-vector of any Eulerian poset satisfies a collection of linear equalities now known as the *generalized Dehn–Sommerville relations* [2]. These linear equations may be interpreted as natural redundancies among the components of the flag $f$-vector. Bayer and Klapper removed these redundancies by showing that the space of flag $f$-vectors of Eulerian posets has a natural basis with Fibonacci many elements consisting of certain non-commutative polynomials in the two variables $c$ and $d$ [3]. The coefficients of this cd-index were later shown by Stanley to be non-negative in the case of spherically-shellable posets [27]. Other milestones for the cd-index include its inherent coalgebraic structure [11], its appearance in the proofs of inequalities for flag vectors [5, 9, 10, 20], its use in understanding the combinatorics of arrangements of subspaces and sub-tori [6, 14], and most recently, its connection to the Bruhat graph and Kazhdan–Lusztig theory [4, 13].

In this article we extend the cd-index and its properties to a more general situation, that of quasi-graded posets and Whitney stratified spaces. A quasi-grading on a poset $P$ consists of a strictly order-preserving “rank” function $\rho: P \to \mathbb{N}$ and a weighted zeta function $\tilde{\zeta}$ in the incidence algebra $I(P)$ such that $\tilde{\zeta}(x, x) = 1$ for all $x \in P$. See Section 2. A quasi-graded poset $(P, \rho, \tilde{\zeta})$ will be said to be *Eulerian* if the function $(-1)^{\rho(y)-\rho(x)} \cdot \tilde{\zeta}(x, y)$ is the inverse of $\tilde{\zeta}(x, y)$ in the incidence algebra of $P$. This reduces to the classical definition of Eulerian if $(P, \rho, \tilde{\zeta})$ is a ranked poset with the standard zeta function $\zeta$.

**Theorem 3.1** states that the cd-index is defined for Eulerian quasi-graded posets. The existence of the cd-index for Eulerian quasi-graded posets is equivalent to the statement that the flag $\bar{f}$-vector of an Eulerian quasi-graded poset satisfies the generalized Dehn–Sommerville relations (Theorem 3.2).

Eulerian ranked posets arise geometrically as the face posets of regular cell decompositions of a sphere, whereas Eulerian quasi-graded posets arise geometrically from the more general case of Whitney stratifications. A *Whitney stratification* $X$ of a compact topological space $W$ is a decomposition of $W$ into finitely many smooth manifolds which satisfy Whitney’s “no-wiggle” conditions on how the strata fit together. See Section 4. These conditions guarantee (a) that $X$ does not exhibit Cantor set-like behavior and (b) that the closure of each stratum is a union of strata. The faces of a convex polytope and the cells of a regular cell complex are examples of Whitney stratifications, but in general, a stratum in a stratified space need not be contractible. Moreover, the closure of a stratum of dimension $d$ does not necessarily contain strata of dimension $d-1$, or for that matter, of any other dimension. Natural Whitney stratifications exist for real or complex algebraic sets, analytic sets, semi-analytic sets and for quotients of smooth manifolds by compact group actions.

The strata of a Whitney stratification (of a topological space $W$) form a poset, where the order relation $A < B$ is given by $A \subset \bar{B}$. Moreover, this set admits a natural quasi-grading which is defined by $\rho(A) = \dim(A) + 1$ and $\tilde{\zeta}(A, B) = \chi(\mathrm{link}(A) \cap B)$ whenever $A < B$ are strata and $\chi$ is the Euler
characteristic. See Definition 4.4. This is the setting for our Euler-characteristic enumeration.

Theorem 4.5 states that the quasi-graded poset of strata of a Whitney stratified set is Eulerian and therefore its cd-index is defined and its flag $\bar{f}$-vector satisfies the generalized Dehn–Sommerville relations. Due to space constraints, the background and results needed for this proof are omitted. Please refer to the full-length article for details.

It is important to point out that, unlike the case of polytopes, the coefficients of the cd-index of Whitney stratified manifolds can be negative. See Examples 4.1 and 4.8. It is our hope that by applying topological techniques to stratified manifolds, a combinatorial interpretation for the coefficients of the cd-index will be discovered. This may ultimately explain Stanley’s non-negativity results for spherically shellable posets [27] and Karu’s results for Gorenstein* posets [20], and settle the conjecture that non-negativity holds for regular cell complexes.

In his proof that the cd-index of a polytope is non-negative, Stanley introduced the notion of semisuspension. Given a polytopal complex that is homeomorphic to a ball, the semisuspension adds another facet whose boundary is the boundary of the ball. The resulting spherical CW-complex has the same dimension, and the intervals in its face poset are Eulerian [27].

It is precisely the setting of Whitney stratified manifolds, and the larger class of Whitney stratified spaces, which is critical in order to study face enumeration of the semisuspension in higher dimensional spheres and more general topologically interesting examples. In Section 5 the $n$th semisuspension and its cd-index is studied. In Theorem 5.2, by using the method of quasi-graded posets, we are able to give a short proof (that completely avoids the use of shellings) of a key result of Billera and Ehrenborg [5] that was needed for their proof that the $n$-dimensional simplex minimizes the cd-index among all $n$-dimensional polytopes. Furthermore, we establish the Eulerian relation for the $n$th semisuspension (Theorem 5.3).

In Section 6 the cd-index of the $n$th semisuspension of a non-pure shellable simplicial complex is determined. The cd-index of the shelling components are shown to satisfy a recursion involving a derivation which first appeared in [11]. By relaxing the notion of shelling, we furthermore show that the shelling components satisfy a Pascal type recursion. This yields new expressions for the shelling components and illustrates the power of leaving the realm of regular cell complexes for that of Whitney stratified spaces.

## 2 Quasi-graded posets and their ab-index

Recall the incidence algebra of a poset is the set of all functions $f: I(P) \to \mathbb{C}$ where $I(P)$ denotes the set of intervals in the poset. The multiplication is given by $(f \cdot g)(x, y) = \sum_{x<z\leq y} f(x, z) \cdot g(z, y)$ and the identity is given by the delta function $\delta(x, y) = \delta_{x,y}$, where the second delta is the usual Kronecker delta function $\delta_{x,y} = 1$ if $x = y$ and zero otherwise. A poset is said to be *ranked* if every maximal chain in the poset has the same length. This common length is called the *rank* of the poset. A poset is said to be *graded* if it is ranked and has a minimal element $\hat{0}$ and a maximal element $\hat{1}$. For other poset terminology,
we refer the reader to Stanley's treatise [26].

We introduce the notion of a quasi-graded poset. This extends the notion of a ranked poset.

**Definition 2.1** A quasi-graded poset $(P, \rho, \bar{\zeta})$ consists of (i) a finite poset $P$ (not necessarily ranked), (ii) a strictly order-preserving function $\rho$ from $P$ to $\mathbb{N}$, that is, $x < y$ implies $\rho(x) < \rho(y)$, and (ii) a function $\bar{\zeta}$ in the incidence algebra $I(P)$ of the poset $P$, called the weighted zeta function, such that $\zeta(x, x) = 1$ for all elements $x$ in the poset $P$.

Observe that we do not require the poset to have a minimal element or a maximal element. Since $\bar{\zeta}(x, x) \neq 0$ for all $x \in P$, the function $\bar{\zeta}$ is invertible in the incidence algebra $I(P)$ and we denote its inverse by $\bar{\mu}$.

For $x \le y$ in a quasi-graded poset $P = (P, \rho, \bar{\zeta})$, the *rank difference function* is given by $\rho(x, y) = \rho(y) - \rho(x)$. We say that a quasi-graded poset $(P, \rho, \bar{\zeta})$ with minimal element $\bar{0}$ and maximal element $\bar{1}$ has rank $n$ if $\rho(\bar{0}, \bar{1}) = n$. The interval $[x, y]$ is itself a quasi-graded poset together with the rank function $\rho_{[x, y]}(w) = \rho(w) - \rho(x)$ and the weighted zeta function $\bar{\zeta}$.

Let $(P, \rho, \bar{\zeta})$ be a quasi-graded poset with unique minimal element $\bar{0}$ and unique maximal element $\bar{1}$. The assumption of a quasi-graded poset having a $\bar{0}$ and $\bar{1}$ will be essential in order to define its **ab-index** and **cd-index**. For a chain $c = \{x_0 < x_1 < \cdots < x_k\}$ in the quasi-graded poset $P$, define $\bar{\zeta}(c)$ to be the product

$$ \bar{\zeta}(c) = \bar{\zeta}(x_0, x_1) \cdot \bar{\zeta}(x_1, x_2) \cdots \bar{\zeta}(x_{k-1}, x_k). \qquad (2.1) $$

Similarly, for the chain $c$ define its *weight* to be

$$ \mathrm{wt}(c) = (\mathbf{a} - \mathbf{b})^{\rho(x_0, x_1) - 1} \cdot \mathbf{b} \cdot (\mathbf{a} - \mathbf{b})^{\rho(x_1, x_2) - 1} \cdot \mathbf{b} \cdots \mathbf{b} \cdot (\mathbf{a} - \mathbf{b})^{\rho(x_{k-1}, x_k) - 1}, $$

where **a** and **b** are non-commutative variables each of degree 1. The **ab-index** of a quasi-graded poset $(P, \rho, \bar{\zeta})$ is

$$ \Psi(P, \rho, \bar{\zeta}) = \sum_{c} \bar{\zeta}(c) \cdot \mathrm{wt}(c), \qquad (2.2) $$

where the sum is over all chains starting at the minimal element $\bar{0}$ and ending at the maximal element $\bar{1}$, that is, $c = \{\bar{0} = x_0 < x_1 < \cdots < x_k = \bar{1}\}$. When the rank function $\rho$ and the weighted zeta function are clear from the context, we will write the shorter $\Psi(P)$. Observe that if a quasi-graded poset $(P, \rho, \bar{\zeta})$ has rank $n+1$ then its **ab-index** is homogeneous of degree $n$.

The **ab-index** depends on the rank difference function $\rho(x, y)$ but not on the rank function itself. Hence we may uniformly shift the rank function without changing the **ab-index**. Later we will use the convention that $\rho(\bar{0}) = 0$.

The **ab-index** of a quasi-graded poset is a coalgebra homomorphism. Define a coproduct $\Delta : \mathbb{Z}\langle\mathbf{a}, \mathbf{b}\rangle \to \mathbb{Z}\langle\mathbf{a}, \mathbf{b}\rangle \otimes \mathbb{Z}\langle\mathbf{a}, \mathbf{b}\rangle$ by $\Delta(1) = 0$ and for an **ab-monomial** $u = u_1u_2\cdots u_k$ by $\Delta(u) = \sum_{i=1}^k u_1\cdots u_{i-1} \otimes u_{i+1}\cdots u_k$ and extend $\Delta$ extend to $\mathbb{Z}\langle\mathbf{a}, \mathbf{b}\rangle$ by linearity. It is straightforward to see that this coproduct is coassociative. The coproduct $\Delta$ first appeared in [11].
**Theorem 2.2** Let $(P, \rho, \bar{\zeta})$ be a quasi-graded poset. Then the following identity holds:

$$ \Delta(\Psi(P, \rho, \bar{\zeta})) = \sum_{\hat{0} < x < \hat{1}} \Psi([\hat{0}, x], \rho, \bar{\zeta}) \otimes \Psi([x, \hat{1}], \rho, \bar{\zeta}). $$

A quasi-graded poset is said to be Eulerian if for all pairs of elements $x \le z$ we have that

$$ \sum_{x \le y \le z} (-1)^{\rho(x,y)} \cdot \bar{\zeta}(x,y) \cdot \bar{\zeta}(y,z) = \delta_{x,z}. \qquad (2.3) $$

In other words, the function $\bar{\mu}(x, y) = (-1)^{\rho(x,y)} \cdot \bar{\zeta}(x, y)$ is the inverse of $\bar{\zeta}(x, y)$ in the incidence algebra. In the case $\bar{\zeta}(x, y) = \zeta(x, y)$, we refer to relation (2.3) as the classical Eulerian relation.

**Theorem 2.3 (Alexander duality for quasi-graded posets)** Let $(P, \rho, \bar{\zeta})$ be an Eulerian quasi-graded poset with $\hat{0}$ and $\hat{1}$ of rank $n+1$. Let $Q$ and $R$ be two subposets of $P$ such that $Q \cup R = P$ and $Q \cap R = \{\hat{0}, \hat{1}\}$. Then

$$ (\bar{\zeta}|_Q)^{-1}(\hat{0}, \hat{1}) = (-1)^n \cdot (\bar{\zeta}|_R)^{-1}(\hat{0}, \hat{1}). $$

# 3 The cd-index and quasi-graded posets

Bayer and Billera determined all the linear relations which hold among the flag $f$-vector of (classical) Eulerian posets, known as the generalized Dehn–Sommerville relations [2]. Bayer and Klapper showed that the space of flag $f$-vectors of Eulerian posets have a natural basis of Fibonacci dimension as expressed by the cd-index [3]. Stanley later gave a more elementary proof of the existence of the cd-index for Eulerian posets and showed the coefficients are non-negative for spherically-shellable posets [27]. Generalizing the classical result of Bayer and Klapper for graded Eulerian posets, we have the analogue for quasi-graded posets.

**Theorem 3.1** For an Eulerian quasi-graded poset $(P, \rho, \bar{\zeta})$ its ab-index $\Psi(P, \rho, \bar{\zeta})$ can be written uniquely as a polynomial in the non-commutative variables $c = a + b$ and $d = ab + ba$. Furthermore, if the function $\bar{\zeta}$ is integer-valued then the cd-index only has integer coefficients.

A different way to express the existence of the cd-index is as follows.

**Theorem 3.2** The flag $\bar{f}$-vector of an Eulerian quasi-graded poset of rank $n+1$ satisfies the generalized Dehn–Sommerville relations. More precisely, for a subset $S \subseteq \{1, \dots, n\}$ and $i, k \in S \cup \{0, n+1\}$ with $i < k$ and $S \cap \{i+1, \dots, k-1\} = \emptyset$, the following relation holds:

$$ \sum_{j=i}^{k} (-1)^{j} \cdot \bar{f}_{S \cup \{j\}} = 0. \qquad (3.1) $$
# 4 Whitney stratified sets

**Example 4.1** Consider the non-regular CW-complex $\Omega$ consisting of one vertex $v$, one edge $e$ and one 2-dimensional cell $c$ such that the boundary of $c$ is the union $v \cup e$, that is, boundary of the complex $\Omega$ is a one-gon. Its face poset is the four element chain $\mathcal{F}(\Omega) = \{\emptyset < v < e < c\}$. This is not an Eulerian poset. The classical definition of the ab-index, in other words, using $\bar{\zeta}(x, y) = 1$ for all $x \le y$, yields that the ab-index of $\Omega$ is $a^2$. Note that $a^2$ cannot be written in terms of $c$ and $d$.

Observe that the edge $e$ is attached to the vertex $v$ twice. Hence it is natural to change the value of $\bar{\zeta}(v, e)$ to be 2. The face poset $\mathcal{F}(\Omega)$ is now Eulerian, its ab-index is given by $\bar{\zeta}(\Omega) = a^2 + b^2$ and hence its cd-index is $\bar{\zeta}(\Omega) = c^2 - d$.

The motivation for the value 2 in Example 4.1 is best expressed in terms of the Euler characteristic of the link. The link of the vertex $v$ in the edge $e$ is two points whose Euler characteristic is 2. In order to view this example in the right topological setting, we review the notion of a Whitney stratification. For more details, see [8], [17], [18, Part I §1.2], and [22].

A subset $S$ of a topological space $M$ is locally closed if $S$ is a relatively open subset of its closure $\bar{S}$. Equivalently, for any point $x \in S$ there exists a neighborhood $U_x \subseteq S$ such that the closure $\bar{U}_x \subseteq S$ is closed in $M$. Another way to phrase this is a subset $S \subseteq M$ is locally closed if and only if it is the intersection of an open subset and a closed subset of $M$.

**Definition 4.2** Let $W$ be a closed subset of a smooth manifold $M$ which has been decomposed into a finite union of locally closed subsets

$$W = \bigcup_{X \in \mathcal{P}} X.$$

Furthermore suppose this decomposition satisfies the condition of the frontier:

$$X \cap \bar{Y} \neq \emptyset \iff X \subseteq \bar{Y}.$$

This implies the closure of each stratum is a union of strata, and it provides the index set $\mathcal{P}$ with the partial ordering: $X \subseteq \bar{Y} \iff X \subseteq \mathcal{P} Y$. This decomposition of $W$ is a Whitney stratification if

1. Each $X \in \mathcal{P}$ is a (locally closed, not necessarily connected) smooth submanifold of $M$.

2. If $X \subsetneq Y$ then Whitney's conditions (A) and (B) hold: Suppose $y_i \in Y$ is a sequence of points converging to some $x \in X$ and that $x_i \in X$ converges to $x$. Also assume that (with respect to some local coordinate system on the manifold $M$) the secant lines $l_i = \overline{x_i y_i}$ converge to some limiting line $l$ and the tangent planes $T_{y_i} Y$ converge to some limiting plane $\tau$. Then the following inclusions hold:

(A) $T_x X \subseteq \tau$ and (B) $l \subseteq \tau$.
**Remark 4.3** An example of an algebraic set W with a decomposition into smooth manifolds that is not locally trivial is provided by *Whitney's cusp*. See [22, Example 2.6] and [30].

We next state the key definition for developing face incidence enumeration for Whitney stratified spaces.

**Definition 4.4** Let W be a Whitney stratified closed subset of a smooth manifold M. Define the face poset $\mathcal{F} = \mathcal{F}(W)$ of W to be the quasi-graded poset consisting of the poset of strata P adjoined with a minimal element $\emptyset$. The rank function is given by $\rho(X) = \dim(X) + 1$ if $X > \emptyset$ and $\rho(\emptyset) = 0$. The weighted zeta function is $\zeta(X, Y) = \chi(\mathrm{link}_Y(X))$ if $X > \emptyset$ and $\zeta(\emptyset, Y) = \chi(Y)$.

**Theorem 4.5** Let W be Whitney stratified closed subset of a smooth manifold M. Then the face poset of W is an Eulerian quasi-graded poset.

We now give a few examples of Whitney stratifications beginning with the classical polygon.

**Example 4.6** Consider a two dimensional cell c with its boundary subdivided into n vertices $v_1, \dots, v_n$ and n edges $e_1, \dots, e_n$. There are three ways to view this as a Whitney stratification.

(1) Declare each of the $2n + 1$ cells to be individual strata. This is the classical view of an n-gon. Here the weighted zeta function is the classical zeta function, that is, always equal to 1 (assuming $n \ge 2$).

(2) Declare the union of the $n$ edges to be one stratum $e = \cup_{i=1}^n e_i$, that is, we have the $n + 2$ strata $v_1, \dots, v_n, e, c$. Here the non-one values of the weighted zeta function are given by $\zeta(\emptyset, e) = n$ and $\zeta(v_i, e) = 2$.

(3) Lastly, we can have the three strata $v = \cup_{i=1}^n v_i$, $e = \cup_{i=1}^n e_i$ and $c$. Now non-one values of the weighted zeta function are given by $\zeta(\emptyset, v) = \zeta(\emptyset, e) = n$ and $\zeta(v, e) = 2$.

In contrast, we cannot have $v, e_1, \dots, e_n, c$ as a stratification, since the link of a point $p$ in $e_i$ depends on the point $p$ in $v$ chosen.

The cd-index of each of the three Whitney stratifications in Example 4.6 are the same, that is, the cd-index of an n-gon is given by $c^2 + (n-2) \cdot d$ for $n \ge 1$.

The last stratification in the previous example can be extended to any simple polytope.

**Example 4.7** Let P be an $n$-dimensional simple polytope. Recall that the simple condition implies that every interval $[x, y]$, where $\emptyset < x \le y$, is a Boolean algebra. We obtain a different stratification of the ball by joining all the facets together to one strata. Note that the cd-index does not change, since the information is carried in the weighted zeta function. We continue by joining all the subfacets together to one strata. Again the cd-index remains unchanged. In the end we obtain a stratification where the union of all the $i$-dimensional faces forms the $i$th strata $x_{i+1}$. The face poset of this stratification is the
(n + 2)-element chain $C = \{\hat{0} = x_0 < x_1 < \dots < x_{n+1} = \hat{0}\}$, with the rank function $\rho(x_i) = i$ and weighted zeta function $\bar{\zeta}(\hat{0}, x_i) = f_{i-1}(P)$ and $\bar{\zeta}(x_i, x_j) = \binom{n+1-i}{n+1-j}$. We have $\Psi(C, \rho, \bar{\zeta}) = \Psi(P)$.

A similar stratification can be obtained for any regular polytope, since the isomorphism type of any upper interval $[x, \hat{1}]$ only depends on the rank $\rho(x)$.

The next example is a higher dimensional analogue of the one-gon in Example 4.1.

**Example 4.8** Consider the subdivision $\Omega_n$ of the $n$-dimensional ball $\mathbb{B}^n$ consisting of a point $p$, an $(n-1)$-dimensional cell $c$ and the interior $b$ of the ball. If $n \ge 2$, the face poset is $\{\hat{0} < p < c < b\}$ with the elements having ranks 0, 1, $n$ and $n+1$, respectively. In the case $n = 1$, the two elements $p$ and $c$ are incomparable. The weighted zeta function is given by $\bar{\zeta}(\hat{0}, p) = \bar{\zeta}(\hat{0}, c) = \bar{\zeta}(\hat{0}, b) = 1$, $\bar{\zeta}(p, c) = 1 + (-1)^n$, and $\bar{\zeta}(p, b) = \bar{\zeta}(c, b) = 1$. When $n$ is even, the cd-index evaluates to

$$ \Psi(\Omega_n) = \frac{1}{2} \cdot \left[ (\mathbf{c}^2 - 2\mathbf{d})^{n/2} + \mathbf{c} \cdot (\mathbf{c}^2 - 2\mathbf{d})^{(n-2)/2} \cdot \mathbf{c} \right], \quad (4.1) $$

and when $n$ is odd

$$ \Psi(\Omega_n) = \frac{1}{2} \cdot \left[ \mathbf{c} \cdot (\mathbf{c}^2 - 2\mathbf{d})^{(n-1)/2} + (\mathbf{c}^2 - 2\mathbf{d})^{(n-1)/2} \cdot \mathbf{c} \right]. \quad (4.2) $$

As a remark, these cd-polynomials played an important role in proving that the cd-index of a polytope is coefficient-wise minimized on the simplex, namely, $\Psi(\Omega_n) = (-1)^{n-1} \alpha_n$, where $\alpha_n$ are defined in [5]. See Theorem 5.2 for a generalization of one of the main identities in [5].

# 5 The semisuspension

Let $\Gamma$ be a polytopal complex, that is, a regular cell complex whose cells are polytopes. Assume the dimension of $\Gamma$ is $k$. Let $n > k$ be an integer. We define the $n$th semisuspension of $\Gamma$, denoted Semi($\Gamma, n$), to be the family of CW-complexes obtained by embedding $\Gamma$ in the boundary of an $n$-dimensional ball $\mathbb{B}^n$, if they exist. Note that one really has a family of embeddings. For example, one can embed a circle into the boundary of a 4-dimensional ball so that the result is any given knot. Nevertheless, we will show the face poset of Semi($\Gamma, n$) is well-defined. Furthermore, in the case $\Gamma$ is homeomorphic to a $k$-dimensional ball, the semisuspension Semi($\Gamma, n$) is unique.

**Theorem 5.1** Let $\Gamma$ and $\Delta$ be two polytopal complexes such that their union $\Gamma \cup \Delta$ is a polytopal complex of dimension less than $n$. Then the following inclusion-exclusion relation holds:

$$ \Psi(\text{Semi}(\Gamma, n)) + \Psi(\text{Semi}(\Delta, n)) = \Psi(\text{Semi}(\Gamma \cap \Delta, n)) + \Psi(\text{Semi}(\Gamma \cup \Delta, n)). $$
The next theorem generalizes Proposition 4.3 in [5] which considered the case when $F_1, \dots, F_r$ is the initial line shelling segment of an $n$-dimensional polytope. Their proof is based on shelling, whereas our proof of Theorem 5.2 is an application of inclusion-exclusion.

**Theorem 5.2** Let $\Gamma$ be a polytopal complex of dimension less than $n$. Assume that $\Gamma$ has facets $F_1, \dots, F_r$. Then the cd-index of the semisuspension $\text{Semi}(\Gamma, n)$ is given by

$$ \Psi(\text{Semi}(\Gamma, n)) = - \sum_F \tilde{\chi}(\text{link}_\Gamma(F)) \cdot \Psi(F) \cdot \Psi(\Omega_{n-\dim(F)}), $$

where the sum is over all possible intersections $F$ of the facets $F_1, \dots, F_r$.

Let $\Gamma$ be a regular subdivision of an $n$-dimensional ball $\mathbb{B}^n$ such that the interior of the ball is one the faces. Let $\Lambda$ be a regular subdivision of $\Gamma$ such that the interior of the ball is yet again a face of $\Lambda$. For a face $F$ of $\Gamma$ we define $\Lambda|_F$ to be the subdivision of $F$ induced by $\Lambda$. There are two extremal cases. When $F$ is the empty set, let $\Lambda|_F$ be the empty subdivision of the empty face. In this case the semisuspension $\text{Semi}(\Lambda|_F, n)$ is the $(n-1)$-dimensional sphere and the interior of the $n$-dimensional ball. The second extremal case is when $F = \hat{1}$, and we let $\Lambda|_F$ and $\text{Semi}(\Lambda|_F, n)$ denote the subdivision $\Lambda$ of the $n$-dimensional sphere.

**Theorem 5.3** Let $\Gamma$ be a regular subdivision of the $n$-ball $\mathbb{B}^n$ and let $\Lambda$ be a regular subdivision of $\Gamma$ such that both subdivisions have the interior of the ball as a face. Then the alternating sum of cd-indices of semisuspensions is equal to zero, that is,

$$ \sum_{F \in \Gamma} (-1)^{\rho(F, \hat{1})} \cdot \Psi(\text{Semi}(\Lambda|_F, n)) = 0. $$

# 6 Shelling components for non-pure simplicial complexes

We now turn our attention to computing the cd-index of the $n$th semisuspension of a (non-pure) shellable simplicial complex. The first step is to define the shelling components. For $i \le k$ let $\Delta_{k,i}$ be the simplicial complex consisting of $i+1$ facets of the $k$-dimensional simplex. Define the quasi-graded poset $P_{n,k,i}$ for $0 \le i \le k \le n$ to be the face poset of the semisuspension $P_{n,k,i} = \mathcal{F}(\text{Semi}(\Delta_{k,i}, n))$. Define the shelling component $\tilde{\Phi}(n, k, i)$ to be the difference $\tilde{\Phi}(n, k, i) = \Psi(P_{n,k,i}) - \Psi(P_{n,k,i-1})$ for $1 \le i \le k \le n$ and $\tilde{\Phi}(n, k, 0) = \Psi(P_{n,k,0})$ for $0 \le k \le n$. The polynomials $\tilde{\Phi}(n, n, i)$ (the case $k = n$) were introduced by Stanley [27]. Let $G$ be the derivation on $\mathbb{Z}\langle\mathbf{c}, \mathbf{d}\rangle$ defined by $G(\mathbf{c}) = \mathbf{d}$ and $G(\mathbf{d}) = \mathbf{cd}$.

**Theorem 6.1** The shelling components of the simplex satisfy the recursion

$$ G(\tilde{\Phi}(n, k, i)) = \tilde{\Phi}(n + 1, k + 1, i + 1) $$
with the boundary conditions $\tilde{\Phi}(n, k, 0) = \Psi(B_k) \cdot \Psi(\Omega_{n-k+1})$, for $k \ge 1$ and $\tilde{\Phi}(n, 0, 0)$ is $(\mathbf{c}^2 - 2\mathbf{d})^{n/2}$ or $(\mathbf{c}^2 - 2\mathbf{d})^{(n-1)/2} \cdot \mathbf{c}$ depending on parity of $n$.

Recall that Björner and Wachs [7] extended the notion of shellability to non-pure complexes. They generalized the h-vector to the h-triangle.

**Theorem 6.2** Let $\Delta$ be a non-pure shellable simplicial complex of dimension at most $n$. Then the cd-index of the semisuspension of $\Delta$ is given by

$$ \Psi(\text{Semi}(\Delta, n)) = \sum_{k=0}^{n} \sum_{i=0}^{k} h_{k,i} \cdot \tilde{\Phi}(n, k, i), $$

where the h-triangle entry $h_{k,i}$ is the number of facets of shelling type $(k, i)$.

# 7 Concluding remarks

As was mentioned in the introduction, finding the linear inequalities that hold among the entries of the cd-index of a Whitney stratified manifold expands the program of determining linear inequalities for flag vectors of polytopes. Since the coefficients may be negative, one must ask what should the new minimization inequalities be. Observe that Kalai's convolution [19] still holds. More precisely, let $M$ and $N$ be two linear functionals defined on the cd-coefficients of any $m$-dimensional, respectively, $n$-dimensional manifold. If both $M$ and $N$ are non-negative then their convolution is non-negative on any $(m+n+1)$-dimensional manifold.

Other inequality questions are: Can Ehrenborg's lifting technique [9] be extended to stratified manifolds? Is there an associated Stanley-Reisner ring for the barycentric subdivision of a stratified space, and if so, what is the right version of the Cohen-Macaulay property [28]? Finally, what non-linear inequalities hold among the cd-coefficients?

One interpretation of the coefficients of the cd-index is due to Karu [20] who, for each cd-monomial, gave a sequence of operators on sheaves of vector spaces to show the non-negativity of the coefficients of the cd-index for Gorenstein* posets [20]. Is there a signed analogue of Karu's construction to explain the negative coefficients occurring in the cd-index of quasi-graded posets?

Observe that the shelling components $\tilde{\Phi}(n, k, i)$ can have negative coefficients. For which values of $n, k$ and $i$ do we know that they are non-negative? Is there a combinatorial interpretation of the cd-polynomials $\tilde{\Phi}(n, k, i)$? In the case $n = k$ such interpretations are known in terms of André permutations and Simsun permutations [11, 15, 16].

Given a Whitney stratified space, its face poset with rank function given by dimension and weighted zeta function involving the Euler characteristic (see Definition 4.4 and Theorem 4.5) yields an Eulerian
quasi-graded poset. Conversely, given an Eulerian quasi-graded poset $(P, \rho, \tilde{\zeta})$ can one construct an associated Whitney stratified space? It is clear that for $x \prec y$ with $\rho(x) + 1 = \rho(y)$ one must require $\tilde{\zeta}(x, y)$ to be a positive integer since $\text{link}_y x$ is a 0-dimensional space consisting of a collection of one or more points. What other conditions on an Eulerian quasi-graded poset are necessary so that it is the face poset of a Whitney stratified space?

As always when the ab-index is defined one also has the companion quasisymmetric function. This quasisymmetric function can be defined by the (almost) isomorphism $\gamma$ in [12, Section 3]. More directly, for a chain $c = \{\hat{0} = x_0 < x_1 < \cdots < x_k = \hat{1}\}$, define the composition $\rho(c) = (\rho(x_0, x_1), \rho(x_1, x_2), \dots, \rho(x_{k-1}, x_k))$. Then the quasisymmetric function of a quasi-graded poset $(P, \rho, \tilde{\zeta})$ is given by $F(P, \rho, \tilde{\zeta}) = \sum_c \tilde{\zeta}(c) \cdot M_{\rho(c)}$, where $M$ is the monomial quasisymmetric function. It is straightforward to observe that $F$ can be viewed as a Hopf algebra morphism as follows.

$$ \Delta(F(P, \rho, \tilde{\zeta})) = \sum_{\hat{0} \le x \le \hat{1}} F([\hat{0}, x], \rho, \tilde{\zeta}) \otimes F([x, \hat{1}], \rho, \tilde{\zeta}), \\ F(P \times Q, \rho_{P \times Q}, \tilde{\zeta}_{P \times Q}) = F(P, \rho_P, \tilde{\zeta}_P) \times F(Q, \rho_Q, \tilde{\zeta}_Q). $$

See [1] for results on generalized Dehn–Sommerville relations in the setting of combinatorial Hopf algebras.

## Acknowledgements

The authors thank the Institute for Advanced Study where this research was done.

## References

[1] M. AGUIAR, N. BERGERON AND F. SOTTILE, Combinatorial Hopf algebras and generalized Dehn–Sommerville relations, *Compos. Math.* **142** (2006), 1–30.

[2] M. BAYER AND L. BILLERA, Generalized Dehn–Sommerville relations for polytopes, spheres and Eulerian partially ordered sets, *Invent. Math.* **79** (1985), 143–157.

[3] M. BAYER AND A. KLAPPER, A new index for polytopes, *Discrete Comput. Geom.* **6** (1991), 33–47.

[4] L. J. BILLERA AND F. BRENTI, Quasisymmetric functions and Kazhdan–Lusztig polynomials, *Israel J. Math.* **184** (2011), 317–348.

[5] L. J. BILLERA AND R. EHRENBORG, Monotonicity properties of the cd-index for polytopes, *Math. Z.* **233** (2000), 421–441.

[6] L. J. BILLERA, R. EHRENBORG, AND M. READDY, The c-2d-index of oriented matroids, *J. Combin. Theory Ser. A* **80** (1997), 79–105.

[7] A. BJÖRNER AND M. WACHS, Shellable nonpure complexes and posets. I, *Trans. Amer. Math. Soc.* **348** (1996), 1299–1327.
[8] A. DU PLESSIS AND T. WALL, *The Geometry of Topological Stability*, London Mathematical Society Monographs. New Series, 9. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1995.

[9] R. EHRENBORG, Lifting inequalities for polytopes, *Adv. Math.* **193** (2005), 205–222.

[10] R. EHRENBORG AND K. KARU, Decomposition theorem for the cd-index of Gorenstein posets, *J. Algebraic Combin.* **26** (2007), 225–251.

[11] R. EHRENBORG AND M. READDY, Coproducts and the cd-index, *J. Algebraic Combin.* **8** (1998), 273–299.

[12] R. EHRENBORG AND M. READDY, The Tchebyshev transforms of the first and second kind, *Ann. Comb.* **14** (2010), 211–244.

[13] R. EHRENBORG AND M. READDY, The cd-index of Bruhat and balanced graphs, preprint 2011.

[14] R. EHRENBORG, M. READDY AND M. SLONE, Affine and toric hyperplane arrangements, *Discrete Comput. Geom.* **41** (2009), 481–512.

[15] G. HETYEI, On the cd-variation polynomials of André and simsun permutations, *Discrete Comput. Geom.* **16** (1996), 259–276.

[16] G. HETYEI AND E. REINER, Permutation trees and variation statistics, *European J. Combin.* **19** (1998), 847–866.

[17] C. G. GIBSON, K. WIRTHMÜLLER, A. DU PLESSIS AND E. J. N. LOOIJENGA, *Topological Stability of Smooth Mappings*, Lecture Notes in Mathematics, Vol. 552. Springer-Verlag, Berlin-New York, 1976.

[18] M. GORESKY AND R. MACPHERSON, *Stratified Morse Theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], 14*, Springer-Verlag, Berlin, 1988.

[19] G. KALAI, A new basis of polytopes, *J. Combin. Theory Ser. A* **49** (1988), 191–209.

[20] K. KARU, The cd-index of fans and posets, *Compos. Math.* **142** (2006), 701–718.

[21] D. KLAIN AND G.-C. ROTA, *Introduction to Geometric Probability. Lezioni Lincee. [Lincei Lectures]*, Cambridge University Press, Cambridge, 1997.

[22] J. MATHER, Notes on topological stability, Harvard University, 1970.

[23] G.-C. ROTA, On the combinatorics of the Euler characteristic, in *Studies in Pure Mathematics (Presented to Richard Rado)*, pp. 221–233, Academic Press, London, 1971.

[24] G.-C. ROTA, On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete **2** (1964), 340–368.

[25] S. SCHANUEL, Negative sets have Euler characteristic and dimension in *Category theory (Como, 1990)*, Lecture Notes in Math., **1488**, pp. 379–385, Springer, Berlin, 1991.

[26] R. P. STANLEY, *Enumerative Combinatorics, Vol. I.*, Wadsworth and Brooks/Cole, Pacific Grove, 1986.

[27] R. P. STANLEY, Flag f-vectors and the cd-index, *Math. Z.* **216** (1994), 483–499.

[28] R. P. STANLEY, *Combinatorics and Commutative Algebra, Second edition*, Progress in Mathematics, 41, Birkhäuser Boston, Inc., Boston, MA, 1996.

[29] R. THOM, Ensembles et morphismes stratifiés, *Bull. Amer. Math. Soc.* **75** (1969), 240–284.

[30] H. WHITNEY, Local properties of analytic varieties. 1965 *Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse)* pp. 205–244 Princeton University Press, Princeton, NJ.