Erdős–Szekeres 定理：修订间差异

2025年10月27日 (一) 05:48的最新版本

埃尔德什–塞凯赖什定理
术语名称	埃尔德什–塞凯赖什定理
英语名称	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{ m+1 }[/math] 的链，或者
大小为 [math]\displaystyle{ n+1 }[/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] 。

@@ 第1行： / 第1行： @@
 [[分类:序理论]]
 [[分类:极值集合论]]
+[[分类:以 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=Erdős–Szekeres 定理
+|name=埃尔德什–塞凯赖什定理
 |eng_name=Erdős–Szekeres theorem
 }}
@@ 第9行： / 第17行： @@
 == 定理 ==
-对偏序集 <math>(S,\preceq)</math> ，若有 <math>\operatorname{card} S = mn + 1</math> ，其中 <math>m, n\in \mathbb{N}_+</math> ，则其中必然：存在长度为 <math>m+1</math> 的链，或者，存在长度为 <math>n+1</math> 的反链。
+=== 偏序集版本 ===
+设 <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>m</math> 宽度 <math>n</math> 的偏序一定能被 <math>n</math> 条 <math>m</math> 个元素的链覆盖，此时只有 <math>mn</math> 个元素构成 <math>m</math> 级每级 <math>n</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> 。
-[[Euclid 空间（几何）|二维 Euclid 平面]]上任意 <math>mn+1</math> 个点若其中任意两点横纵坐标都不同，总能构造出 <math>m+1</math> 条正斜率线段或 <math>n+1</math> 条负斜率线段。
+向以上构造的偏序集中增加任何一个元素，由于[[鸽巢原理]]，偏序集中或者递增序列数增加导致反链大小达到 <math>n+1</math> ，或者链长度增加导致链长度达到 <math>m+1</math> 。