狄尔沃斯定理

狄尔沃斯定理(Dilworth's theorem)亦称偏序集分解定理，是关于偏序集的极大极小的定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真，它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目，由偏序集P按如下方式产生的图G称为偏序集的可比图：G的节点集由P的元素组成，而e为G中的边，仅当e的两端点在P中是可比较的，有限全序集的可比图为完全图1。

基本介绍定理 对偏序集，设A中最长链的长度是n，则将A中元素分成不相交的反链，反链个数至少是n。

证明施归纳于n。

当n=1时，A本身就是一条反链，定理结论成立。(这时≤是恒等关系)。2

假设对于n=k，结论成立。考虑n=k+1的情况，当A中最长链的长度为k+1时，令M为A中极大元的集合，显然M是一条反链。而且A-M中最长链的长度为k。由归纳假设，可以把A-M分成至少k个不相交的反链，加上反链M，则A可分成至少k+1条反链。

这个定理称为狄尔沃斯(Dilworth)定理或偏序集的分解定理，这是组合学三大存在性定理之一，有广泛的应用。这种分解是所有分解方法中反链个数最少的一种分解方法，因为A不可能分解成n-1条反链。假若只有n-1条反链，那么最长链的n个元素中必有2个元素被分到同一个反链，显然这与反链的定义矛盾。

有穷偏序集分解成n条反链的过程可以采用下面的方法去做。

算法 偏序集反链分解算法：

输入：偏序集A．

输出：A中的反链 ．

1．i←1

2． 的所有极大元的集合(显然 是一条反链)

3．令 ．

4．if A≠∅

5．

6．转2

注意：从A中去掉Bi中的元素时，同时去掉连接这些元素与被它覆盖的元素之间的边，行2~3每执行一次，最长链的长度减少l，同时产生一条新的反链。因为最长链长度为n，恰好执行n次，算法结束，并得到n条反链。3

推论 对偏序集，若A中元素为mn+1个，则A中或者存在一条长度为m+1的反链，或者存在一条长度为n+1的链2。

相关介绍组合数学中有很多存在性定理，其中三大基本定理是经常使用的工具：一是1935年P.Hall提出的“相异代表组定理”；二是1950年R.P.Dilworth发现的“偏序集分解定理（狄尔沃斯定理）”；三是1930年F.P.Ramsey发表的“广义鸽洞原理”4。

关于R.P.Dilworth的狄尔沃斯定理的相关介绍：

大家知道，许多离散事物对象之间存在着种种“次序”关系，例如一组事物的排队，某些现象出现的先后，生物的代代相传等，但也不是任何一类事物间都有同一种“序”的关系，因此近代数学从无数具体的对象关系里抽象出来的“偏序集”(即半序集)概念，就显得更加重要而有用，现代组合数学中的若干重要理论就是建立在偏序集概念的基础上的。

由有限个元素(离散事物)所构成的有限偏序集往往可分解成若干条“链”(即有起始元的全序子集)，位于不同链上的元素之间可以没有序关系，这些没有序关系的元素叫作“无序元”，由无序元所作成的子集叫作无序子集，那么，把一个偏序集分解成链的最少条数m和该偏序集所含最大无序子集的元素个数M之间有什么关系呢?Dilworth发现它们之间恰好具有相等关系：m=M。这个定理也是利用精细的归纳法证明的，它不仅对一般组合数学十分重要，而且对生物科学也有很大用处。例如，由这个定理可以推断：在mn+1个实验用的小鼠中，要么有m+1个是代代相传的，要么有n+1个是彼此没有亲缘关系的。”(这里可把上下代关系看作序的关系，故mn+1个小鼠作成一个偏序集)4。

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学