22923 - Remarks on the Poset of the Posets

N. Lygeros

Let’s consider the poset of all posets on n elements where the partial order is that of inclusion of comparabilities. If P is a poset, a subposet of P is a subset of P with the induced order. The width w(P) of P is the maximal number of elements of an antichain of P. Dilworth showed that w(P) equals the minimum number of chains in a partition of P into chains. Duffus, Rival and Winkler proved the following lemma. A poset which does not have a subposet isomorphic to a cycle is a D-poset. A poset P in N-free if P contains no cover-preserving subposet isomorphic to the poset N. Rival proved that every N-free poset is greedy. By the way, a Theorem of Hiraguchi says that removing one point from a poset decreases its dimension by at most one. Trotter summarizes all those points by saying that removing one point from a poset doesn’t increase any of the parameters width, height, jump number and dimension and can decrease each of them by at most one. There is no analogy with removing one comparability as the general result is not a poset. So only a comparability which cannot recover by transitivity can be removed. Trotter proved that if Q is a subposet of P in the poset of posets of order n, then h(P)-1 ≤ h (Q) ≤h(P) and w(P)≤w(Q)≤w(P)+1. And Pouzet and Rival showed that: dimP-1≤dim Q≤dimP+1. And Trotter proved that: int(n/2)( int(n/2)+1) ≤dim Pn ≤ n(n-1).