Generalization of Dilworth's theorem for labeled DAGs
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 &lt; 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.