Posets (Partially Ordered Sets)

1. Definition

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

See [Bru10] and [Sta10].

1.1. Notations

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__3-1.png

Posets__3-2.png

Posets__3-3.png

Posets__3-4.png

Posets__3-5.png

Posets of Order 4:

Posets__4-1.png

Posets__4-2.png

Posets__4-3.png

Posets__4-4.png

Posets__4-5.png

Posets__4-6.png

Posets__4-7.png

Posets__4-8.png

Posets__4-9.png

Posets__4-10.png

Posets__4-11.png

Posets__4-12.png

Posets__4-13.png

Posets__4-14.png

Posets__4-15.png

Posets__4-16.png

* 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:

Subset 3 Hasse Diagram.png

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

Divides 12 Hasse Diagram.png

3. Remarks

3.1. Extensions of Posets

3.2. Rowmotion

4. Statistics

We have the following 39 statistics in the database:

The number of minimal elements in a poset.
The number of maximal elements of a poset.
The number of antichains in a poset.
The number of maximal chains in a poset.
The rank of the poset.
The number of linear extensions of a poset.
The number of facets in the order polytope of this poset.
The number of facets in the chain polytope of the poset.
The number of chains of a poset.
The number of connected components of the Hasse diagram for the poset.
The number of elements in the poset.
The size of the preimage of the map 'to poset' from Binary trees to Posets.
The size of the preimage of the map 'to poset' from Ordered trees to Posets.
The order dimension or Dushnik-Miller dimension of a poset.
The number of rowmotion orbits of a poset.
The number of cover relations in a poset.
The number of posets with the same order polynomial.
The number of posets with the same zeta polynomial.
The number of posets with combinatorially isomorphic order polytopes.
The width of the poset.
The height of a poset.
The number of modular elements of a lattice.
The number of left modular elements of a lattice.
The jump number of the poset.
The size of the automorphism group of a poset.
The number of endomorphisms of a poset.
The number of strictly order preserving maps of a poset into itself.
The number of relations in a poset.
The rank of the largest boolean interval in a poset.
The number of non-empty boolean intervals in a poset.
The size of the smallest orbit of antichains under Panyushev complementation.
The size of the largest orbit of antichains under Panyushev complementation.
The number of cuts of a poset.
The Grundy value for Hackendot on posets.
The number of ordinal summands of a poset.
The maximal number of elements covered by an element in a poset.
The maximal number of elements covering an element of a poset.
The balance constant multiplied with the number of linear extensions of a poset.
The number of 1/3-balanced pairs in a poset.

5. Maps

We have the following 3 maps in the database:

to graph
Greene-Kleitman invariant
dual poset

6. References

[Bru10]   R. Brualdi, 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).

[Wei14]   E. Weisstein, Cover relation, Math World (2014).

7. Sage Examples

Posets (last edited 2016-05-30 11:19:58 by ChristianStump)