Dimension of CPT posets

DOI10.1007/S11083-020-09524-5MaRDI QIDQ2663165zbMATH OpenOpenAlexFDO

Authors Atrayee Majumder, Rogers Mathew, Deepak Rajendraprasad

Publication date 16 April 2021

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.09326

zbMATH Keywords

order dimensiondimension of a poset3-suitable family of permutationsCPT-poset

Mathematics Subject Classification ID

Trees (05C05) Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07)

Abstract: A collection of linear orders on $X$, say $mathcalL$, is said to emph{realize} a partially ordered set (or poset) $mathcalP=(X,preceq)$ if, for any two distinct $x,yinX$, $xpreceqy$ if and only if $xpre{c}_{L}y$, $forallLinmathcalL$. We call $mathcalL$ a emph{realizer} of $mathcalP$. The emph{dimension} of $mathcalP$, denoted by $dim(mathcalP)$, is the minimum cardinality of a realizer of $mathcalP$. A emph{containment model} $M_{mathcalP}$ of a poset $mathcalP=(X,preceq)$ maps every $xinX$ to a set $M_x$ such that, for every distinct $x,yinX,xpreceqy$ if and only if $M_{x}varsubsetneq{M}_y$. We shall be using the collection $(M_x{)}_{xinX}$ to identify the containment model $M_{mathcalP}$. A poset $mathcalP=(X,preceq)$ is a Containment order of Paths in a Tree (CPT poset), if it admits a containment model $M_{mathcalP}=(P_x{)}_{xinX}$ where every $P_x$ is a path of a tree $T$, which is called the host tree of the model. We show that if a poset $mathcalP$ admits a CPT model in a host tree $T$ of maximum degree $Delta$ and radius $r$, then ogers{$dim(mathcalP)leqlglgDelta+(frac12+o(1))lglglgDelta+lgr+frac12lglgr+frac12lgpi+3$. This bound is asymptotically tight up to an additive factor of $min(frac12lglglgDelta,frac12lglgr)$. Further, let $mathcalP(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 $mathcalP(1,2;n)$ whose cardinality is only an additive factor of at most $frac32$ away from the optimum.

Recommendations

• On dimension of poset variety
• scientific article; zbMATH DE number 3999988
• The dimension of the cartesian product of posets
• A note on the dimension of a poset
• On recognizing the dimension of a poset
• The involutory dimension of involution posets
• Cayley posets
• scientific article; zbMATH DE number 4118416

Cites work

• [article; zbMATH DE number 53952 (Why is no real title available?)]
• [article; zbMATH DE number 6157247 (Why is no real title available?)]
• Angle orders, regular n-gon orders and the crossing number
• Circle orders, n-gon orders and the crossing number
• Containment Graphs, Posets, and Related Classes of Graphs
• Geometric containment orders: A survey
• Interval graphs and interval orders
• On Dedekind's Problem: The Number of Isotone Boolean Functions. II
• Partially Ordered Sets
• Recent results on containment graphs of paths in a tree
• Some theorems on graphs and posets
• The maximum number of edges in a graph of bounded dimension, with applications to ring theory
• The order dimension of the complete graph
• The rank of a distributive lattice

Cited in

(8)

• scientific article; zbMATH DE number 3999988 (Why is no real title available?)
• Containment graphs and posets of paths in a tree: wheels and partial wheels
• Containment orders – a lifelong journey
• Directed tree decompositions
• On containment graphs of paths in a tree
• scientific article; zbMATH DE number 4025488 (Why is no real title available?)
• Recent results on containment graphs of paths in a tree
• On dually-CPT and strongly-CPT posets

This page was built for publication: Dimension of CPT posets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2663165)