Generalization of Dilworth's theorem for labeled DAGs

Question

An antichain in a DAG $(V, E)$ is a subset $A \subseteq V$ of vertices that are pairwise unreachable, namely, there are no $v \neq v' \in A$ such that $v$ is reachable from $v'$ in $E$. From Dilworth's theorem in partial order theory, it is known that if DAG has no antichain of size $k \in \mathbb{N}$, then it can be decomposed in a union of at most $k-1$ disjoint chains, i.e., directed paths.

Now, I am interested in labeled DAGs, i.e., DAGs where each vertex $v$ carries a label $\lambda(v)$ in some fixed finite set $\Sigma$ of labels. Given an antichain $A \subseteq V$, I can define its labeled size as the minimal number of occurrences of the labels of $\Sigma$ in $A$, namely, $\min_{a \in \Sigma} |\{v \in A \mid \lambda(v) = a\}|$. Is there an analogue of Dilworth's theorem in this context? In other words, if I assume that a DAG has no antichain of labeled size $k \in \mathbb{N}$, what can I assume about its structure? Can I decompose it in some special way? I am already puzzled by the case of $\Sigma = \{a, b\}$, but also interested in the case of a general finite label set.

To visualize this for $\Sigma = \{a, b\}$, saying that $G$ has no antichain of labeled size $k$ means that there is no antichain containing at least $k$ vertices labeled $a$ and $k$ vertices labeled $b$; there can be arbitrarily large antichains but they have to contain only $a$ elements or only $b$ elements, up to $k-1$ exceptions at most. It seems that disallowing large antichains should enforce that the DAG essentially "alternates" between parts of large width for $a$-labeled vertices, and large width for $b$-labeled vertices, but I have not been able to formalize this intuition. (Of course, a suitable structural characterization must talk about the labels of vertices in addition to the shape of the DAG, because already for $k \geq 1$ and on $\{a, b\}$ the condition is satisfied by completely arbitrary DAGs whenever all vertices carry the same label.)

Answer 1

With Charles Paperman we have been able to obtain such a result for DAGs labeled with the alphabet $\{a, b\}$. Essentially, we can show that given a DAG $G$ that has large antichains of $a$-labeled elements, large antichains of $b$-labeled elements, but no large antichains containing both many $a$-labeled and $b$-labeled elements, then there is a decomposition of $G$ as a partition $L_1, \ldots, L_n$, where:

• the partition $L_1, ..., L_n$ is what we call a "layering", i.e.:
  • each $L_i$ is a convex set, i.e., if $x, y \in L_i$ and $x \leq z \leq y$ then $z \in L_i$
  • for all $i < j$, there is no $x \in L_i$ and $y \in L_j$ such that $y \leq x$
• for any antichain $A$ of $G$, there is some $i$ such that $A$ is "almost contained" in $L_i$, i.e., $|A \setminus L_i|$ is less than a constant
• for each $L_i$, one of the following is true:
  • $L_i$ contains a large antichain of $a$-labeled elements and contains no large antichain of $b$-labeled elements
  • $L_i$ contains a large antichain of $b$-labeled elements but contains no large antichain of $a$-labeled elements

Further, such a partition can be computed in PTIME.

I have posted our current proof online. It's very rough and essentially not proofread because we have no use for the result for now, but I still thought it was tidier to add an answer to this CStheory question with our current progress. Don't hesitate to get in touch with me if you're interested in the result but can't make sense of the proof.