Dimension of CPT Posets

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 1-element and 2-element 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]

IITH Creators: