Erdős–Szekeres 定理
| 埃尔德什–塞凯赖什定理 | |
|---|---|
| 术语名称 | 埃尔德什–塞凯赖什定理 |
| 英语名称 | Erdős–Szekeres theorem |
Erdős–Szekeres 定理(Erdős–Szekeres theorem)是关于偏序集中给定长度链或反链至少存在一个，或者全序的序列给定长度的单调上升或下降子序列至少存在一个的定理。
定理
偏序集版本
设 [math]\displaystyle{ (P, \preceq) }[/math] 是一个偏序集，如果 [math]\displaystyle{ |P| \geq mn + 1 }[/math]，其中 [math]\displaystyle{ m, n \in \mathbb{N}_+ }[/math] ，则 [math]\displaystyle{ P }[/math] 中必然存在：
序列版本
任意由 [math]\displaystyle{ mn + 1 }[/math] 个不同实数构成的序列中，必然存在：
- 长度为 [math]\displaystyle{ m+1 }[/math] 的递增子序列，或者
- 长度为 [math]\displaystyle{ n+1 }[/math] 的递减子序列。
几何版本
在二维欧几里得平面上，任意 [math]\displaystyle{ mn + 1 }[/math] 个横纵坐标都两两不同的点中，必然存在：
- [math]\displaystyle{ m+1 }[/math] 个点，其横纵坐标都单调递增（形成"上升"点列），或者
- [math]\displaystyle{ n+1 }[/math] 个点，其横纵坐标单调递减（形成"下降"点列）。
说明
Erdős–Szekeres 定理是一个紧界，可基于 [math]\displaystyle{ m \times n }[/math] 的网格结构，构造出大小为 [math]\displaystyle{ mn }[/math] 的偏序集，既不包含长度为 [math]\displaystyle{ m+1 }[/math] 的链，也不包含大小为 [math]\displaystyle{ n+1 }[/math] 的反链， 此时原集合可视为由 [math]\displaystyle{ n }[/math] 条长度为 [math]\displaystyle{ m }[/math] 的链构成的偏序集，所有元素作为结尾的递增序列和递减序列都不超过 [math]\displaystyle{ m }[/math] 和 [math]\displaystyle{ n }[/math] 。
向以上构造的偏序集中增加任何一个元素，由于鸽巢原理，偏序集中或者递增序列数增加导致反链大小达到 [math]\displaystyle{ n+1 }[/math] ，或者链长度增加导致链长度达到 [math]\displaystyle{ m+1 }[/math] 。