Dilworth 定理略记

whhsteven · 2021-11-05 23:25:16 · 个人记录

前置芝士

1. 设 R 是集合 A 上的一个二元关系，若 R 是自反的、反对称的和可传递的，则称 R 是集合 A 上的偏序关系，简称偏序，记作 \preceq。将集合 A 和偏序 \preceq 放在一起构成偏序集 (A,\preceq)。这里自反的、反对称的和可传递的即要求：

   • 自反性：\forall \ a \in A 有 a \preceq a；

   • 反对称性：\forall \ a,b \in A，若 a \preceq b \ \land \ b \preceq a 则有 b = a；

   • 传递性：\forall \ a,b,c \in A，若 a \preceq b \ \land \ b \preceq c 则有 a \preceq c。

2. 对有偏序关系的集合 A，如果其子集 P 满足其中任意一对元素均可比，则称 P 是一条链。任意一对元素均无关的子集称为反链。

Dilworth 定理

定理内容

对于任意有限偏序集，其最长反链的长度（元素数目）必等于最小链划分中链的数目。

其对偶形式亦真。

简证

• 反链上的任意一对元素均不可比，所以任一元素均在单独的一条链上，故最小链划分数 \geq 最长反链长度；

• 因为是最长反链，所以不存在任一元素在该反链外却与该反链上元素均不可比，故所有最长反链外的元素均可以在最长反链上元素所在的这些链上，即这些链已经足够。因为是最小链划分，所以最小链划分数 \leq 最长反链长度。

综上即得：最小链划分数 = 最长反链长度。

相关芝士

设 R 是集合 A 上的一个二元关系，若 R 是反自反的、非对称的和可传递的，则称 R 是集合 A 上的严格偏序或反自反偏序关系，记作 \prec。这里反自反的、非对称的和可传递的即要求：

• 反自反性：\forall \ a \in A 有 a \nprec a；

• 非对称性：\forall \ a,b \in A，若 a \prec b 则有 b \nprec a；

• 传递性：\forall \ a,b,c \in A，若 a\prec b \ \land \ b \prec c 则有 a \prec c。

严格偏序关系和 DAG 有直接的联系。