Posets, simplicial complexes, and polytopes


Definition partially ordered set or poset is a set P equipped with a relation \leq that is reflexive, antisymmetric, and transitive. That is, for all x,y,z\in P:

  1. x\leq x.
  2. If x\leq y and y\leq x, then x=y (antisymmetry)
  3. If x\leq y and y\leq z, then x\leq z (transitivity).

We say that x is covered by y, written x\lessdot y, if x<y and there is no  z such that x<z<y. Two posets P,Q are isomorphic  if  there is a bijection \phi:P\to Q that is order-persverin; that is, x\leq y in P iff \phi(x)\leq \phi(y) in Q.

We’ll usually assume that P is finite.

Ranked posets

Definition A chain x_0<x_1<\dots<x_n is saturated if it is not properly contained in any other chain from x_0 to x_n; equivalently, if x_{i-1}\lessdot x_i for every i\in [n]. In this case, the number n is the length of the chain. A poset P is ranked if for every x\in P, all saturated chains with top element x have the same length; this number is called the rank  of x and denoted r(x).  A poset is graded if it is ranked and bounded.

Definition Let P be a ranked set with rank function r. The rank-generating function  of P is the formal power series

\displaystyle F_p(q):=\sum_{x\in P}q^{r(x)}.

Simplicial complexes

Definition Let V be a finite set of vertices. An simplicial complex \Delta on V is a nonempty family of subsets of V with the property that if \sigma\in\Delta and \tau\subset\sigma, then \tau\in\Delta. Equivalently, \Delta is an order ideal in the Boolean algebra 2^V. The element of \Delta are called its faces or simplices.

The incidence algebra of a poset

Let P be a poset and let \mathrm{Int}(P) denote the set of (nonempty) intervals of P, i.e., the sets

\displaystyle [x,y]:=\{z\in P:x\leq z\leq y\}

for all x\leq y.

We will always assume that p is locally finite, i.e., every interval is finite.

Definition (Incidence algebra) The incidence algebra is the set of funciton f:\mathrm{Int}(P)\to\mathbf{C} (“incidence funcitons”), made into a \mathbf{C}-vector space with pointwise addition, subtraction and scalar multiplication, and equipped with the convolution product 

\displaystyle (f*g)(x,y)=\sum_{z\in[x,y]}f([x,z])g([z,y]).

It is often convenient to set f(x,y)=0 if  x\nleqslant y. Note that the assumption of local finiteness is both necessary and sufficient for convolution to be well-defined.

Proposition Convolution is associative (although it is not in general commutative).

Proposition An incidence function f\in I(P) has a left/right two side side-convolution inverse if and only if f([x,x])\neq 0 for all x. In that case, the inverse is given by the formula

\displaystyle f^{-1}([x,y])=\begin{cases} f([x,x])^{-1} & \text{if}\ x=y,\\  -f([y,y])^{-1}\sum_{z:x\leq z<y} f^{-1}(x,z)f(z,y)& \text{if}\ x<y.  \end{cases}




Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s