数组合数学

偏序集与Dilworth定理

字数统计: 3.4k字   |   阅读时长: 13分
, , ,

摘要: 偏序集、Dilworth定理

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

此前我们系统第学习了组合数学，详细内容见下面这些文章：

组合数学的内容还是很丰富的，上面这些只是经典组合数学中比较初等的一部分，结合各种应用可以延展出很多比较深入的内容，下面我们简单串讲一下。

组合数学研究离散对象，对于离散对象，在描述清楚其模式之后，从简单到复杂我们要知道 5 个问题：

  • (1) 存在性问题：给定模式的离散对象是否存在。
  • (2) 构造问题：构造给定模式的离散对象的一个实例。
  • (3) 计数问题：给定模式的离散对象共有多少不同的实例。
  • (4) 枚举问题：将给定模式的离散对象的所有实例一一枚举出来。
  • (5) 优化问题：给定模式的离散对象的所有实例中，哪一实例使得目标函数取得最值。

上述每种问题都可以引入一些数学方法，每种问题都在计算机的场景中有无数例子，每种问题都涉及到到很多算法，每种问题都在 leetcode 中有相关的题目。

这只是从问题的角度出发，组合数学已经可以延展出这么多内容，再结合离散对象的多样性，组合数学的内容会变得更丰富。

集合是最基础的概念，从集合出发，我们可以讨论各种离散结构。对于前面提到的五个问题，当离散结构不一样时，用到的方法也会不一样。

  • 首先集合元素如果什么特性都没有，那么我们可以研究子集的问题，由于结构太简单，存在性、构造和计数往往是显然的，我们往往研究的都是子集的枚举、优化问题。作为经常刷 leetcode 来讲，子集型的回溯法，状态压缩DP应该没少写吧。
  • 如果元素之间有序的关系，那么我们面对的就是偏序集、全序集，进一步地还可以涉猎排列、矩阵这样的对象。作为程序员来讲，数组肯定用过吧，那么你已经每天都在处理这类离散对象了；
  • 如果元素之间定义了某种关系，那我们将面对图、树这样的结构。由于这一主题已经足够丰富，图上的存在、构造、计数、枚举、优化问题已经独立出来了，也就是图论。
  • 如果元素之间定义了某种运算，那我们面对的就是代数结构。我前面的写的教程中，群论这部分就是讨论群上的计数问题。当然有限域也是计算机应用中很常见的一个代数结构。

综上，当我们解决组合数学的问题的时候，一看清楚我们要解决的是五类问题的哪一个、二看离散对象是什么类型的，就可以考虑大致从哪些方法开始尝试了。

本文我们抛砖引玉，讨论偏序集上的存在性问题，我们会简要介绍相关的概念、以及 Dilworth 定理。有了前面的宏观性的介绍，下面三行就可以概括清楚本文的内容：

  • 问题类型：存在性问题
  • 离散结构：偏序集
  • 方法：Dilworth 定理

$1 偏序集和偏序关系

定义

X 为一个非空集合，R 是定义在 X 上的具有自反，反对称，传递的二元关系，称 $P = (X, R)$ 为一个偏序集(不引起混淆时可以直接说 X 是偏序集)，R 为偏序关系。

通常用 $x \leq y$ 描述 X 中的元素 x, y 满足偏序集 $(X, R)$ 中 R 规定的关系。即 $(x, y) \in R$ 记为 $x \leq y$，这样偏序集也可以写为 $(X, \leq)$。

根据 $\leq$，可以自然地定义 $ < $。$x < y$ 表示 $x \leq y$ 且 $x \neq y$。

例子

  • 正整数集合 $\mathbb{Z}^{+}$，对于 $\forall a,b \in \mathbb{Z}^{+}$，规定 $a \leq b$ 当且仅当 $a|b$，则 $\mathbb{Z}$ 为一个偏序集。

  • S 为集合，P(S) 为 S 的幂集，对于 $\forall A, B \in P(S)$，规定 $A \leq B$ 当且仅当 $A \subseteq B$，则 $P(S)$ 为偏序集。

  • V 是域 F 上的线性空间，$L(V)$ 为 V 的所有子空间所组成的集合，对于 $U, W \in L(V)$，规定 $U \leq W$ 当且仅当 $U \subseteq W$。$L(V)$ 为一个偏序集。

$2 全序集，链，反链

给定偏序集 $P = (X, R)$，对 X 中任意两个元素 x, y，

(1) $x \leq y$ 和 $y \leq x$ 必有一个成立，则 P 称为全序集，也成为链。

(2) $x \leq y$ 和 $y \leq x$ 均不成立。P 称为反链。

$3 子偏序集

给定偏序集 $(X, R)$，$X^{‘}$ 为 X 的子集，则 R 在 $X^{‘}$ 上也是偏序集。$P^{‘} = (X^{‘}, R)$ 称为 $P = (X, R)$ 的子偏序集。

$4 全序集的长度，偏序集的高度，宽度

有限链或反链中的元素个数为链或反链的长度。

