Possible database queries for posets: search your data / browse all statistics / browse all maps
1. Definition & Example
A (finite) poset (or partially ordered set) is a finite set $P$ together with a partial order $\leq$ 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$,
One often writes $a < b$ for $a \leq b$ and $a \neq b$.
A cover relation $a \prec b$ is a pair of elements $a < b$ such that there exists no $c \in P$ for which $a < c < b$ [Wei14].
The five unlabelled posets on 3 elements with their canonical labelling |
||||
([],3) |
([(1,2)],3) |
([(0,1),(0,2)],3) |
([(0,2),(2,1)],3) |
([(0,2),(1,2)],3) |
Posets are graphically represented by their Hasse diagram which is the directed graph of cover relations.
Two posets $(P,\leq_P)$ and $(P',\leq_{P'})$ are isomorphic if there exists a bijection $\pi: P\ \tilde\longrightarrow\ P'$ such that $x \leq_P y$ if and only if $\pi(x) \leq_{P'} \pi(y)$ for all $x,y \in P$.
This project considers unlabelled posets. This is, two posets are considered to be equal if they are isomorphic.
For the number of unlabelled posets see OEIS:A000112.
2. Additional information
2.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 \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.
2.2. 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].
3. References
[Sta10] R. Stanley, Enumerative Combinatorics Vol 1, Second edition, Cambridge Studies in Advanced Mathematics (2011).
4. Sage examples
5. Technical information for database usage
A poset is uniquely represented as a tuple (E,n) where E is the sorted list of cover relations and n is the number of elements. For this representation, we consider a canonical labelling of a poset. This is, a labelling of the elements by $\{0,1,\ldots,n-1\}$ such that any two posets are isomorphic if and only if their canonical labellings coincide.
- Posets are graded by the number of elements.
- The database contains all posets of size at most 7.