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)


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:
IITH CreatorsORCiD
Mathew, Rogershttps://orcid.org/ 0000-0003-4536-1136
Item Type: Article
Uncontrolled Keywords: 3-suitable family of permutations, Containment order of paths in a tree, Order dimension, Poset dimension
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Mrs Haseena VKKM
Date Deposited: 09 Dec 2021 09:25
Last Modified: 11 Mar 2022 10:26
URI: http://raiith.iith.ac.in/id/eprint/9067
Publisher URL: https://link.springer.com/article/10.1007%2Fs11083...
OA policy: https://v2.sherpa.ac.uk/id/publication/17431
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9067 Statistics for this ePrint Item