偏序集的最长子链长度称为偏序集的高度。

偏序集的最长子反链的长度为偏序集的宽度。

例子1

整除关系决定的偏序集 $P = ((\mathbb{Z}^{+}), |)$ 中：

(1) $(\{m|m=2^{k},k\in \mathbb{N}\}, |)$ 为一个子偏序集，且它是一个链。

(2) $(\{p | p 是素数\}, |)$ 也是一个子偏序集，但它是反链。

例子2

在包含关系决定的偏序集 $P = (P(S), \subseteq)$ 中，$(\{A \subseteq S | |A| = 1\}, \subseteq)$ 为一个子反链。

$5 极小元，最小元，极大元，最大元

对于偏序集 X 以及其中的一个元素 a：

(1) a 为极小元: 没有异于 a 的元素 x 满足 $x \leq a$。即若有 $x \leq a, x \in X$ 则 $x = a$。

(2) a 为最小元: 对任意元素 $x \in X$，均有 $a \leq x$。

(3) a 为极大元: 没有异于 a 的元素 x 满足 $x \geq a$。即若有 $x \geq a, x \in X$ 则 $x = a$。

(4) a 为最大元: 对任意元素 $x \in X$，均有 $a \geq x$。

对于链(全序集)，极小元就是最小元，极大元就是最大元。

偏序集的所有极小元形成一个反链，所有极大元也形成一个反链。

$6 Dilworth 定理

狄尔沃斯定理(Dilworth’s theorem)也称偏序集分解定理。

Dilworth 定理对偶形式 (Mirsky)

偏序集 $(X, \leq)$，高度为 n，则存在划分 $X = \bigcup\limits_{i=1}\limits^{n}A_{i}$，使得每个 $A_{i}$ 都是反链。

注：最长链 = 最小反链覆盖 = 偏序集高度。

证明 (数学归纳法)：

偏序集 $(X, \leq)$ 高度为 $n$ 也就是 $X$ 的最长子链长度为 $n$，因此 $X$ 不可能划分成更少的反链。下面证明 $X$ 可以划分为 $n$ 个反链。
Mirsky
对 n 归纳。当 $n = 1$ 时，结论成立。假设对于 $n - 1$ 来说结论成立，下面看 $n$ 的情形。

记 $A_{1}$ 为 $X$ 的所有极大元素组成的集合，则 $A_{1}$ 为一个反链。

如果 $X \setminus A_{1}$ 中有长度为 $n$ 的链，则此链的最后一个元素为 $X$ 的极大元，属于 $A_{1}$，矛盾，因此 $X \setminus A_{1}$ 的高度为 $n-1$。由归纳假设，$X \setminus A_{1}$ 可以划分为 $n-1$ 个反链，因此 $X$ 可以划分为 $n$ 个反链。$\Box$

Dilworth 定理

设有限偏序集 $(X, \leq)$ 的宽度为 m，则存在划分 $X = \bigcup\limits_{i=1}\limits^{m}C_{i}$，使得每个 $C_{i}$ 都是链。

注：最小链覆盖 = 最长反链 = 偏序集宽度。

证明 (数学归纳法)：

偏序集 $(X, \leq)$ 宽度为 $m$ 也就是 $X$ 的最长子反链长度为 $m$，因此 $X$ 不可能划分成更少的链。下面证明 $X$ 可以划分为 $m$ 个链。

对 $|X|$ 做归纳。$|X|=1$ 时，结论成立。假设结论对 $<|X|$ 成立，下面考虑 $|X|$ 的情况。

设 $C_{1}$ 为 $X$ 的一个极大链，也就是没有其它的链真包含 $C_{1}$。

考虑偏序集 $X \setminus C_{1}$，如果 $X \setminus C_{1}$ 的宽度为 $m-1$ 则结论成立。

若 $X \setminus C_{1}$ 的宽度为 $m$，设 $\{a_{1}, a_{2}, \cdots, a_{m}\}$ 为 $X \setminus C_{1}$ 的一条反链。

定义 $S^{-}=\{x\in X | \exists i, x \leq a_{i}\}$，$S^{+}=\{x\in X | \exists i, x \geq a_{i}\}$。

因为 $(X, \leq)$ 的宽度为 $m$，得：

由于 $C_{1}$ 为极大链，所以 $C_{1}$ 得最大元不在 $S^{-}$ 中，由归纳假设知：

  • $S^{-}$ 可以划分为 $m$ 个链 $S_{1}^{-}, S_{2}^{-}, \cdots, S_{m}^{-}$，其中 $a_{i}$ 为 $S^{-}_{i}$ 的最大元。
  • $S^{+}$ 可以划分为 $m$ 个链 $S_{1}^{+}, S_{2}^{+}, \cdots, S_{m}^{+}$。其中 $a_{i}$ 为 $S^{+}_{i}$ 的最小元。

对任意 $1 \leq i \leq m$，把 $S^{-}_{i}$ 和 $S^{+}_{i}$ 通过 $a_{i}$ 连接起来，就把 $X$ 划分为了 $m$ 个链。 $\Box$

