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

  |  

摘要: 偏序集、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