I define a *$n$-labeling* of a directed acyclic graph $G = (V, E)$ as a function $f$ from $V$ to the power set of {1, ..., $n$} such that for any $x, y \in V$, $x \neq y$, we have $f(y) \subset f(x)$ iff $x \rightarrow^+ y$ (i.e. there is a path of length >0 from $x$ to $y$ in $G$). Clearly, any DAG $G$ admits a $|V|$-labeling (by assigning a unique id to each vertex and setting each vertex's label as the set of its own id and the ids of vertices reachable from this vertex), but this upper bound is not tight (for instance a perfect binary tree of height $h$ has $2^{h+1} - 1$ vertices but admits a $2^h$-labeling by assigning a unique number to each leaf). Hence my question: Given a graph $G$, what is the smallest $n$ such that there exists an $n$-labeling of $G$?

(This problem seems related to things such as comparability graphs and geometric containment orders, but I could not find the exact terms. It seems likely to me that this problem is already known with a different terminology, so I'd be happy to get relevant references if you know some.)

(Another possible choice of condition would be: for any $x, y \in V$, we have $f(y) \subsetneq f(x)$ iff $x \rightarrow^+ y$. It's not equivalent (it allows some nodes with the same children to carry the same labels) and I'm not sure of which one is the more natural.)

fromthis vertex, in order for the containment to go in the correct order. $\endgroup$ – Joel David Hamkins Jul 13 '12 at 11:44