edit this page

1. Definition

A partially ordered set (poset) is a set $P$ together with a partial order $\leq$ 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 48 statistics in the database:

St000068
Posets ⟶ ℤ
The number of minimal elements in a poset.
St000069
Posets ⟶ ℤ
The number of maximal elements of a poset.
St000070
Posets ⟶ ℤ
The number of antichains in a poset.
St000071
Posets ⟶ ℤ
The number of maximal chains in a poset.
St000080
Posets ⟶ ℤ
The rank of the poset.
St000100
Posets ⟶ ℤ
The number of linear extensions of a poset.
St000104
Posets ⟶ ℤ
The number of facets in the order polytope of this poset.
St000151
Posets ⟶ ℤ
The number of facets in the chain polytope of the poset.
St000180
Posets ⟶ ℤ
The number of chains of a poset.
St000181
Posets ⟶ ℤ
The number of connected components of the Hasse diagram for the poset.
St000189
Posets ⟶ ℤ
The number of elements in the poset.
St000281
Posets ⟶ ℤ
The size of the preimage of the map 'to poset' from Binary trees to Posets.
St000282
Posets ⟶ ℤ
The size of the preimage of the map 'to poset' from Ordered trees to Posets.
St000298
Posets ⟶ ℤ
The order dimension or Dushnik-Miller dimension of a poset.
St000307
Posets ⟶ ℤ
The number of rowmotion orbits of a poset.
St000327
Posets ⟶ ℤ
The number of cover relations in a poset.
St000524
Posets ⟶ ℤ
The number of posets with the same order polynomial.
St000525
Posets ⟶ ℤ
The number of posets with the same zeta polynomial.
St000526
Posets ⟶ ℤ
The number of posets with combinatorially isomorphic order polytopes.
St000527
Posets ⟶ ℤ
The width of the poset.
St000528
Posets ⟶ ℤ
The height of a poset.
St000550
Posets ⟶ ℤ
The number of modular elements of a lattice.
St000551
Posets ⟶ ℤ
The number of left modular elements of a lattice.
St000632
Posets ⟶ ℤ
The jump number of the poset.
St000633
Posets ⟶ ℤ
The size of the automorphism group of a poset.
St000634
Posets ⟶ ℤ
The number of endomorphisms of a poset.
St000635
Posets ⟶ ℤ
The number of strictly order preserving maps of a poset into itself.
St000639
Posets ⟶ ℤ
The number of relations in a poset.
St000640
Posets ⟶ ℤ
The rank of the largest boolean interval in a poset.
St000641
Posets ⟶ ℤ
The number of non-empty boolean intervals in a poset.
St000642
Posets ⟶ ℤ
The size of the smallest orbit of antichains under Panyushev complementation.
St000643
Posets ⟶ ℤ
The size of the largest orbit of antichains under Panyushev complementation.
St000656
Posets ⟶ ℤ
The number of cuts of a poset.
St000680
Posets ⟶ ℤ
The Grundy value for Hackendot on posets.
St000717
Posets ⟶ ℤ
The number of ordinal summands of a poset.
St000845
Posets ⟶ ℤ
The maximal number of elements covered by an element in a poset.
St000846
Posets ⟶ ℤ
The maximal number of elements covering an element of a poset.
St000848
Posets ⟶ ℤ
The balance constant multiplied with the number of linear extensions of a poset.
St000849
Posets ⟶ ℤ
The number of 1/3-balanced pairs in a poset.
St000850
Posets ⟶ ℤ
The number of 1/2-balanced pairs in a poset.
St000906
Posets ⟶ ℤ
The length of the shortest maximal chain in a poset.
St000907
Posets ⟶ ℤ
The number of maximal antichains of minimal length in a poset.
St000908
Posets ⟶ ℤ
The length of the shortest maximal antichain in a poset.
St000909
Posets ⟶ ℤ
The number of maximal chains of maximal size in a poset.
St000910
Posets ⟶ ℤ
The number of maximal chains of minimal length in a poset.
St000911
Posets ⟶ ℤ
The number of maximal antichains of maximal size in a poset.
St000912
Posets ⟶ ℤ
The number of maximal antichains in a poset.
St000914
Posets ⟶ ℤ
The sum of the values of the Möbius function of a poset.

5. Maps

We have the following 6 maps in the database:

Mp00013
Binary trees ⟶ Posets
to poset
Mp00047
Ordered trees ⟶ Posets
to poset
Mp00065
Permutations ⟶ Posets
permutation poset
Mp00074
Posets ⟶ Graphs
to graph
Mp00110
Posets ⟶ Integer partitions
Greene-Kleitman invariant
Mp00125
Posets ⟶ Posets
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