Verallgemeinerung des Dilworth-Theorems für markierte DAGs

Eine Antichain in einer DAG ist eine Teilmenge A ⊆ V von Scheitelpunkten, die paarweise nicht erreichbar sind, dh es gibt kein v ≠ v ' ∈ A, so dass v von v ' in E erreichbar ist . Aus dem Dilworth-Theorem in der Teilordnungstheorie ist bekannt, dass DAG, wenn es keine Antichain der Größe k ∈ N hat , in einer Vereinigung von höchstens k - 1 disjunkten Ketten, dh gerichteten Pfaden , zerlegt werden kann .$(V, E)$$A \subseteq V$$v \neq v' \in A$$v$$v'$$E$$k \in \mathbb{N}$$k-1$

$v$$\lambda(v)$$\Sigma$$A \subseteq V$$\Sigma$$A$$\min_{a \in \Sigma} |\{v \in A \mid \lambda(v) = a\}|$ $k \in \mathbb{N}$Was kann ich über seine Struktur annehmen? Kann ich es auf besondere Weise zersetzen? Der Fall von verwirrt mich bereits , interessiert mich aber auch für den Fall eines allgemeinen endlichen Etikettensatzes.$\Sigma = \{a, b\}$

Um dies für zu visualisieren , bedeutet die Aussage, dass keine Antichain der markierten Größe , dass es keine Antichain gibt, die mindestens mit Eckpunkte und mit bezeichnete Eckpunkte enthält ; Es kann beliebig große Antichains geben, sie müssen jedoch nur Elemente oder nur Elemente enthalten, höchstens bis zu Ausnahmen. Es scheint, dass das Nichtzulassen großer Antichains erzwingen sollte, dass die DAG im Wesentlichen zwischen Teilen mit großer Breite für markierte Eckpunkte und großer Breite für "wechselt"$\Sigma = \{a, b\}$$G$$k$$k$$a$$k$$b$$a$$b$$k-1$$a$$b$-beschriftete Eckpunkte, aber ich konnte diese Intuition nicht formalisieren. (Natürlich muss eine geeignete strukturelle Charakterisierung zusätzlich zur Form der DAG über die Beschriftungen von Eckpunkten sprechen, da bereits für und auf die Bedingung von völlig willkürlichen DAGs erfüllt wird, wann immer alle Eckpunkte tragen das gleiche Etikett.)$k \geq 1$$\{a, b\}$

Mit Charles Paperman konnten wir ein solches Ergebnis für DAGs erzielen, die mit dem Alphabet . Im Wesentlichen können wir zeigen, dass bei einer DAG , die große Antichains von markierten Elementen, große Antichains von markierten Elementen, aber keine großen Antichains, die sowohl viele markierte als auch markierte Elemente enthalten, eine Zersetzung von vorliegt als Partition , wobei:$\{a, b\}$$G$$a$$b$$a$$b$$G$$L_1, \ldots, L_n$

• Die Partition ist das, was wir als "Schichtung" bezeichnen, dh: $L_1, ..., L_n$
  • Jedes ist eine konvexe Menge, dh wenn und dann$L_i$$x, y \in L_i$$x \leq z \leq y$$z \in L_i$
  • für alle gibt es kein und so dass$i < j$$x \in L_i$$y \in L_j$$y \leq x$
• für jede Antichain von gibt es einige so dass in "fast enthalten" ist , dhist weniger als eine Konstante$A$$G$$i$$A$$L_i$$|A \setminus L_i|$
• Für jedes gilt eine der folgenden Bedingungen: $L_i$
  • $L_i$ enthält eine große Antichain von markierten Elementen und keine große Antichain von markierten Elementen$a$$b$
  • $L_i$ enthält eine große Antichain von markierten Elementen, aber keine große Antichain von markierten Elementen$b$$a$

Ferner kann eine solche Partition in PTIME berechnet werden.

Ich habe unseren aktuellen Proof online gestellt . Es ist sehr grob und im Wesentlichen nicht Korrektur gelesen, da wir das Ergebnis derzeit nicht verwenden können, aber ich dachte immer noch, es wäre ordentlicher, eine Antwort auf diese CStheory-Frage mit unseren aktuellen Fortschritten hinzuzufügen. Zögern Sie nicht, sich mit mir in Verbindung zu setzen, wenn Sie am Ergebnis interessiert sind, aber den Beweis nicht verstehen können.