Majumder, A and Mathew, R and et al, .
(2021)
Dimension of CPT Posets.
Order.
ISSN 01678094
Full text not available from this repository.
(
Request a copy)
Abstract
A collection of linear orders on X, say L, is said to realize a partially ordered set (or poset) P= (X, ≼) if, for any two distinct x,y ∈ X, x ≼ y if and only if x ≺Ly, ∀ L∈ L. We call L a realizer of P. The dimension of P, denoted by dim(P) , is the minimum cardinality of a realizer of P. A containment modelMP of a poset P= (X, ≼) maps every x ∈ X to a set Mx such that, for every distinct x,y ∈ X, x ≼ y if and only if Mx⫋ My. We shall be using the collection (Mx)x∈X to identify the containment model MP. A poset P= (X, ≼) is a Containment order of Paths in a Tree (CPT poset), if it admits a containment model MP=(Px)x∈X where every Px is a path of a tree T, which is called the host tree of the model. 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)≤lglgΔ+(12+o(1))lglglgΔ+lgr+12lglgr+12lgπ+3. This bound is asymptotically tight up to an additive factor of min(12lglglgΔ,12lglgr). Further, let P(1 , 2 ; n) be the poset consisting of all the 1element and 2element subsets of [n] under ‘containment’ relation and let dim(1,2;n) denote its dimension. The proof of our main theorem gives a simple algorithm to construct a realizer for P(1 , 2 ; n) whose cardinality is only an additive factor of at most 32 away from the optimum.
[error in script]
Actions (login required)

View Item 