Polyhedral Subdivisions and Projections of Polytopes Jörg Rambau Dissertation (Advisor: Günter M. Ziegler, TU Berlin)

   
Partially Ordered Sets

The notation used in this section is based on the book of STANLEY [68, Chapter III].

Definition 4.1.1   Let $S$ be a finite set. A   partial order on $S$ is a binary relation ``$\le$'' on $S$ that is reflexive, antisymmetric, and transitive. That is,

(i)

$x \le x$ for all $x \in S$,

(ii)

$x \le y$ and $y \le x$ implies $x = y$, and

(iii)

$x \le y$ and $y \le z$ implies $x \le z$.

The pair $\mathcal{S} = (S, \le)$ is called a   partially ordered set, or a   poset, for short. Consider a binary relation ``$<$'' on $S$ that is irreflexive, antisymmetric, and acyclic. That is,

(i)

$x \nless x$ ($x$ is not related to $x$ by ``$<$'') for all $x \in S$,

(ii)

$x < y$ implies $y \nless x$, and

(iii)

there is no chain of relations $x < \dots < x$.

Then the   transitive closure ``$\le$'' of ``$<$'' is the partial order given by

$$x \le y :\iff \text{either} \quad x = y \quad \text{or} \qua... ...ts < x_r = y \quad \text{for some $x_1, \dots, x_r \in S$ }.$$

A   chain in $\mathcal{S}$ is a totally ordered subset of $S$. Its   length is the number of elements minus one. The   interval $[x,y]$ in $\mathcal{S}$ is the set of all $z \in S$ with $x \le z$ and $z \le y$ with the induced partial order. If $[x,y] = (\{ x, y \}, \le )$ then $y$ is a   cover of $x$ and $x \lessdot y$ denotes the corresponding   covering relation. $\mathcal{S}$ is   bounded if there is a unique   maximal and a unique   minimal element in $\mathcal{S}$, that means, if $\mathcal{S} = [\Hat{0}, \Hat{1}]$ for suitable $\Hat{0}$ and $\Hat{1}$ in $S$. $\mathcal{S} \sm \{ \Hat{0}, \Hat{1} \}$ is called the   proper part of $\mathcal{S}$. $\mathcal{S}$ is   graded, or   ranked, if it is bounded and every maximal chain has the same length. The length of a maximal chain in $[\Hat{0}, x]$ is the   rank of $x$. The   rank of $\mathcal{S}$ is the rank of $\Hat{1}$.

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

The minimal elements of the proper part of a graded lattice are called   atoms, the maximal elements   coatoms. If every element in $S$ is the join of atoms in $\mathcal{S}$ then $\mathcal{S}$ is   atomic. $\mathcal{S}$ is   coatomic if every element in $S$ is the meet of coatoms in $\mathcal{S}$.

Definition 4.1.2   A map $f: (S, \le_S) \to (R, \le_R)$ is   order-preserving, respectively   order-reversing, if $f(x) \le_R f(y)$, respectively $f(y) \le_R f(x)$, for all $x \le_S y$ in $S$.   Isomorphisms are order-preserving,   anti-isomorphisms are order-reversing bijections in the category of posets.

Definition 4.1.3   The   Hasse diagram of a poset $\mathcal{S} = (S, \le)$ is a directed graph with vertex set $S$. Two vertices $x$ and $y$ in $S$ are connected by an arc from $x$ to $y$ if and only if $y$ covers $x$. In a drawing of this graph usually all arcs are directed upwards, whence the arrows are omitted.

The following example will appear in much more general form in Sections 3.7 and 3.8.

Example 4.1.4   Let $S_n$ be the set of all permutations on $n$ elements, where $[n] = \{ 1, \dots , n \}$ is linearly ordered with $1 < \dots < n$. For a permutation $\pi$, let $\inv (\pi )$ be the set of all pairs $(i,j)$ with $1 \le i < j \le n$ and $\pi (i) > \pi (j)$. We set $\pi \le \sigma$ if and only if $\inv (\pi ) \subseteq \inv (\sigma )$. The poset $(S_n, \le)$ is the   weak (Bruhat) order on $S_n$.

We end this section with a definition of the   order complex of a poset, which is the standard translation of combinatorial structures into topology.

Definition 4.1.5   Let $\mathcal{S} = (S, \le)$ be a poset. The (abstract) simplicial complex (see Section A.4)

$$\Delta (\mathcal{S}) := \setof{R \subset S}{\text{$R$\space is a chain in $\mathcal{S}$ }}$$

is the   order complex of  $\mathcal{S}$.