Dilworth定理

· · 个人记录

偏序集的定义：偏序是在集合X上的二元关系≤（这只是个抽象符号，不是“小于或等于”，它满足自反性、反对称性和传递性）。即，对于X中的任意元素a,b和c，有:

(1)自反性：a≤a;

(2)反对称性：如果a≤b且b≤a，则有a=b;

(3)传递性：如果a≤b且b≤c，则a≤c 。

带有偏序关系的集合称为偏序集。

一个反链A是X的一个子集，它的任意两个元素都不能进行比较。

一个链C是X的一个子集，它的任意两个元素都可比。

Dilworth定理1：对于一个偏序集，其最少反链划分数等于其最长链的长度。

Dilworth定理2​：对于一个偏序集，最少链划分等于最长反链长度。

即链的最少划分数 <=> 反链的最长长度

即最长不下降子序列的数量是最长下降子序列(还有其他三种表达方式)

在X中，对于元素a，如果任意元素b，都有a≤b，则称a为极小元。

考虑证明:

第一个与第二个类似,只证明第一个

设p为最少反链划分数,r为最长链长度,C是最大链,X为当前偏序集.

  1. 证明:偏序集中不能划分出小于r个反链.

    由于r是最大链C的大小,C中任意两个元素都可比,所以C中任意两个元素都不能属于同一反链.所以p>=r.(至少有r个不同的反链)

  2. 设X1＝X，A1是X1中的极小元的集合。从X1中删除A1得到X2。注意到对于X2中任意元素a2，必存在X1中的元素a1，使得

    a1<=a2。令A2是X2中极小元的集合，从X2中删除A2得到X3……，最终会有一个X_k 非空而Xk+1为空。于是A1,A2,…,Ak就是X的

    反链的划分，同时存在链a1<=a2<=…<=ak，其中ai在Ai内。由于r是最长链大小，因此r>=k。由于X被划分成了k个反链，因此

    r>=k>=p。

    人话:

    我们每次找极小元的集合,把那个集合拿出,再在拿出后剩下的集合里重复操作.直到剩下空集.我们发现这样子操作后相邻操作的两个集合必定是存在关系.因为它是由极小元集合分裂而出.

    操作图示类似于拓扑图.然后发现对于拓扑图中,我们可以连许多条链.而这个链的长度就是反链的数量(每次分裂)且一定\le r.

    所以r>=p

  3. 由于r<=p且r>=p,因此r=p，定理1得证。