Dimension of CPT posets
share
A containment model M_P of a poset P=(X,≼) maps every x ∈ X to a set M_x such that, for every distinct x,y ∈ X,x ≼ y if and only if M_x M_y. We shall be using the collection (M_x)_x ∈ X to identify the containment model M_P. A poset P=(X,≼) is a Containment order of Paths in a Tree (CPT poset), if it admits a containment model M_P=(P_x)_x ∈ X where every P_x is a path of a tree T, which is called the host tree of the model. In this paper, we give an asymptotically tight bound on the dimension of a CPT poset, which is tight up to a multiplicative factor of (2+ϵ), where 0 < ϵ < 1, with the help of a constructive proof. We show that if a poset P admits a CPT model in a host tree T of maximum degree Δ and radius r, then dim(P) ≤ 2_2_2Δ +2_2r+3.
READ FULL TEXT