Is there a nice characterization of posets induced by trees?

439 Views Asked by At

Define that a tree in $X$ is a set of ordinal-indexed sequences with codomain $X$ that is closed under the operations of restricting to an ordinal. (I do not know if this definition is standard.)

Under this definition, every tree induces a poset in a natural way. Is there a nice characterization of posets induced by trees? I feel like there probably should be, but I can't think of one.

Furthermore, every such poset induces a comparability graph. Is there a nice characterization of the comparability graphs of posets induced by trees?

1

There are 1 best solutions below

0
On

As mentioned in the comments, a poset $P$ comes from a tree in this sense iff for each $p\in P$, the set $\{q\in P:q<p\}$ is well-ordered. The reverse direction is obvious: given a tree in your sense and an element $p:\alpha\to X$ of it, $\{q\in P:q\leq p\}$ is just the set of restrictions of $p$ to ordinals $\beta<\alpha$, and this set is isomorphic to $\alpha$ and hence well-ordered.

For the forward direction, suppose $P$ is a poset such that $\{q\in P:q<p\}$ is well-ordered for all $p\in P$. Let $\alpha_p\in Ord$ be the order-type of $\{q\in P:q<p\}$ and let $f_p:\alpha_p\to P$ be the unique order-preserving injection with image $\{q\in P:q<p\}$. The set $\{f_p:p\in P\}$ is then a tree in $P$ in your sense, which is isomorphic to $P$ via $p\mapsto f_p$.