查看“︁Erdős–Szekeres 定理”︁的源代码

[[分类:序理论]]
[[分类:极值集合论]]
[[分类:以 Erdős 命名]]
[[分类:以 Szekeres 命名]]{{DEFAULTSORT:erdos szekeres ding4li3}}
{{#seo:
|keywords=Erdős–Szekeres定理, 埃尔德什–塞凯赖什定理
|description=本文介绍Erdős–Szekeres定理的定义、内容和应用，包括在偏序集中链与反链的存在性、实数序列中单调子序列的存在性、及其几何意义。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2024-02-29
}}
{{InfoBox
|name=埃尔德什–塞凯赖什定理
|eng_name=Erdős–Szekeres theorem
}}
'''Erdős–Szekeres 定理'''('''Erdős–Szekeres theorem''')是关于[[偏序集]]中给定长度[[链]]或[[反链]]至少存在一个，或者全序的序列给定长度的[[单调]]上升或下降[[子序列]]至少存在一个的定理。

== 定理 ==

=== 偏序集版本 ===
设 <math>(P, \preceq)</math> 是一个偏序集，如果 <math>|P| \geq mn + 1</math>，其中 <math>m, n \in \mathbb{N}_+</math> ，则 <math>P</math> 中必然存在：
* 长度为 <math>m+1</math> 的[[链]]，或者
* 大小为 <math>n+1</math> 的[[反链]]。

=== 序列版本 ===
任意由 <math>mn + 1</math> 个不同实数构成的序列中，必然存在：
* 长度为 <math>m+1</math> 的递增子序列，或者
* 长度为 <math>n+1</math> 的递减子序列。

=== 几何版本 ===
在二维欧几里得平面上，任意 <math>mn + 1</math> 个横纵坐标都两两不同的点中，必然存在：
* <math>m+1</math> 个点，其横纵坐标都单调递增（形成"上升"点列），或者
* <math>n+1</math> 个点，其横纵坐标单调递减（形成"下降"点列）。

== 说明 ==

Erdős–Szekeres 定理是一个紧界，可基于 <math>m \times n</math> 的网格结构，构造出大小为 <math>mn</math> 的偏序集，既不包含长度为 <math>m+1</math> 的链，也不包含大小为 <math>n+1</math> 的反链，
此时原集合可视为由 <math>n</math> 条长度为 <math>m</math> 的链构成的偏序集，所有元素作为结尾的递增序列和递减序列都不超过 <math>m</math> 和 <math>n</math> 。

向以上构造的偏序集中增加任何一个元素，由于[[鸽巢原理]]，偏序集中或者递增序列数增加导致反链大小达到 <math>n+1</math> ，或者链长度增加导致链长度达到 <math>m+1</math> 。