旭-ASAHI | 【组合数学】Erdős

作者介绍：

北京大学物理专业

这是组合数学中的一个基础定理，在这里随手搬运一下它的几个^[1]巧妙证明。

Theorem (Erdős–Szekeres): 对于
个互不相同实数组成的数列
，一定存在长为
的递增子列或长为
的递减子列。
Remark: 题图是它的几何意义：二维欧式平面上任意
个点总能构造出
条正斜率线段或
条负斜率线段（只要该坐标系下任意两点横纵坐标都不同）

Dilworth定理

简单回顾下集合论中的一些术语。

集合上满足自反性，反对称性和传递性的二元关系称为偏序关系。
装备了偏序关系
的集合
称为偏序集
。

称
中部分元素
为
的链，如果
。
称
中部分元素
为
的反链，如果任意两个元素无序关系。
集合的划分指将其写作一系列不交集合的并。

这样，Erdős–Szekeres定理可以重新表述为：

Theorem (Erdős–Szekeres):

为偏序集

，

,那么

存在长为

的链或长为

的反链。

下面证明Dilworth定理：

Lemma (Dilworth): 偏序集最少的链划分数等于其最长反链长度。
proof: 对偏序集
的元素个数
进行第二归纳，
那么
时，命题显然成立。
假设
时命题成立，下面讨论
的情况：
设
为
中的一个极大元，令偏序集
，由归纳假设，
满足命题。假设
最小的链划分数以及最长反链长度为
，被划分为
这些不相交的链，长度为
的反链为
。记
为
中所有属于长为
的反链的元素中的最大元，
。在
中若存在
,那么
上的任意元素都与
可比。但是
上存在一个元素和
共同属于某个反链，产生矛盾。因此
是反链。
下面考虑偏序集
。如果
与
中每个元素都不可比，那么
是一条长为
的反链，且一定为
中最长反链。由抽屉原理易知，划分
一定是链数最小的划分。(否则
中会出现一对可比元素)
如果
,考虑
,那么集合
中最长反链长度为
。由归纳假设，它最少可以划分为
个链。这些链再加上
构成
的划分。
综上所述，
时命题成立，定理得证。

顺便跑个题，Dilworth定理在OI中有很多应用，比如经典OJ题目[NOIP1999]拦截导弹，其第二问就可以利用该定理，转化为LIS问题，用dp即可方便求解。

Erdős–Szekeres定理就是Dilworth定理的简单推论，使用一次反证即可。读者自证不难。

Mirsky定理

其实这就是Dilworth定理的对偶命题...不过证明容易很多。

Lemma (Mirsky): 偏序集最少的反链划分数等于其最长链长度。
proof: 对
中最长链长度
进行第一归纳：
时集合为单元素集，显然成立。
假设
时命题成立，
时：
设
为
中的极大元集合，那么
为反链，且
最长链长度为
。由归纳假设，
最少可划分为
个反链。那么
可划分为
个反链，这一定是最小值。
综上，命题得证。

1、构造性证明

proof: 将

按照如下算法放置在一系列栈中：
(1)将

推入第一个栈
(2)按顺序扫描所有栈，如果

大于(小于)栈顶元素，将

推入该栈
(3)若没有入栈，建立新栈并让

进入该栈
(4)回到(2),直到遍历全部元素
首先，每个栈都对应一个递增(递减)子列，其次，对于第

个栈中的任意元素

，第

个栈中总能找到比它大(小)的元素。这样，总存在着一条长度和栈数相同的递减(递增)子列。若最长递增(递减)子列长度小于

,那么至少有

个栈。证毕。

2、抽屉原理

proof: 定义函数

定义为以

开头的最长递增子列长度。假如最长递增子列长度小于

，那么

的值域最大只能是

,记之为

。由抽屉原理，

。在该集合中取

个元素

。这里一定有

。否则与

矛盾。这意味着

是单减子列。原命题得证。

3、天秀

proof: 对每个元素

赋予标签

，其中

是以

结尾的最长递增子列长度，

是以

结尾的最长递减子列长度。显然不同元素的标签不会相同，且

。若命题不成立，最多只能提供

个标签，矛盾。原命题得证。

参考

^只选择了前置知识较少的几种证明。更多证明详见此处。 http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。