Posets (Partially Ordered Sets)

Contents

# 1. Definition

A * partially ordered set (often called a poset)* is a set $P$ together with a partial order $\leq = \leq_P$ satisfying

$\leq$ is

*reflexive*: $x \leq x$ for all $x \in P$,$\leq$ is

*transitive*, $x \leq y \leq z$ implies $x \leq z$ for all $x,y,z \in P$,$\leq$ is

*antisymmetric*, $x \leq y \Rightarrow y \not\leq x$ for $x,y \in P$ such that $x \neq y$.

## 1.1. Notations

$x,y \in P$ are called

*comparable*if $x \leq y$ or $y \leq x$. A poset is called*linear*,*linearly ordered*, or*totally ordered*if any two elements are comparable.$x

$x \prec y$ if $x < y$ and there does not exist an element $z \in P$ such that $x < z < y$. In this case, $(x,y)$ is a

*cover relation*in $P$, and*y covers x*[Wei14],$x \in P$ is

*minimal*if there is no $y \in X$ such that $y \leq x$,$x \in P$ is

*maximal*if there is no $y \in X$ such that $x \leq y$.A subset $X$ of $P$ is called

*chain*if it is pairwise comparable, and*antichain*if it is pairwise not comparable. A*maximal chain*is containment-maximal chain.An

*order ideal*or*down-closed set*is a subset $X$ of $P$ such that $x \leq y \in X$ implies $x \in X$. There is a one-to-one correspondence between order ideals and antichains.

## 1.2. Hasse diagram

Finite posets are often represented by their **Hasse diagram**. This is the directed graph with vertices $P$ and with directed edges $x \rightarrow y$ if $x \prec y$.

## 1.3. Poset isomorphism

Two posets $(P,\leq_P)$ and $(P',\leq_{P'})$ are *isomorphic* if there exists a bijection $\pi: P \tilde\rightarrow P'$ such that $x \leq_P y$ if and only if $\pi(x) \leq_{P'} \pi(y)$ for all $x,y \in P$.

# 2. Examples

## 2.1. Nonisomorphic Posets of Order $n$

**Posets of Order 3:**

**Posets of Order 4:**

* The number of nonisomorphic posets on $n$ elements is OEIS:A000112.

## 2.2. Specific Poset Examples

**The poset of subset of $\{1,2,3\}$ ordered by inclusion:**

**Hasse Diagram for the partial order given by divisibility on $\{1,2,3,4,5,6,7,8,9,10,11,12\}$:**

# 3. Remarks

## 3.1. Extensions of Posets

Let $P$ be a set with two partial orders $\leq_1$ and $\leq_2$. Then $\leq_2$ is an

*extension*of $\leq_1$ if $x \leq_1 y$ implies $x \leq_2 y$.Linear extensions of posets play a particularly important role, see [Sta10].

Order Dimension, or Dushnik-Miller Dimension, is defined as the minimum number of linear extensions, whose intersection is the poset Wikipedia:Order dimension.

## 3.2. Rowmotion

A rowmotion is an operation on an order ideal of some poset $P$. Given some order ideal $I$, a rowmotion is defined by finding the order ideal generated by the minimal antichain of $P \setminus I$. [StWi12]

# 4. Statistics

We have the following **35 statistics** in the database:

# 5. Maps

We have the following **3 maps** in the database:

# 6. References

*Partial orders and equivalence relations*, Combinatorics Fifth Edition (2010).

[Sta10] R. Stanley, *Enumerative Combinatorics Vol 1, Second edition*, Cambridge Studies in Advanced Mathematics (2011).

[StWi12] J. Striker and N. Williams, *Promotion and Rowmotion*, European Journal of Combinatorics Volume 8 (2012).

# 7. Sage Examples