Generalisasi teorema Dilworth untuk DAG berlabel

Sebuah antichain dalam DAG adalah bagian A ⊆ V dari simpul yang berpasangan terjangkau, yaitu, tidak ada v ≠ v ' ∈ A sehingga v dapat dicapai dari v ' di E . Dari teorema Dilworth dalam teori urutan parsial, diketahui bahwa jika DAG tidak memiliki ukuran antik dari ukuran k ∈ N , maka dapat didekomposisi dalam penyatuan paling banyak rantai terpisah k - 1 , yaitu jalur yang diarahkan.$(V, E)$$A \subseteq V$$v \neq v' \in A$$v$$v'$$E$$k \in \mathbb{N}$$k-1$

Sekarang, saya tertarik pada DAG berlabel , yaitu, DAGs di mana setiap simpul membawa label λ ( v ) dalam beberapa set fin label tetap yang terbatas . Diberi antichain A ⊆ V , saya dapat mendefinisikan ukurannya sebagai jumlah minimal kemunculan label Σ di A , yaitu, min a ∈ Σ | { v ∈ A ∣ λ ( v ) = a } | .$v$$\lambda(v)$$\Sigma$$A \subseteq V$$\Sigma$$A$$\min_{a \in \Sigma} |\{v \in A \mid \lambda(v) = a\}|$Apakah ada analogi teorema Dilworth dalam konteks ini? Dengan kata lain, jika saya berasumsi bahwa DAG tidak memiliki barang antik ukuran berlabel , apa yang dapat saya asumsikan tentang strukturnya? Bisakah saya menguraikannya dengan cara khusus? Saya sudah bingung dengan kasus Σ = { a , b } , tetapi juga tertarik dengan kasus set label hingga umum.$k \in \mathbb{N}$$\Sigma = \{a, b\}$

Untuk memvisualisasikan ini untuk , mengatakan bahwa G tidak memiliki barang antik berukuran label k berarti tidak ada barang antik yang mengandung setidaknya k simpul yang berlabel a dan k simpul yang berlabel b ; mungkin ada antikristus besar yang sewenang-wenang tetapi mereka harus mengandung hanya satu elemen atau hanya b elemen, hingga paling banyak pengecualian k - 1 . Tampaknya pelarangan antichains besar harus menegakkan bahwa DAG pada dasarnya "alternatif" antara bagian-bagian dari lebar besar untuk $\Sigma = \{a, b\}$$G$$k$$k$$a$$k$$b$$a$$b$$k-1$$a$simpul -labeled, dan lebar besar untuk -labeled simpul, tapi saya belum bisa untuk meresmikan intuisi ini. (Tentu saja, karakterisasi struktural yang cocok harus berbicara tentang label simpul selain bentuk DAG, karena sudah untuk k ≥ 1 dan pada { a , b } kondisi ini dipenuhi oleh DAGs sepenuhnya sewenang-wenang setiap kali semua simpul membawa label yang sama.)$b$$k \geq 1$$\{a, b\}$

$\{a, b\}$$G$$a$$b$$a$$b$$G$$L_1, \ldots, L_n$

• $L_1, ..., L_n$
  • $L_i$$x, y \in L_i$$x \leq z \leq y$$z \in L_i$
  • $i < j$$x \in L_i$$y \in L_j$$y \leq x$
• $A$$G$$i$$A$$L_i$$|A \setminus L_i|$
• $L_i$
  • $L_i$$a$$b$
  • $L_i$$b$$a$

Selanjutnya, partisi seperti itu dapat dihitung dalam PTIME.

Saya telah memposting bukti kami saat ini secara online . Ini sangat kasar dan pada dasarnya tidak mengoreksi karena kami tidak menggunakan hasilnya untuk saat ini, tetapi saya masih berpikir itu lebih rapi untuk menambahkan jawaban untuk pertanyaan CStheory ini dengan kemajuan kami saat ini. Jangan ragu untuk menghubungi saya jika Anda tertarik dengan hasilnya tetapi tidak bisa memahami buktinya.