组合数学拾遗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)$ 的宽度为 m,则存在划分 $X = \bigcup\limits_{i=1}\limits^{m}C_{i}$,使得每个 $C_{i}$ 都是反链。

Dilworth 定理对偶形式

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


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

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

Share