Dimension of CPT posets (Q2663165)

The dimension of a poset \((X, \le)\), \(\dim X\), is the minimum cardinality of a collection \((\le_i: i \in I)\) of linear orders on \(X\) such that \(x \le y\) iff \(x \le_i y\) for all \(i \in I\); such a collection is called a realizer of \((X, \le)\). A CPT poset is a poset \((X, \le\)) which is isomorphic to a poset (called a CPT model of \(X\)) consisting of paths of some tree (the host tree) and ordered by inclusion. The main theorem gives an upper estimation for the dimension of a CPT poset modeled by the set of all paths of a rooted tree where every internal vertex has exactly \(k\) children. An upper estimation of \(\dim X\) for a poset \(X\) admitting a CPT model in a host tree of a given radius and maximum degree is obtained as a corollary. The proof of the theorem gives an algorithm for constructing a realizer, under inclusion relation, for the poset consisting of all 1-element and 2-element subsets of \(\{1,2,\dots,n\}\) .