PlanetMath: $\mathbf{ab}$-index of graded posets

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (204)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

$\mathbf{ab}$ -index of graded posets

(Topic)

Let be a graded poset of rank with a $\hat{0}$ and a $\hat{1}$ . Let $\rho\colon P\to\mathbb{N}$ be the rank function of . The $\mathbf{ab}$ -index of with coefficients in the ring is a noncommutative polynomial $\Psi(P)$ in the free associative algebra $R\langle\mathbf{a},\mathbf{b}\rangle$ defined by the formula

$\displaystyle \Psi(P)=\sum_{c=\{\hat{0}=x_0<x_1<\dots<x_k=\hat{1}\}}w(c),$

with the weight of a chain

defined by $w(c)=z_1\cdots z_n$ , where

$\displaystyle z_i=\begin{cases} \mathbf{b}, & i\in\rho(x_0,\dots,x_k) \ \mathbf{a}-\mathbf{b}, & \text{otherwise}. \end{cases}$

Let us compute $\Psi$ in a simple example. Let be the face lattice of an -gon. Below we display .

$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & & \hat{1}\ar@{-}[lld]\ar@{-}[l... ...@{-}[d] & \{s\}\ar@{-}[ld] & \{t\}\ar@{-}[lld] \ & & \hat{0} & & } } \end{xy}$

Thus

has

atoms, corresponding to vertices, and

coatoms, corresponding to edges. Further, each vertex is incident with exactly two edges. Let $c=\{\hat{0}=x_0<\cdots<x_k=\hat{1}\}$ be a chain in

. There are four possibilities.

$c=\{\hat{0} < \hat{1}\}$ . This chain does not include any elements of ranks 1 or 2, so its weight is $(\mathbf{a}-\mathbf{b})^2=\mathbf{a}^2-\mathbf{a}\mathbf{b}-\mathbf{b}\mathbf{a}+\mathbf{b}^2$ .
includes a vertex but not an edge. This can happen in ways. Each such chain has weight $\mathbf{b}(\mathbf{a}-\mathbf{b})$ .
includes an edge but not a vertex. This can also happen in ways. Each such chain has weight $(\mathbf{a}-\mathbf{b})\mathbf{b}$ .
includes a vertex and an edge. Since each vertex is incident with exactly two edges, this can happen in ways. The weight of such a chain is .

Summing over all the chains yields

$\displaystyle \Psi(P)$	$\displaystyle =\mathbf{a}^2+(n-1)\cdot\mathbf{a}\mathbf{b}+(n-1)\cdot\mathbf{b}\mathbf{a}+\mathbf{b}^2$
	$\displaystyle =(\mathbf{a}+\mathbf{b})^2+(n-2)\cdot(\mathbf{a}\mathbf{b}+\mathbf{b}\mathbf{a}).$

In this case the $\mathbf{a}\mathbf{b}$ -index can be rewritten as a noncommutative polynomial in the variables $\mathbf{c}=\mathbf{a}+\mathbf{b}$ and $\mathbf{d}=\mathbf{a}\mathbf{b}+\mathbf{b}\mathbf{a}$ . When this happens, we say that

has a $\mathbf{c}\mathbf{d}$ -index. Thus the $\mathbf{c}\mathbf{d}$ -index of the

-gon is $\mathbf{c}^2+(n-2)\cdot\mathbf{d}$ . Not every graded poset has a $\mathbf{c}\mathbf{d}$ -index. However, every poset which arises as the face lattice of a convex polytope, or more generally, every graded poset which satisfies the generalized Dehn-Sommerville relations, has a $\mathbf{c}\mathbf{d}$ -index.

An example of a poset whose $\mathbf{a}\mathbf{b}$ -index cannot be written in terms of $\mathbf{c}$ and $\mathbf{d}$ is the boolean algebra with a new maximal element adjoined:

$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & \hat{1}\ar@{-}[d] & \ & \{0,... ...-}[rd] & \ \{0\}\ar@{-}[rd] & & \{1\}\ar@{-}[ld] \ & \hat{0} & } } \end{xy}$

The $\mathbf{a}\mathbf{b}$ -index of this poset is $\mathbf{a}^2+\mathbf{b}\mathbf{a}$ .

Bibliography

1: Bayer, M. and L. Billera, Generalized Dehn-Sommerville relations for polytopes, spheres and Eulerian partially ordered sets, Invent. Math. 79 (1985), no. 1, 143-157.
2: Bayer, M. and A. Klapper, A new index for polytopes, Discrete Comput. Geom. 6 (1991), no. 1, 33-47.
3: Stanley, R., Flag -vectors and the $\mathbf{cd}$ -index, Math. Z. 216 (1994), 483-499.