数组合数学

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

字数统计: 1.1k字   |   阅读时长: 4分
,

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