Erdős–Szekeres 定理

Erdős–Szekeres 定理
术语名称	Erdős–Szekeres 定理
英语名称	Erdős–Szekeres theorem

Erdős–Szekeres 定理(Erdős–Szekeres theorem)是关于偏序集中给定长度链或反链至少存在一个，或者全序的序列给定长度的单调上升或下降子序列至少存在一个的定理。

定理

对偏序集 [math]\displaystyle{ (S,\preceq) }[/math] ，若有 [math]\displaystyle{ \operatorname{card} S = mn + 1 }[/math] ，其中 [math]\displaystyle{ m, n\in \mathbb{N}_+ }[/math] ，则其中必然：存在长度为 [math]\displaystyle{ m+1 }[/math] 的链，或者，存在长度为 [math]\displaystyle{ n+1 }[/math] 的反链。

其中高度 [math]\displaystyle{ m }[/math] 宽度 [math]\displaystyle{ n }[/math] 的偏序一定能被 [math]\displaystyle{ n }[/math] 条 [math]\displaystyle{ m }[/math] 个元素的链覆盖，此时只有 [math]\displaystyle{ mn }[/math] 个元素构成 [math]\displaystyle{ m }[/math] 级每级 [math]\displaystyle{ n }[/math] 个元素的结构。

等价表述

有 [math]\displaystyle{ mn + 1 }[/math] 个元素的实数列中一定存在长 [math]\displaystyle{ m+1 }[/math] 的上升子序列或长 [math]\displaystyle{ n+1 }[/math] 的下降子序列。

二维 Euclid 平面上任意 [math]\displaystyle{ mn+1 }[/math] 个点若其中任意两点横纵坐标都不同，总能构造出 [math]\displaystyle{ m+1 }[/math] 条正斜率线段或 [math]\displaystyle{ n+1 }[/math] 条负斜率线段。