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.)



Minimal labeling of a directed acyclic graph
Joel David Hamkins is right, the question is equivalent to finding the smallest $n$ for which a given partial order embeds into the power set lattice $\langle P(\lbrace 1, ..., n\rbrace), \subset\rangle$. It turns out that this question is well-known: the quantity $n$ is called the 2-dimension (because $n$ is the minimal number of chains of length 2 which realize the order, which is similar to order dimension which works with chains (linear extensions) of arbitrary length).


A recent study of this problem is *Computational aspects of the 2-dimension of partially ordered sets* by M. Habib, L. Nourine, O. Raynaud and E. Thierry. The paper links to various surveys, heuristics and computational results. In particular, it is known that determining the 2-dimension is an NP-complete problem. 


