数组合数学

组合数学拾遗2-偏序集,Dilworth定理

字数统计: 1.6k字   |   阅读时长: 6分
, , ,

摘要: 偏序集、Dilworth定理

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

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

本文我们整理一些此前没有提到但还比较有用的概念，包括偏序集以及相关的概念、Diworth 定理。参考《组合数学》冯荣权 $1-2。

$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 定理对偶形式

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

证明

偏序集 $(X, \leq)$ 高度为 n 也就是 X 的最长子链长度为 n，因此 X 不可能划分成更少的反链。

对 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$ 个反链。

Dilworth 定理

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

证明

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

对 $|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$ 个链。

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

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