Definitions: Posets

Definition 2.5 (Poset)

A poset $ (S,\le) $ is a finite partially ordered set, that is, a finite set equipped with a relation "$ \le $" which is

reflexive: $ (x \le x \text{ for all } x \in S) $
transitive: $ (x \le y \text{ and } y \le z \Rightarrow x \le z) $
antisymmetric: $ (x \le y \text{ and } y \le x \Rightarrow x=y) $.

Additionally a poset is denoted by $S$, when the partial order is clear. Note that any subset of $S$ is also a poset, with the induced partial order.

Example

Take the following triangle

The faces are

The whole triangle: $P$
The edges: $ab,bc,ac$
The vertices: $a,b,c$
The empty face: $\emptyset$

This makes a partially ordered set with order relation $\subseteq$.

Chain

A chain in $S$ is a totally ordered subset of $S$. The length is its number of elements minus $1$.

In the triangle above, an example of a chain is

$$ \begin{align*} \emptyset \subset a \subset ab \subset P \end{align*} $$

Interval

For elements $x,y$ in a poset $S$ with $x \le y$, we denote by $$ [x,y] := \{\,w \in S : x \le w \le y\,\} $$ the interval between $x$ and $y$.

Additionally, an interval in $S$ is boolean if it is isomorphic to the poset

$$ B_k=(2^{[k]},\subseteq) $$

of all subsets of a $k$-element set, for some $k$.

Bounded Poset

A poset is bounded if it has a unique minimal element, denoted $ \hat 0 $, and a unique maximal element, denoted $ \hat 1 $. The proper part of a bounded poset $ S $ is $$ \overline{S}:=S\setminus\{\hat 0,\hat 1\}. $$

Is the triangle poset above bounded?

It has a unique minimal element $\hat{0} = \emptyset$
It has a unique maximal element $\hat{1} = P$

So it is bounded by the definition above.

Graded Poset

A poset is graded if it is bounded, and every maximal chain has the same length. In this case the length of a maximal chain in the interval $ [\hat 0,x] $ is the rank of $ x $, denoted by $ r(x) $. The rank $$ r(S):=r(\hat 1) $$ is also called the length of $ S $.

In the triangle example, the maximal chains are all of the same length. One example is $$ \begin{align*} \emptyset \subset a \subset ab \subset P \end{align*} $$

The length of this maximal chain in $[\hat{0},P]$ is the rank of $P$. We know the length is the number of elements minus 1 so its length is $3$ which is also the rank of $P$. Since it’s bounded and all the maximal chains are of the same length, then it is a graded poset by definition.

Note that once we establish that every maximal chain has the same length, then the definition of rank becomes well-defined. So we must establish every that $L(P)$ is a graded poset before talking about the rank.

Lattice

A poset is a lattice if it is bounded, and every two elements $ x,y \in S $ have a unique minimal upper bound in $ S $, called the join $x \vee y,$ and every two elements $ x,y \in S $ have a unique maximal lower bound in $ S $, called the meet $x \wedge y.$

So take two elements $a$ and $b$ in the triangle example. An upper bound is any element that is above both $a$ and $b$. For example, $ab$ and $P$ are both upper bounds. The least upper bound however is $ab$ and therefore it is unique. We call this a join. Notice that in the triangle example, for every two elements, we can also find a unique minimal upper bound (join) and a unique maximal lower bound (meet). Hence the triangle poset is a lattice.

Atoms and Coatoms

If $ S $ is a graded lattice, then the minimal elements of $ S\setminus\{\hat 0\} $ are called its atoms, and the maximal elements of $ S\setminus\{\hat 1\} $ are called its coatoms. Equivalently, the atoms are the elements of rank $ 1 $, and the coatoms are the elements of rank $ r(S)-1 $.

Notice that in the triangle example, the atoms are $a$, $b$ and $c$. The coatoms in this case are $ab, ac$ and $bc$.

Atomic and Coatomic lattices

A lattice is atomic if every element is a join $$ x=a_1\vee\cdots\vee a_k $$ of atoms. Similarly, a lattice is coatomic if every element is a meet of coatoms.

Opposite Poset

The opposite poset $ S^{op} $ (or order dual) has the same underlying set as $ S $, with $$ x \le y \text{ in } S^{op} \iff y \le x \text{ in } S. $$

Cover Relations

A cover relation is a relation $ x \prec y $ such that $$ x < y \quad\text{and}\quad [x,y]=\{x,y\}. $$

For example $a \prec ab$ is a cover relation since there are no faces between $a$ and $ab$. However $a \prec P$ is not a cover relation.

Definition 2.6 (Face Lattice)

The face lattice of a convex polytope $P$ is the poset $L := L(P)$ of all faces of $P$, partially ordered by inclusion

In this example, the face lattice is

$$ \begin{align*} L(P) = \{ \emptyset, a,b,c,ab,ac,bc,P\} \end{align*} $$

References

Lectures on Polytopes