Erdős–Szekeresの定理(単調部分列)
概要
Erdős–Szekeresの定理(単調部分列)（Erdős–Szekeres theorem on monotone subsequences）とは、整数 $r,s\ge1$ について、相異なる実数からなる長さ $(r-1)(s-1)+1$ の数列は長さ $r$ の増加部分列か長さ $s$ の減少部分列を必ず含む、という組合せ論の定理である。同値な形として、項数は最長の増加部分列の長さと最長の減少部分列の長さの積以下である。各項に「そこで終わる最長の増加・減少部分列の長さ」の組を対応させる鳩の巣原理の証明と、添字の集合を半順序集合とみて Dilworth の定理を使う証明がある。項数 $(r-1)(s-1)$ では成り立たない例があり、平面の点の凸多角形についての同名の定理とは別の定理である。
前提知識: 部分列, 鳩の巣原理, 半順序集合, Dilworthの定理
Erdős–Szekeres の定理(単調部分列)（Erdős–Szekeres theorem on monotone subsequences）とは、$r,s\ge1$ を整数とするとき、相異なる実数からなる長さ $(r-1)(s-1)+1$ の数列は、長さ $r$ の増加部分列か、長さ $s$ の減少部分列を必ず含む、という定理である。項数 $(r-1)(s-1)+1$ は最良であり、長さ $(r-1)(s-1)$ の数列でどちらも含まないものが作れる。たとえば相異なる $10$ 個の実数をどう並べても、$4$ 項の増加部分列か $4$ 項の減少部分列が見つかる。
P. Erdős と G. Szekeres は 1935 年の同じ論文で、この定理と、平面の点の中に凸多角形をなす点が必ずあるという定理の両方を示した（MS12 p. 2）。後者は Erdős–Szekeresの定理(凸多角形) の記事で扱う。この記事が扱うのは数列の単調部分列のほうで、点の配置や凸性は現れない。
この記事では、主定理を「最長の増加部分列の長さと最長の減少部分列の長さの積は項数以上である」という形で述べ、鳩の巣原理による証明（A. Seidenberg による）と、Dilworthの定理 による証明の 2 つを与える。2 つの証明が実は同じ分割を見ていることも確かめる。そのあと最良性を与える数列を構成し、仮定を外したときの反例と、無限数列版・ランダムな置換への広がりを述べる。
定義
実数の有限列 $a=(a_1,\dots,a_N)$ に対し、添字 $1\le i_1< i_2<\cdots< i_\ell\le N$ を選んで得られる列 $(a_{i_1},\dots,a_{i_\ell})$ を $a$ の長さ $\ell$ の 部分列 という。
$$
a_{i_1}< a_{i_2}<\cdots< a_{i_\ell}
$$
のとき 増加部分列、$a_{i_1}>a_{i_2}>\cdots>a_{i_\ell}$ のとき 減少部分列 という。長さ $1$ の部分列は増加部分列でも減少部分列でもある。$a$ の増加部分列の長さの最大値を $L^+(a)$、減少部分列の長さの最大値を $L^-(a)$ と書く（$N\ge1$ なら $L^\pm(a)\ge1$）。
この記事で「増加」「減少」というときは、断らない限り狭義の意味である。項が相異なる列では、2 項はいつも大小が比べられて等しくならないので、狭義と広義の区別は問題にならない。
主定理
$a=(a_1,\dots,a_N)$ を相異なる実数からなる列とする。このとき
$$
N\le L^+(a)\,L^-(a)
$$
が成り立つ。とくに、$r,s\ge1$ について $N\ge(r-1)(s-1)+1$ ならば、$a$ は長さ $r$ の増加部分列か長さ $s$ の減少部分列を含む。
前半の不等式を示せば後半は従う。$L^+(a)\le r-1$ かつ $L^-(a)\le s-1$ なら、前半により $N\le(r-1)(s-1)$ となり仮定に反するからである。$L^+(a)\ge r$ なら最長の増加部分列の先頭の $r$ 項が長さ $r$ の増加部分列を与え、減少の側も同じである。前半の証明は下の 2 つの節で与える（prf-esm-main-pigeonhole、prf-esm-main-dilworth）。
$r=s=n+1$ とおくと「$n^2+1$ 項なら長さ $n+1$ の単調部分列がある」という形になる（鳩の巣原理 の記事の定理「Erdős–Szekeres の定理」）。教科書では $mn+1$ 項から長さ $m+1$ の増加部分列か長さ $n+1$ の減少部分列を導く形で述べることも多い（KT17 Theorem 4.2、p. 59）。これは $r=m+1$、$s=n+1$ とおいたものである。
鳩の巣原理による証明
各添字 $i$ について、$a_i$ で終わる増加部分列の長さの最大値を $p_i$、$a_i$ で終わる減少部分列の長さの最大値を $q_i$ とおく。$a_i$ だけからなる部分列があるので $p_i,q_i\ge1$ であり、定義から $p_i\le L^+(a)$、$q_i\le L^-(a)$ である。
$i< j$ とする。$a_i< a_j$ なら $p_j>p_i$ であり、$a_i>a_j$ なら $q_j>q_i$ である。とくに、項が相異なる列では組 $(p_i,q_i)$ と $(p_j,q_j)$ は異なる。
$a_i< a_j$ とし、$a_i$ で終わる長さ $p_i$ の増加部分列 $a_{i_1}<\cdots< a_{i_{p_i}}=a_i$ をとる。$i_{p_i}=i< j$ かつ $a_i< a_j$ なので、末尾に $a_j$ を付け加えた列は $a_j$ で終わる長さ $p_i+1$ の増加部分列である。よって $p_j\ge p_i+1$ である。$a_i>a_j$ のときは減少部分列について同じ議論をして $q_j\ge q_i+1$ を得る。項が相異なるので $a_i< a_j$ と $a_i>a_j$ のどちらかが成り立ち、いずれの場合も組が異なる。$\square$
lem-esm-labels により、写像
$$
\{1,\dots,N\}\to\{1,\dots,L^+(a)\}\times\{1,\dots,L^-(a)\},\qquad i\mapsto(p_i,q_i)
$$
は単射である。単射の定義域の元の個数は値域の元の個数以下なので（鳩の巣原理）、$N\le L^+(a)L^-(a)$ である。$\square$
この証明は A. Seidenberg（1959 年）による（MS12 p. 2 による紹介）。Erdős と Szekeres の原論文の証明は、必要な項数についての漸化式を立てるものであった（同 p. 2）。
相異なる $10=(4-1)(4-1)+1$ 個の数の列 $a=(6,2,9,4,1,8,3,10,7,5)$ のラベルは次のとおりである。
| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| $a_i$ | 6 | 2 | 9 | 4 | 1 | 8 | 3 | 10 | 7 | 5 |
| $p_i$ | 1 | 1 | 2 | 2 | 1 | 3 | 2 | 4 | 3 | 3 |
| $q_i$ | 1 | 2 | 1 | 2 | 3 | 2 | 3 | 1 | 3 | 4 |
10 個の組 $(p_i,q_i)$ はすべて異なる。$p_8=4$ から長さ $4$ の増加部分列 $2,4,8,10$ が、$q_{10}=4$ から長さ $4$ の減少部分列 $9,8,7,5$ が見つかる。ラベルは左から順に、$p_j=1+\max\{p_i\mid i< j,\ a_i< a_j\}$（そのような $i$ がなければ $p_j=1$）で求まり、$q_j$ も不等号 $a_i< a_j$ を $a_i>a_j$ に替えた式で求まる。
Dilworth の定理による証明
数列を半順序集合に読み替えると、増加部分列は鎖に、減少部分列は反鎖になる（鎖の定義は 鎖(順序集合)）。
$a=(a_1,\dots,a_N)$ を相異なる実数の列とする。添字の集合 $[N]:=\{1,\dots,N\}$ に
$$
i\preceq j\iff i\le j\ \text{かつ}\ a_i\le a_j
$$
で関係を定める。
反射律は明らかである。$i\preceq j$ かつ $j\preceq i$ なら $i\le j\le i$ から $i=j$ なので反対称律が成り立ち、推移律は $\le$ の推移律を 2 つの成分で使えば成り立つ。よって $([N],\preceq)$ は有限半順序集合である。項が相異なるので、$i\ne j$ のとき $i\prec j$ は「$i< j$ かつ $a_i< a_j$」と同じである。
$S=\{i_1<\cdots< i_\ell\}\subset[N]$ とする。$S$ が $([N],\preceq)$ の鎖であることと、$(a_{i_1},\dots,a_{i_\ell})$ が増加部分列であることは同値である。$S$ が反鎖であることと、$(a_{i_1},\dots,a_{i_\ell})$ が減少部分列であることは同値である。したがって、この半順序集合の高さ（鎖の元の個数の最大値）は $L^+(a)$、幅（反鎖の元の個数の最大値）は $L^-(a)$ である。
$S$ が鎖なら、$u< v$ について $i_u$ と $i_v$ は比較可能で、$i_u< i_v$ なので $i_v\preceq i_u$ はありえず $i_u\prec i_v$、すなわち $a_{i_u}< a_{i_v}$ である。逆に増加部分列なら、どの 2 元も $i_u\prec i_v$ で比較可能である。$S$ が反鎖なら、$u< v$ について $i_u\prec i_v$ でないので $a_{i_u}\ge a_{i_v}$、項が相異なるので $a_{i_u}>a_{i_v}$ である。逆に減少部分列なら、$u< v$ について $a_{i_u}>a_{i_v}$ なので $i_u\preceq i_v$ でも $i_v\preceq i_u$ でもない。$\square$
Dilworthの定理 の記事の定理「Dilworthの定理」により、有限半順序集合 $([N],\preceq)$ は幅と同じ個数、すなわち lem-esm-chain-antichain により $L^-(a)$ 個の鎖に分割できる。各鎖は増加部分列を与えるので元の個数は $L^+(a)$ 以下である。よって $N\le L^-(a)\cdot L^+(a)$ である。$\square$
鎖と反鎖の役割を入れ替えて、Mirskyの定理 を使っても同じ結論が出る。高さ $L^+(a)$ と同じ個数の反鎖に分割でき、各反鎖は減少部分列なので元の個数が $L^-(a)$ 以下だからである。
Mirskyの定理 の証明で使う反鎖への分割は、各元 $x$ に「$x$ を最大元とする鎖の元の個数の最大値」を対応させ、その値ごとに元を集めたものである。$([N],\preceq)$ では、$i$ を最大元とする鎖は $a_i$ で終わる増加部分列にほかならないので、この値は鳩の巣原理による証明のラベル $p_i$ そのものである。ex-esm-labels の列では、$p_i=1,2,3,4$ ごとに項を集めた
$$
(6,2,1),\quad(9,4,3),\quad(8,7,5),\quad(10)
$$
がそれぞれ減少部分列になっている。つまり lem-esm-labels の前半は「$p_i$ が等しい項は減少部分列をなす」ことを言っている。同じ組の中では後半により $q_i$ が後ろの項ほど大きいので、各組の項の個数は $L^-(a)$ 以下である。鳩の巣原理による証明は、Mirsky の分割とこの評価を 1 つの単射にまとめたものと読める。数列の定理が順序集合の定理の特別な場合であることは MS12 p. 4 にも述べられている。
最良性
項数 $(r-1)(s-1)+1$ は 1 つも減らせない。
$r,s\ge1$ とし、$k=1,\dots,r-1$ について長さ $s-1$ の減少列
$$
B_k:=\bigl(k(s-1),\ k(s-1)-1,\ \dots,\ (k-1)(s-1)+1\bigr)
$$
をとる。$B_1,B_2,\dots,B_{r-1}$ をこの順につなげた長さ $(r-1)(s-1)$ の列 $b$ は、$1,\dots,(r-1)(s-1)$ を 1 回ずつ並べたものであり、長さ $r$ の増加部分列も長さ $s$ の減少部分列も含まない。
$B_k$ の項はちょうど $(k-1)(s-1)+1$ 以上 $k(s-1)$ 以下の整数なので、$b$ は $1,\dots,(r-1)(s-1)$ を 1 回ずつ並べたものである。$k< k'$ なら $B_k$ のどの項も $B_{k'}$ のどの項より小さい。
増加部分列は同じ $B_k$ から 2 項をとれない（$B_k$ の中では後の項ほど小さい）。よって長さは高々ブロックの個数 $r-1$ である。減少部分列は 2 つのブロックにまたがれない（後のブロックの項は前のブロックの項より大きい）。よって長さは高々 $s-1$ である。$\square$
たとえば $r=4$、$s=3$ では $b=(2,1,4,3,6,5)$ で、長さ $6=3\cdot2$ の列に長さ $4$ の増加部分列も長さ $3$ の減少部分列もない。$r=1$ または $s=1$ のときは空列であり、主定理の後半は「$1$ 項以上の列は長さ $1$ の部分列を含む」という自明な主張になる。KT17 §4.4（p. 64）も同じ種類のブロックの並べ方で最良性を説明している。
prop-esm-sharp の列では、$i\mapsto(p_i,q_i)$ が $\{1,\dots,r-1\}\times\{1,\dots,s-1\}$ への全単射になっている（$B_k$ の $t$ 番目の項のラベルは $(k,t)$）。一般に、主定理の不等式 $N\le L^+(a)L^-(a)$ で等号が成り立つのは、単射 $i\mapsto(p_i,q_i)$ が全単射になるときに限る。
反例
次の表の各行は、主定理の後半の仮定を 1 つだけ外した例である。どの行でも、結論「長さ $r$ の増加部分列か長さ $s$ の減少部分列がある」が成り立たない。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 項数が $(r-1)(s-1)+1$ 以上 | 項数 $(r-1)(s-1)$ の prop-esm-sharp の列。$r=4$、$s=3$ なら $(2,1,4,3,6,5)$ | 長さ $r$ の増加部分列か長さ $s$ の減少部分列があること |
| 項が相異なる | $r=s=2$、項数 $2=1\cdot1+1$ の列 $(0,0)$ | 長さ $2$ の（狭義の）増加部分列か減少部分列があること |
| 項が全順序集合（実数）の元である | $\mathbb R^2$ に成分ごとの順序（$(x,y)\le(x',y')\iff x\le x'$ かつ $y\le y'$）を入れ、$r=s=2$、列 $\bigl((1,2),(2,1)\bigr)$ | 長さ $2$ の増加部分列か減少部分列があること |
2 行目の列の 2 項は等しいので、どちらの向きの狭義の不等式も成り立たない。3 行目の 2 項は比較できないので、$(1,2)<(2,1)$ も $(1,2)>(2,1)$ も成り立たない。一般に、相異なる 2 元がいつも比較できる（全順序である）ことが lem-esm-labels の「どちらかが成り立つ」の部分で使われている。
補足
広義の単調部分列
項の重複を許すと 2 行目の反例があるが、一方の向きを広義にすれば定理は残る。
$r,s\ge1$ とし、$a=(a_1,\dots,a_N)$ を実数の列（重複を許す）、$N\ge(r-1)(s-1)+1$ とする。このとき、$a_{i_1}\le\cdots\le a_{i_r}$ となる長さ $r$ の部分列か、長さ $s$ の（狭義の）減少部分列がある。
$a_i\ne a_j$ となる組についての $|a_i-a_j|$ の最小値を $\delta$ とし（そのような組がなければ $\delta=1$）、$0<\varepsilon<\delta/N$ をとって $b_i:=a_i+\varepsilon i$ とおく。$a_i< a_j$ なら $b_j-b_i>\delta-\varepsilon N>0$ なので $b_i< b_j$ であり、$a_i=a_j$ かつ $i< j$ なら $b_i< b_j$ である。よって $b_i$ は相異なり、$i< j$ について $b_i< b_j\iff a_i\le a_j$、$b_i>b_j\iff a_i>a_j$ が成り立つ。$b$ に thm-esm-main を当てれば、$b$ の長さ $r$ の増加部分列は $a$ の広義の増加部分列を、長さ $s$ の減少部分列は $a$ の減少部分列を与える。$\square$
無限数列
相異なる実数の無限列 $(a_n)_{n\ge1}$ は、無限の増加部分列か無限の減少部分列を含む。
添字 $m$ が 山 であるとは、すべての $n>m$ について $a_m>a_n$ が成り立つことをいう。山が無限個あるとき、それを小さい順に $m_1< m_2<\cdots$ と並べると、$m_k$ が山で $m_{k+1}>m_k$ なので $a_{m_k}>a_{m_{k+1}}$ であり、無限の減少部分列が得られる。山が有限個のとき、すべての山より大きい添字 $n_1$ をとる。$n_1$ は山でないので $n_2>n_1$ で $a_{n_2}\ge a_{n_1}$、項が相異なるので $a_{n_2}>a_{n_1}$ となるものがある。$n_2$ も山でないので同様に $n_3>n_2$ で $a_{n_3}>a_{n_2}$ となるものがあり、これを続けて無限の増加部分列が得られる。$\square$
prf-esm-infinite で項が相異なることを使ったのは、最後に $a_{n_2}\ge a_{n_1}$ を $a_{n_2}>a_{n_1}$ に強める所だけである。したがって一般の実数列も、無限の減少部分列か、無限の広義の増加部分列を含む。有界な実数列では単調な部分列は収束するので、Bolzano–Weierstrassの定理 の 1 つの証明になる（Ramsey理論 の記事でも同じ見方が述べられている）。
全順序集合への一般化
証明で使ったのは、項の間の順序が全順序であることだけである。したがって、thm-esm-main は、実数を任意の全順序集合の元に替えてもそのまま成り立つ。たとえば $\{1,\dots,N\}$ の置換 $\pi$ を列 $(\pi(1),\dots,\pi(N))$ と見ると、$L^+(\pi)L^-(\pi)\ge N$ であり、とくに $\max(L^+(\pi),L^-(\pi))\ge\sqrt N$ である。
盤の形による見方
置換 $\sigma$ に Robinson–Schensted 対応で Young 図形 $\lambda$ を対応させると、$L^+(\sigma)$ は第 $1$ 行の箱の個数に、$L^-(\sigma)$ は行の個数に等しい（Schensted の定理。Robinson–Schensted–Knuth対応 の記事の系「Schenstedの定理」）。図形の箱の個数は $N$ なので、$N\le L^+(\sigma)L^-(\sigma)$ が箱を行と列で数えるだけで出る。これは主定理の 3 つ目の証明であり、同じ記事の定理「Greeneの定理」は $k$ 個の増加部分列の和集合の大きさまで決める精密化である。
ランダムな置換
主定理は、$\{1,\dots,n\}$ のすべての置換 $\pi$ について $\max(L^+(\pi),L^-(\pi))\ge\sqrt n$ を保証する最悪の場合の評価であり、prop-esm-sharp の列（$r=s$ の場合）のように $L^+$ も $L^-$ も $\sqrt n$ 程度にとどまる置換もある。典型的な置換では、最長の増加部分列はこれより長い。$\{1,\dots,n\}$ の置換を一様に無作為に選んだときの最長の増加部分列の長さを $\ell(\pi_n)$ とすると、
$$
\frac{\ell(\pi_n)}{\sqrt n}\to2\qquad(n\to\infty)
$$
が、置換の列を Poisson 点過程から同じ確率空間の上に作る構成のもとで概収束の意味で成り立つ（極限の存在は Hammersley の方法により劣加法的エルゴード定理から従い、極限値が $2$ であることは Logan–Shepp と Vershik–Kerov による。Dur19 Example 6.5.2、pp. 348–349）。この記事では証明しない。主定理が $\max(L^+,L^-)$ について保証する $\sqrt n$ と、最長の増加部分列の典型的な値 $2\sqrt n$ は同じ大きさの程度である。
凸多角形の定理との違い
Erdős–Szekeresの定理(凸多角形) は、一般の位置にある平面の点が十分多ければ凸 $n$ 角形をなす $n$ 点があるという定理で、必要な点の数の上からの評価は二項係数 $\binom{2n-4}{n-2}+1$ である（MS12 p. 2）。単調部分列の定理では必要な項数が $(r-1)(s-1)+1$ と正確に決まるのに対し、凸多角形の定理では正確な値は $n\le6$ でしか分かっていない（Erdős–Szekeresの定理(凸多角形) の記事の表）。証明の道具も違い、凸多角形の定理の証明では、点の並びの傾きを使う議論（カップとキャップ）や Ramseyの定理 を使う。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
