Uogólnienie twierdzenia Dilwortha dla oznaczonych DAG

Antyłańcuch w DAG jest podzbiorem wierzchołków, które są parami nieosiągalny, czyli, nie ma taki sposób, że jest dostępne z w . Z twierdzenia Dilwortha w teorii częściowego porządku wiadomo, że jeśli DAG nie ma antychainu o rozmiarze , wówczas może zostać rozłożony na połączenie co najwyżej łańcuchów rozłącznych, tj. Ścieżek kierowanych.$(V, E)$$A \subseteq V$$v \neq v' \in A$$v$$v'$$E$$k \in \mathbb{N}$$k-1$

Teraz interesują mnie oznaczone DAG , tj. DAG, w których każdy wierzchołek niesie etykietę w jakimś ustalonym skończonym zestawie etykiet. Biorąc pod uwagę antychain , mogę zdefiniować jego rozmiar jako minimalną liczbę wystąpień etykiet w , a mianowicie. Czy w tym kontekście istnieje odpowiednik twierdzenia Dilwortha? Innymi słowy, jeśli założę, że DAG nie ma antichain o oznaczonym rozmiarze k \ in \ mathbb {N}$v$$\lambda(v)$$\Sigma$$A \subseteq V$$\Sigma$$A$$\min_{a \in \Sigma} |\{v \in A \mid \lambda(v) = a\}|$ $k \in \mathbb{N}$, co mogę założyć o jego strukturze? Czy mogę go rozłożyć w jakiś szczególny sposób? Zaskakuje mnie już przypadek $\Sigma = \{a, b\}$ , ale interesuje mnie również ogólny zestaw skończonych etykiet.

W celu uwidocznienia tego na $\Sigma = \{a, b\}$ , stwierdzając, że $G$ ma antyłańcuch znakowanego wielkości $k$ oznacza, że nie ma antyłańcuch zawierający co najmniej $k$ wierzchołki oznaczone $a$ i $k$ wierzchołki oznaczone $b$ ; nie może być dowolnie duże antyłańcuch ale muszą zawierać tylko $a$ elementów lub tylko $b$ elementów, do $k-1$ wyjątków w większości. Wydaje się, że nie zezwalanie na duże antychiny powinno wymuszać, że DAG zasadniczo „naprzemiennie” między częściami o dużej szerokości w $a$ wierzchołków oznakowanych i dużej szerokości w przypadku k ≥ 1 { a , b $b$-znakowane wierzchołki, ale nie byłem w stanie sformalizować tej intuicji. (Oczywiście odpowiednia charakterystyka strukturalna musi mówić o etykietach wierzchołków oprócz kształtu DAG, ponieważ już dla i na warunek jest spełniony przez całkowicie arbitralne DAG, ilekroć wszystkie wierzchołki mają tę samą etykietę).$k \geq 1$$\{a, b\}$

Dzięki Charlesowi Papermanowi byliśmy w stanie uzyskać taki wynik dla DAG oznaczonych alfabetem . Zasadniczo, można wykazać, że otrzymuje DAG G , który ma dużą antyłańcuch z a znakowanego elementów dużych antyłańcuch z b znakowanych elementów, ale nie wykazujące zarówno duże antyłańcuch wiele A znakowanego i b elementów znakowanego, to jest rozkład G jako partycja L 1 , … , L n , gdzie:$\{a, b\}$$G$$a$$b$$a$$b$$G$$L_1, \ldots, L_n$

• partycja jest to, co nazywamy „warstw”, to znaczy: $L_1, ..., L_n$
  • każdy jest zestaw wypukły, to znaczy, gdy x , y ∈ l i i x ≤ z ≤ Y następnie z ∈ L $L_i$$x, y \in L_i$$x \leq z \leq y$$z \in L_i$
  • dla wszystkich nie ma x ∈ l i i Y ∈ L j , tak że Y ≤ $i < j$$x \in L_i$$y \in L_j$$y \leq x$
• dla każdej antyłańcuch do G , istnieją pewne i takie, które jest „prawie zawarte” w L I , czyli | A ∖ L i | jest mniejsza niż stała$A$$G$$i$$A$$L_i$$|A \setminus L_i|$
• dla każdego jest spełniony jeden z poniższych warunków: $L_i$
  • zawiera dużą antyłańcuch w ciągu znakowanego elementów i nie zawiera dużą antyłańcuch z b znakowanych elementów$L_i$$a$$b$
  • zawiera dużą antyłańcuch z b znakowanych elementów, ale nie zawiera dużą antyłańcuch w ciągu znakowanego elementami$L_i$$b$$a$

Ponadto taką partycję można obliczyć w PTIME.

Nasz aktualny dowód opublikowałem online . Jest to bardzo szorstkie i zasadniczo nie jest poprawiane, ponieważ na razie nie mamy sensu, ale nadal uważałem, że łatwiej jest dodać odpowiedź na to pytanie CStheory z naszym obecnym postępem. Nie wahaj się ze mną skontaktować, jeśli jesteś zainteresowany rezultatem, ale nie możesz zrozumieć dowodu.