Dimension of CPT posets

Abstract

A collection of linear orders on $X$, say $\mathcal{L}$, is said to \emph{realize} a partially ordered set (or poset) $\mathcal{P}=(X,⪯)$ if, for any two distinct $x,y\in X$, $x⪯y$ if and only if $x{\prec }_{L}y$, $\forall L\in \mathcal{L}$. We call $\mathcal{L}$ a \emph{realizer} of $\mathcal{P}$. The \emph{dimension} of $\mathcal{P}$, denoted by $dim(\mathcal{P})$, is the minimum cardinality of a realizer of $\mathcal{P}$. A \emph{containment model} $M_{\mathcal{P}}$ of a poset $\mathcal{P}=(X,⪯)$ maps every $x\in X$ to a set $M_x$ such that, for every distinct $x,y\in X,x⪯y$ if and only if $M_xM_y$. We shall be using the collection $(M_x{)}_{x\in X}$ to identify the containment model $M_{\mathcal{P}}$. A poset $\mathcal{P}=(X,⪯)$ is a Containment order of Paths in a Tree (CPT poset), if it admits a containment model $M_{\mathcal{P}}=(P_x{)}_{x\in X}$ 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 $\mathcal{P}$ admits a CPT model in a host tree $T$ of maximum degree $\Delta$ and radius $r$, then \rogers{$dim(\mathcal{P})\le \lg \lg \Delta +(\frac{1}{2}+o(1))\lg \lg \lg \Delta +\lg r+\frac{1}{2}\lg \lg r+\frac{1}{2}\lg \pi +3$. This bound is asymptotically tight up to an additive factor of $\min (\frac{1}{2}\lg \lg \lg \Delta ,\frac{1}{2}\lg \lg r)$. Further, let $\mathcal{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 $\mathcal{P}(1,2;n)$ whose cardinality is only an additive factor of at most $\frac{3}{2}$ away from the optimum.

10 Pages