Erdős–Szekeresの定理（凸多角形）

要点：(1) から (2) は ex-esz-position (2) と同じ議論である。(2) から (1) は、1 点 $D$ が三角形 $ABC$ の外にあることから、ある辺、たとえば $BC$ を含む直線について $D$ と $A$ が反対側にあることを使う。線分 $AD$ が直線 $BC$ と交わる点が線分 $BC$ の上にあれば、2 本の線分 $AD$ と $BC$ が交わり、$A,B,D,C$ の順に並べると凸の位置になる。交わる点が線分 $BC$ の外にあると、$B$ か $C$ がほかの 3 点の三角形の内部に入ってしまい、(2) に反する。

方針：左端の点 $A$ から見て、残りの 4 点を傾きの順に $B_1,B_2,B_3,B_4$ と並べ、三角形 $T=AB_1B_4$ を考える。$B_2$ か $B_3$ が $T$ の外にあるかどうかで場合を分け、どちらの場合も lem-esz-four の (2) を満たす 4 点を見つける（図 2・図 3）。
段 1（並べる）。$x$ 座標が最小の点を $A$ とし、残りの 4 点はすべて $A$ より右にある。$A$ と各点を結ぶ直線の傾きは、一般の位置なのですべて異なる。傾きの小さい順に $B_1,B_2,B_3,B_4$ と名づける。三角形 $AB_jB_l$ の点は $A+s\overrightarrow{AB_j}+t\overrightarrow{AB_l}$（$s,t\ge0$、$s+t\le1$）と書けるので（点の存在範囲と凸結合）、$A$ 以外の点の $A$ から見た傾きは、$AB_j$ と $AB_l$ の傾きの間にある。
段 2（$B_2$ か $B_3$ が $T$ の外にある場合）。$B_i$（$i=2$ または $3$）が三角形 $T=AB_1B_4$ の内部にないとする。4 点 $A,B_1,B_i,B_4$ が lem-esz-four の (2) を満たすことを確かめる。$A$ は、ほかの 3 点の三角形の点の $x$ 座標がどれも $A$ より大きいので、その内部にない。$B_1$ は、三角形 $AB_iB_4$ の点の傾きが $AB_i$ と $AB_4$ の傾きの間にあり、$AB_1$ の傾きはそれより小さいので、その内部にない。$B_4$ も同じ理由で三角形 $AB_1B_i$ の内部にない。$B_i$ は仮定により $T$ の内部にない。よって lem-esz-four により、この 4 点は凸の位置にある。
段 3（$B_2$、$B_3$ がどちらも $T$ の内部にある場合）。直線 $B_2B_3$ は、一般の位置なので $A$、$B_1$、$B_4$ のどれも通らない。3 点を直線の 2 つの側に分けると、鳩の巣原理 により、同じ側に 2 点がある。それを $U$、$V$ とする。4 点 $U,V,B_2,B_3$ が lem-esz-four の (2) を満たすことを確かめる。

• $U$ は三角形 $VB_2B_3$ の内部にない。この三角形の 3 頂点は $T$ に含まれるので、三角形全体が $T$ に含まれる。三角形の内部の点のまわりの十分小さい円は三角形に含まれ、したがって $T$ に含まれるが、$T$ の頂点 $U$ のまわりの円はどんなに小さくても $T$ からはみ出す。$V$ も同じである。
• $B_2$ は三角形 $UVB_3$ の内部にない。この三角形は直線 $B_2B_3$ の $U$、$V$ の側（直線を含む）にあり、直線とは $B_3$ でだけ出会う。$B_2$ は直線の上の $B_3$ でない点なので、三角形の内部にない。$B_3$ も同じである。
  よって lem-esz-four により、$U,V,B_2,B_3$ は凸の位置にある。$\square$

$y_{k+1}-y_k=s_k(x_{k+1}-x_k)$ なので、$k=i$ から $j-1$ まで足すと
$$ y_j-y_i=\sum_{k=i}^{j-1}s_k(x_{k+1}-x_k) $$
である。両辺を $x_j-x_i>0$ で割ると等式を得る。係数 $\dfrac{x_{k+1}-x_k}{x_j-x_i}$ は正で、和は $\dfrac{x_j-x_i}{x_j-x_i}=1$ である。正の係数で和が $1$ の足し合わせは、各 $s_k$ を最小値に置きかえると小さくなるか等しく、最大値に置きかえると大きくなるか等しいので、最小値以上、最大値以下である。等号は、置きかえで値が変わらないとき、つまりすべての $s_k$ が等しいときだけである。$\square$

