Dilworth定理（及其对偶定理）

BJpers2 · 2019-10-06 20:54:24 · 个人记录

一、定义

假设我们有有限偏序集(S,\leq)（可以理解为一个DAG）。

定义「链」A为一个点集，使得对任意两个点u,v有u\leq v或v\leq u。

定义「反链」B为一个点集，使得对任意两个点u,v有u\nleq v且v\nleq u。

定义一个「链覆盖」为一组链<C_1,C_2,\dots,C_k>，满足\forall i\ne j,C_i\cap C_j=\varnothing，且\bigcup_{i=1}^k C_i=S。并称其大小为k。

类似定义「反链覆盖」。

定义「极大元素」为满足如下性质的元素u：没有任何除u以外的元素v使得u\le v。

二、定理

定理一

对任意有限偏序集(S,\leq)，其最长链长度L等于其最小反链覆盖大小N。

证明

• 因为对于任意一条链C，它的每个元素必须被划分到不同的反链中，所以L\leq N。

• 再考虑S中所有极大元素组成的集合\Gamma_1，则\Gamma_1必是反链。我们从S中删去\Gamma_1后，又可类似地构造\Gamma_2,\Gamma_3,\dots,\Gamma_n。这样我们得到了一个反链覆盖，根据定义N\leq n。

• 当i>1，对\Gamma_i中的任意元素u，必存在v\in\Gamma_{i-1}使得v\geq u。因此我们必然有一条长为n的链。根据定义L\geq n。

• 综合以上三点可得L=N。

定理二

对任意有限偏序集(S,\leq)，其最长反链长度T等于其最小链覆盖大小M。

证明

• 因为对于任意一条反链A，它的每个元素必须被划分到不同的链中，所以T\leq M。

• 考虑归纳证明，当|S|=1时T=M=1。

• 否则取极大值x，令S'=S-x。我们假设S'的最长反链=最小链覆盖=K，且C_1,C_2,\dots,C_K是一组最小链覆盖。并令b_i为C_i中可能在最长反链中的最大值。

• 首先，因为同一条链上不会有两个点同时在一条反链上，所以要凑出最长反链必须是每条链上各取一点。

• 假设i\ne j且b_i\leq b_j，那么考虑b_j所在反链与链C_i的交点u，一方面我们有b_j\ge b_i\ge u，而这又与b_j和u在同一反链上矛盾。

• 因此\forall i\ne j，有b_i \nleq b_j，也即集合B=\{b_i|i\in[1,K]\}是一条S'的最长反链。

• 接下来考虑原集合。首先明确一点，T,M\in [K,K+1]。

  • 假如集合B+x是反链，则T=K+1。同时根据T\leq M可得T=M。

  • 否则因为x是极大的，存在b_i使得x\ge b_i，我们取出所有链C_i上可能出现在S'的最长反链中的元素和x构成集合D，那么D必是链。

  • 再考虑S-D，它是S'的子集，而且所有可能的最长反链都被抽走了一个点，所以S''的最长反链=最小链覆盖=K-1。再算上D，S就有了一个大小为K的链覆盖。结合T\le M，其最长反链也为K。

• 证毕