Research Space for Linear Algebra & Discrete Mathematics
我猜你的 S 是 {1,2,3,4}.最大的 antichain 其 size 為 6. 另外; 至少 6 個 disjoint chain 才能 cover 這個 poset.Ps. 可以參考 Dilworth's Theorem. 此定理說明: 最大的 antichain 的 size 等於使用 chain 來 cover 此 poset 的最少數量.
抱歉還是不太懂耶~ 所以不是去計算最長的antichain由幾個element組成囉?
最大的antichain是6沒錯, 我下次會更正過來, 所以需要6個chain才能形成它們的union, 因為我們要的chain都要disjoint, 所以要6個, chain不用每個都由最小元素開始, 也就是不用都取最長的chain, 事實上都取最長的chain不會形成disjoint它的想法類似定理3的想法, 轉過來看而已
張貼留言
這題之前有人問過了 可是我覺得解答寫的怪怪的
解答寫最大的antichain為4 可是其實最大的antichain應該為六
3 則留言:
我猜你的 S 是 {1,2,3,4}.
最大的 antichain 其 size 為 6. 另外; 至少 6 個 disjoint chain 才能 cover 這個 poset.
Ps. 可以參考 Dilworth's Theorem. 此定理說明: 最大的 antichain 的 size 等於使用 chain 來 cover 此 poset 的最少數量.
抱歉還是不太懂耶~ 所以不是去計算最長的antichain由幾個element組成囉?
最大的antichain是6沒錯, 我下次會更正過
來, 所以需要6個chain才能形成它們的
union, 因為我們要的chain都要disjoint
, 所以要6個, chain不用每個都由最小元素
開始, 也就是不用都取最長的chain, 事實上
都取最長的chain不會形成disjoint
它的想法類似定理3的想法, 轉過來看而已
張貼留言