Generalización del teorema de Dilworth para DAG etiquetados

Un anticadena en un DAG $(V, E)$ es un subconjunto $A \subseteq V$ de vértices que son pairwise inalcanzable, es decir, no hay $v \neq v' \in A$ tal que $v$ es alcanzable desde $v'$ en $E$ . Por el teorema de Dilworth en la teoría del orden parcial, se sabe que si DAG no tiene una cadena de antemano de tamaño $k \in \mathbb{N}$ , entonces puede descomponerse en una unión de a lo sumo $k-1$ cadenas disjuntas, es decir, caminos dirigidos.

$v$$\lambda(v)$$\Sigma$$A \subseteq V$$\Sigma$$A$$\min_{a \in \Sigma} |\{v \in A \mid \lambda(v) = a\}|$ $k \in \mathbb{N}$, ¿qué puedo asumir sobre su estructura? ¿Puedo descomponerlo de alguna manera especial? Ya estoy desconcertado por el caso de $\Sigma = \{a, b\}$ , pero también estoy interesado en el caso de un conjunto general de etiquetas finitas.

Para visualizar esto para , decir que no tiene una cadena principal de tamaño etiquetado significa que no hay cadena principal que contenga al menos vértices marcados con y vértices marcados con ; no puede ser arbitrariamente grande anticadenas pero tienen que contener sólo elementos o solamente elementos, hasta excepciones en la mayoría. Parece que no permitir grandes anticadenas debe hacer cumplir que el DAG esencialmente "suplentes" entre las partes de gran anchura para vértices marcado con, y gran anchura de$\Sigma = \{a, b\}$$G$$k$$k$$a$$k$$b$$a$$b$$k-1$$a$$b$vértices etiquetados, pero no he podido formalizar esta intuición. (Por supuesto, una caracterización estructural adecuada debe referirse a las etiquetas de vértices además de la forma del DAG, porque ya para $k \geq 1$ y en $\{a, b\}$ la condición se cumple con DAG completamente arbitrarios siempre que todos los vértices llevan la misma etiqueta).

Con Charles Paperman hemos podido obtener dicho resultado para los DAG etiquetados con el alfabeto . Esencialmente, podemos mostrar que dado un DAG que tiene grandes anticadenas de elementos de marcado con, grandes anticadenas de marcado con elementos, pero no hay anticadenas grandes que contienen tanto muchos -etiquetados y elementos -etiquetados, entonces hay una descomposición de como partición , donde:$\{a, b\}$$G$$a$$b$$a$$b$$G$$L_1, \ldots, L_n$

• la partición es lo que llamamos una "estratificación", es decir: $L_1, ..., L_n$
  • cada es un conjunto convexo, es decir, si y entonces$L_i$$x, y \in L_i$$x \leq z \leq y$$z \in L_i$
  • para todo , no hay e tal que$i < j$$x \in L_i$$y \in L_j$$y \leq x$
• para cualquier antichain de , hay alguna tal que está "casi contenida" en , es decir,es menos que una constante$A$$G$$i$$A$$L_i$$|A \setminus L_i|$
• para cada , se cumple uno de los siguientes: $L_i$
  • $L_i$ contiene una gran anticadena de elementos -etiquetados y no contiene gran anticadena de marcado con elementos$a$$b$
  • $L_i$ contiene una gran anticadena de marcado con elementos pero no contiene ningún gran anticadena de elementos -etiquetados$b$$a$

Además, dicha partición se puede calcular en PTIME.

He publicado nuestra prueba actual en línea . Es muy difícil y esencialmente no se corrige porque no tenemos ningún uso para el resultado por ahora, pero aún así pensé que era más ordenado agregar una respuesta a esta pregunta de CStheory con nuestro progreso actual. No dude en ponerse en contacto conmigo si está interesado en el resultado pero no puede entender la prueba.