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

  • 1
    $\begingroup$ Could you tell us what a "DAG" is? $\endgroup$ – Tom De Medts Jul 13 '12 at 10:29
  • 3
    $\begingroup$ Probably "directed acyclic graph". $\endgroup$ – Joel David Hamkins Jul 13 '12 at 10:35
  • $\begingroup$ In the sentence beginning "clearly", I think you want to set the labels to be the set of its own id and the ids of the vertices that can reach this vertex, rather than the vertices reachable from this vertex, in order for the containment to go in the correct order. $\endgroup$ – Joel David Hamkins Jul 13 '12 at 11:44
  • $\begingroup$ Joel David Hamkins: you're right, I switched the variable order in the condition to fix this. $\endgroup$ – a3nm Jul 13 '12 at 11:56

Perhaps it is helpful to mention that an equivalent formulation of your question concerns partial orders rather than graphs.

Namely, if $(V,E)$ is a directed acylic graph, then your reachability relation $\to^+$ is transitive and irreflexive, and hence it is a (strict) partial order. And conversely every partial order is realized as an instance of $\to^+$ for a directed acyclic graph.

Thus, an equivalent formulation of your question inquires about the smallest $n$ for which a given partial order embeds into the power set lattice $\langle P(\{1,\ldots,n\}),{\subset}\rangle$.

  • $\begingroup$ Thanks for this insight! Do you know of any study of this equivalent problem? $\endgroup$ – a3nm Jul 13 '12 at 11:56
  • $\begingroup$ A benefit to this view is that various classes of posets may have been handled -- for example, for finite lattices I think you could use the set of join irreducibles less than or equal to an element $x$ as the label for $x$. You can adjoin a unique source if you don't already have one. $\endgroup$ – Patricia Hersh Jul 13 '12 at 12:07
  • $\begingroup$ There are some interesting related ideas at this question: mathoverflow.net/questions/25874/… $\endgroup$ – Joel David Hamkins Jul 13 '12 at 12:15

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.