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

[[分类:序理论]]
[[分类:极值集合论]]
{{InfoBox
|name=Erdős–Szekeres 定理
|eng_name=Erdős–Szekeres theorem
}}
'''Erdős–Szekeres 定理'''('''Erdős–Szekeres theorem''')是关于[[偏序集]]中给定长度[[链]]或[[反链]]至少存在一个，或者全序的序列给定长度的[[单调]]上升或下降[[子序列]]至少存在一个的定理。

== 定理 ==

对偏序集 <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>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> 的下降子序列。

[[Euclid 空间（几何）|二维 Euclid 平面]]上任意 <math>mn+1</math> 个点若其中任意两点横纵坐标都不同，总能构造出 <math>m+1</math> 条正斜率线段或 <math>n+1</math> 条负斜率线段。