术语

Erdős–Szekeres 定理

一列互不相同的数里,最长上升子列的长度乘最长下降子列的长度,不小于这列数的个数。

别名 · 埃尔德什–塞凯赖什定理 · 最长上升 × 最长下降 ≥ N

在第 1 讲里

1935 年由 Paul Erdős 和 George Szekeres 发表。证明可以用抽屉原理:给每一项配一个数对(以它结尾的最长上升子列长、最长下降子列长),任何两项的数对都不同。2025 年 IMO 第六题证明下界(不少于 2112 块)时用到它。

参考资料