方針：カップの場合に、各辺を含む直線に関して残りの点がすべて同じ側にあることを、lem-esz-slope で示す。キャップは上下を裏返すとカップになる。
段 1（辺 $p_ip_{i+1}$、$1\le i\le m-1$）。$p_i$、$p_{i+1}$ を通る直線を $\ell$ とし、その傾きは $s_i$ である。$j\ge i+2$ の点 $p_j$ について、lem-esz-slope により $p_{i+1}$ と $p_j$ を結ぶ傾きは $s_{i+1},\dots,s_{j-1}$ の最小値 $s_{i+1}$ 以上で、$s_i$ より大きい。したがって $y_j-y_{i+1}>s_i(x_j-x_{i+1})$、つまり $p_j$ は $\ell$ より上にある。$j\le i-1$ の点 $p_j$ について、$p_j$ と $p_i$ を結ぶ傾きは $s_j,\dots,s_{i-1}$ の最大値 $s_{i-1}$ 以下で、$s_i$ より小さい。したがって $y_i-y_j< s_i(x_i-x_j)$ で、$y_j>y_i-s_i(x_i-x_j)$、つまり $p_j$ はやはり $\ell$ より上にある。残りの点はすべて $\ell$ より上にある。
段 2（辺 $p_mp_1$）。$1< j< m$ の点 $p_j$ について、$p_1$ と $p_j$ を結ぶ傾き $t_j$ と、$p_1$ と $p_m$ を結ぶ傾き $t$ を比べる。lem-esz-slope の式で、$t$ は $s_1,\dots,s_{m-1}$ の平均で、$t_j$ は前半の $s_1,\dots,s_{j-1}$ の平均である。$t$ は「前半の平均 $t_j$」と「後半 $s_j,\dots,s_{m-1}$ の平均」を正の係数（和が $1$）で足し合わせたもので、後半の平均は $s_j$ 以上、$t_j$ は $s_{j-1}$ 以下なので、後半の平均は $t_j$ より大きい。よって $t>t_j$ で、$p_j$ は直線 $p_1p_m$ より下にある。残りの点はすべて同じ側にある。
段 3（キャップ）。すべての点の $y$ 座標の符号を変えると、傾きの符号がすべて変わり、キャップはカップになる。直線に関して同じ側にあるかどうかは、符号を変えても変わらない。よって段 1・段 2 からキャップも凸の位置にある。$\square$

方針：$a+b$ についての数学的帰納法で示す（数学的帰納法と整列性）。長さ $a-1$ のカップの「最後の点」になれる点を集め、その集まりの中のキャップと、そこで終わるカップをつなぐ（図 4）。
段 1（$a=2$ または $b=2$）。$a=2$ なら $\dbinom{b-2}0+1=2$、$b=2$ なら $\dbinom{a-2}{a-2}+1=2$ である。2 点あれば、その 2 点が長さ $2$ のカップであり、キャップでもある。
段 2（点の数）。$a,b\ge3$ とし、$a+b$ がより小さい場合は正しいと仮定する。二項係数の漸化式（場合の数の数え方の体系）
$$ \binom{a+b-4}{a-2}=\binom{a+b-5}{a-3}+\binom{a+b-5}{a-2} $$
を使う。点の集まり $S$ が $\dbinom{a+b-4}{a-2}+1$ 個以上の点をもち、長さ $a$ のカップも長さ $b$ のキャップもないと仮定して、矛盾を導く。
段 3（最後の点の集まり $E$）。$S$ の点のうち、$S$ の中の長さ $a-1$ のカップの最後の点（$x$ 座標が最大の点）になっているものの集まりを $E$ とする。$S$ から $E$ を除いた集まりには、長さ $a-1$ のカップがない（あれば、その最後の点は $E$ に入るはずである）。長さ $b$ のキャップもない。帰納法の仮定（$a-1$ と $b$ の場合）により、$E$ を除いた集まりの点は $\dbinom{a+b-5}{a-3}$ 個以下である。したがって
$$ E\text{ の点の数}\ \ge\ \binom{a+b-4}{a-2}+1-\binom{a+b-5}{a-3}=\binom{a+b-5}{a-2}+1 $$
である。
段 4（$E$ の中のキャップ）。$E$ には長さ $a$ のカップがない（$S$ にないから）。帰納法の仮定（$a$ と $b-1$ の場合）により、$E$ には長さ $b-1$ のキャップ $d_1,d_2,\dots,d_{b-1}$ がある。$d_1\in E$ なので、$S$ の中に $d_1$ で終わる長さ $a-1$ のカップ $c_1,\dots,c_{a-2},d_1$ がある。
段 5（つなぐ）。$c_{a-2}$ と $d_1$ を結ぶ傾きを $t$、$d_1$ と $d_2$ を結ぶ傾きを $u$ とする。3 点 $c_{a-2},d_1,d_2$ は一直線上にないので $t\ne u$ である。$t< u$ なら、カップ $c_1,\dots,c_{a-2},d_1$ の後に $d_2$ をつなげた列は、傾きが増え続けるので長さ $a$ のカップになる。$t>u$ なら、$c_{a-2}$ の後にキャップ $d_1,\dots,d_{b-1}$ をつなげた列は、傾きが減り続けるので長さ $b$ のキャップになる。どちらも仮定に反する。$\square$

座標軸を選び直して、どの 2 点も $x$ 座標が異なるようにする。lem-esz-cupcap で $a=b=n$ とすると、$\dbinom{2n-4}{n-2}+1$ 個以上の点の中には長さ $n$ のカップか長さ $n$ のキャップがある。lem-esz-cup-convex により、その $n$ 点は凸の位置にある。$\square$