组合数学中有很多存在性定理，其中三大基本定理是经常使用的工具：

  • (1) 1935年P.Hall, 【相异代表组定理】
  • (2) 1950年R.P.Dilworth, 【偏序集分解定理】
  • (3) 1930年F.P.Ramsey, 【广义鸽洞原理】

$7 Erdos-Szekeres定理

Erdos-Szekeres 定理是 Dilworth 定理的推论，可以用鸽巢原理来证明，也可以构造性证明。定理描述如下。

Erdos-Szekeres定理

对于偏序集 $\{X, \leq\}$，$m, n \in \mathbb{N}^{+}$，$|X| = mn + 1$，则要么 $X$ 存在长度至少为 $m+1$ 的链（高度），要么存在长度至少为 $n+1$ 的反链（宽度）。

证明1 (反证)：

假设 $X$ 不存在长度至少为 $m+1$ 的链，也不存在长度至少为 $n+1$ 的链。

记 $X$ 的最长链长度为 $H$，最长反链长度为 $W$，依假设条件有 $H \leq m, W \leq n$。

由 Dilworth 定理，存在划分 $X = \bigcup\limits_{i=1}\limits^{W}C_{i}$，每个 $C_{i}$ 都是链，长度为 $H_{i}$，由于 $X$ 的最长链长度为 $H$。因此：

而给定的条件是 $|X| = mn + 1$，矛盾。$\Box$

证明2：

定义函数 $f: A\rightarrow \mathbb{N}$，其中 $A = \{1,2,\cdots,mn+1\}$，$f(i)$ 为以 $x_{i}$ 作为最小元的链的最长长度。

假设 $\forall i \in A, f(i) < m + 1$，那么 $f$ 的值域最大只能是 $\{1,2,\cdots,m\}$，记为 $B$。

由鸽巢原理，$\exists b\in B, |f^{-1}(b)| \geq \left\lceil\frac{|A|}{|B|}\right\rceil = \left\lceil\frac{mn+1}{m}\right\rceil = n + 1$。在集合 $A$ 中取出这 $n+1$ 个元素记为 $a_{1}, a_{2}, \cdots, a_{n+1}$。有 $f(a_{1}) = \cdots = f(a_{n+1}) = b$。

按照 $f$ 的定义，$X$ 中以 $x_{a_{1}}, x_{a_{2}}, \cdots, x_{a_{n+1}}$ 作为最小元的链的最长长度均为 $b$，因此 $x_{a_{1}},x_{a_{2}},\cdots,x_{a_{n+1}}$ 之间任意两个元素都不可比，假设某两个元素可比 $x_{a_{i}} \leq x_{a_{j}}$，那么 $f(a_{i}) = 1 + f(a_{j})$，与 $f(a_{i}) = f(a_{j}) = b$ 矛盾。因此 $x_{a_{1}},x_{a_{2}},\cdots,x_{a_{n+1}}$ 构成了一个长为 $n+1$ 的反链。$\Box$

$8 DAG 上的偏序集

在实际问题中，如果要应用 Dilworth 定理，首先就要把要研究的对象抽象为一个偏序集 $(X, \leq)$，而这里面比较重要的是搞清楚在我们研究的对象 $X$ 上，什么叫 $\leq$。

而在 DAG 中，由于节点之间的关系是有向边，可以基于这些有向边来定义偏序关系。下面顶点集和边集的例子。

偏序集 偏序关系 Dilworth 定理：最小链覆盖
顶点集 点的可达性 DAG 上的最小可重路径点覆盖
边集 边的可达性 DAG 上的最小可重路径边覆盖

偏序集的相关概念总结

本文的概念非常多，并且比较抽象难懂，这里做个汇总。

对于偏序集 $(X, \leq)$，相关的概念总结如下。

  • 链：$Y \subseteq X$，满足 $Y$ 中任意两个元素都可比（$y_{1} \leq y_{2}$ 和 $y_{2} \leq y_{1}$ 必有一个成立），即 $Y$ 构成全序集。
  • 反链：$Y \subseteq X$，满足 $Y$ 中任意两个元素都不可比（$y_{1} \leq y_{2}$ 和 $y_{2} \leq y_{1}$ 均不成立）。即 $Y$ 的任意非空子集都不是全序集。
  • 链覆盖：若干个链的并集为 $X$，且两两之间交集为 $\varnothing$
  • 反链覆盖：若干个反链的并集为 $X$，且两两之间交集为 $\varnothing$
  • 最长链：元素个数最多的链。
  • 偏序集高度：最长链的元素数。
  • 最长反链：元素个数最多的反链。
  • 偏序集宽度：最长反链的元素数。
  • 极小元：$a \in X$，$X$ 中不存在 $b < a$ 的元素 $b$。偏序集的极小元集合形成一条反链。
  • 极大元：$a \in X$，$X$ 中不存在 $b > a$ 的元素 $b$。偏序集的极小元集合形成一条反链。
Share