対角ラムゼー数の上界

$R(k,l)$は、赤い$K_k$か青い$K_l$が必ず現れる最小の点の数とする。

1. 青い$K_2$は線1本なので、青い線が1本でもあればそれで足りる。すべての線が赤なら、赤い$K_k$には$k$点が要る。

   $$R(k,2)=R(2,k)=k,R(k)=R(k,k)$$

2. $R(k-1,l)+R(k,l-1)$点を塗ったとして、1点$v$を選ぶ。残りの点は、$v$と赤で結ばれた組$A$と、青で結ばれた組$B$に分かれる。2つの組の大きさを足すと決まった数になるので、どちらかは大きい。

   $$|A|+|B|=R(k-1,l)+R(k,l-1)-1$$

3. $|A|\ge R(k-1,l)$なら、$A$の中に赤い$K_{k-1}$か青い$K_l$がある。赤い$K_{k-1}$はどの点も$v$と赤で結ばれているので、$v$を足すと赤い$K_k$になる。$|B|\ge R(k,l-1)$のときも同じである。

   $$R(k,l)\le R(k-1,l)+R(k,l-1)$$

4. この漸化式はパスカルの三角形と同じ形をしていて、帰納法で二項係数の上界になる（計算は次の章）。

   $$R(k)\le \left(\genfrac{}{}{0ex}{}{2k-2}{k-1}\right)<4^{k-1}$$

5. 同じ議論は、点を1つずつ仕分ける手順としても読める。候補の集まり$X$から1点を選び、赤い隣と青い隣の多いほうを新しい$X$にして、選んだ点を赤か青の組に入れる。$2^{2k-1}$点あれば$2k-1$回続けられ、どちらかの組に$k$点がたまる。底の4は、1回で半分を捨てることから来ている。

   $$|X_{j+1}|\ge \frac{|X_j|-1}{2}$$

6. 下からは、線を1本ずつ硬貨で赤か青に塗る。決めた$k$点を結ぶ$\left(\genfrac{}{}{0ex}{}{k}{2}\right)$本がすべて同じ色になる確率は$2\cdot 2^{-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}$である。同じ色の$k$点組の個数は整数なので、その期待値が1より小さければ、1つもできない塗り方が少なくとも1つある。

   $$\left(\genfrac{}{}{0ex}{}{n}{k}\right)2^{1-\left(\genfrac{}{}{0ex}{}{k}{2}\right)}<1⟹R(k)>n$$

7. $n\le 2^{k/2}$なら、$k\ge 3$で手順6の条件が満たされる（次の章）。上と下を合わせると、$R(k)$は2つの指数関数にはさまれる。

   $${\sqrt{2}}^k<R(k)<4^k$$

8. 4を下げるために、カンポスら4人は赤い「ブック」を探した。互いに赤で結ばれた$t$点の背$S$と、$S$のすべての点と赤で結ばれた点の集まり、ページ$T$の組である。$T$の中に赤い$K_{k-t}$があれば、$S$と合わせて赤い$K_k$になる。この見方は、ラムゼーの論文までさかのぼる。

   $$|T|\ge R(k-t,k)⟹\text{赤い}{K}_k\text{か青い}{K}_k\text{がある}$$

9. ブックを組み立てるときは、赤い組$A$と青い組$B$のほかに、点の集まり$X$と$Y$を持つ。$A$から$X$と$Y$へはすべて赤、$B$から$X$へはすべて青という性質を保ちながら、$X$と$Y$を結ぶ赤い線の割合$p$を見張る。手は3つある。赤い組に1点を足す手、青い組に何点もまとめて足す手、$p$を押し上げる手である。押し上げる手では、$X$の中で青い隣が少ない点$x$を$B$に入れ、$X$を$x$の青い隣に、$Y$を$x$の赤い隣に絞る。

   $$p=\frac{e_R(X,Y)}{|X||Y|}$$

10. 最後に残る$(A,Y)$は赤いブックで、手順8の条件はほとんどの場合に満たされる。満たされないのは、$A$の点の数と$p$を押し上げた回数が、それぞれ$4k/5$と$4k/9$に近い狭い場合だけである。そこは、$l$が$k$より小さい$R(k,l)$を指数の分だけ改良した評価を、$Y$の中で使って埋める。完全な証明は約60ページある。

    $$R(k)\le (4-\epsilon {)}^k(\epsilon =2^{-7},k\text{が十分大きいとき})$$