Erdös Szekersの定理とその証明

更新 2021/03/07

Erdös--Szekeres の定理

$a,b$ を正の整数とする。各項が相異なる長さ $ab+1$ の数列があるとき，以下の二つのうち少なくとも一つは必ず存在する。

長さ $a+1$ の部分列で，単調増加なもの
長さ $b+1$ の部分列で，単調減少なもの

受験や数学オリンピックなどで役に立つことは多分ありませんが，主張＆証明が綺麗な定理で，覚えておきたいレベルです。

Erdös Szekeres の定理の例

具体例として $a=3,b=2$ の場合を考えてみます。適当に $7$ 個の異なる数字を持ってきます：
$1,7,3,6,2,5,4$ このとき，長さ $4$ の単調増加列はありませんが，長さ $3$ の単調減少列（例えば $7,6,5$ ）が発見できます。
上記の例でも分かるように，重要なのは大小関係だけです。よって，各項が整数でない場合も小さい順に番号をつけたものを考えればよいです。例えば $-1.3,3.7,0$ という数列に定理が成立するかどうかは $1,3,2$ という数列に定理が成立するかどうかと同じです。
上記の定理は限界ギリギリです。すなわち，任意の $a,b$ に対して定理の条件 $1,2$ のどちらも満たさない $ab$ 項の数列を取ることができます。例えば $a=3,b=2$ の場合， $4,1,5,2,6,3$ とすれば，長さ $4$ の単調増加列も，長さ $3$ の単調減少列も存在しません。

Erdös Szekeres の定理の図形的な意味

Erdös Szekeres の定理は図形的に見ることもできます。本質的には同じことですが，図形的に表現すると趣が変わって面白いです！

$x-y$ 平面上に異なる $ab+1$ 点を適当に取るとき，以下の二つのうち少なくとも一つは必ず存在する。

$a+1$ 点からなる集合で，それらを $x$ 座標の順に折れ線で結ぶと各線分は右上がりになる。
$b+1$ 点からなる集合で，それらを $x$ 座標の順に折れ線で結ぶと各線分は右下がりになる。

これは， $x$ 座標が小さい順に点に番号を振って， $y$ 座標を数列の各項と見て，数列バージョンを適用したものです。

szekeres

例えば， $a=3,b=2$ の場合，平面上に適当に $7$ 点取ります。図において赤い点は数列の三項目に対応しており，赤い点の $y$ 座標が三項目の値 $a_3$ に対応しています。青い3つの点たちは条件2を満たしているので，確かに定理が成立しています。

Erdös Szekeres の定理の証明

いよいよ証明です。鳩ノ巣原理を用います。（→鳩ノ巣原理の意味と例（身近な例から超難問まで））

証明

考えている数列の一般項を $\{a_n\}$ と書く。 $a_k$ で終わる単調増加な部分列で，長さ最大のものの長さを $p_k$ とおく。同様に， $a_k$ で終わる単調減少な部分列で，長さ最大のものの長さを $q_k$ とおく。

例えば，数列 $2,3,4,1,5$ において，三項目で終わる部分列の中で単調増加かつ長さ最大のものは $\{2,3,4\}$ なので $p_3=3$ となる。単調減少かつ長さ最小のものは $\{4\}$ なので $q_3=1$ となる。

今， $(p_k,q_k)=(p_l,q_l)$ となる $k,l\:(k <l)$ が存在したと仮定する。

$a_k <a_l$ なら $p_k$ に対応する単調増加列に $a_l$ を付け加えたものも単調増加列となるので $p_k+1 \leq p_l$ となり矛盾。
$a_k > a_l$ なら $q_k$ に対応する単調減少列に $a_l$ を付け加えたものも単調減少列となるので $q_k+1 \leq q_l$ となり矛盾。

よって， $(p_k,q_k)$ は各 $k$ ごとに異なる（※）。

Erdös Szekeres の定理が成立しないと仮定すると， $1\leq k\leq ab+1$ に対して $1\leq p_k\leq a$ かつ $1\leq q_k\leq b$ となる。ところが，これらを満たす $(p_k,q_k)$ の組は $ab$ 通りしかないので，鳩ノ巣原理より（※）に矛盾してしまう。

Szekeres の発音をカタカナで書くと「セッカーズ」とか「ゼッカーズ」らしいです。かっこいい名前ですね。

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！