主题
Search

Erdős-Szekeres 定理


假设 a,b in Nn=ab+1,并且 x_1, ..., x_n 是一个 n 实数 序列。那么这个序列包含一个 单调 递增(递减)子序列,其包含 a+1 项,或者一个 单调 递减(递增)子序列,其包含 b+1 项。

Dilworth 引理 是这个定理的推广。


另请参阅

组合数学, Dilworth 引理

使用 Wolfram|Alpha 探索

参考文献

Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, pp. 54-55, 1998.

在 Wolfram|Alpha 中被引用

Erdős-Szekeres 定理

引用为

Weisstein, Eric W. "Erdős-Szekeres 定理。" 来自 MathWorld-- Wolfram 网络资源。 https://mathworld.net.cn/Erdos-SzekeresTheorem.html

主题分类