New Upper Bounds for the Classical Ramsey Numbers $R(4,4,4)$, $R(3,4,5)$ and $R(3,3,6)$

この論文は、古典的なラムゼー数 $R(4,4,4)$、$R(3,4,5)$、$R(3,3,6)$ に対して、従来の既知の不等式による上限を超えた新しい上限値（それぞれ 229、157、91）を導出したことを報告しています。

要約

🎉 物語：巨大なパーティと「同じ色のグループ」

想像してください。世界中から何千人もの人々が集まる**「巨大なパーティ」があるとします。
参加者同士は全員、誰かと握手をします。そして、その握手には「赤」「青」「緑」**など、いくつかの色が付けられています（これが「辺の彩色」です）。

**ラムゼー数（Ramsey Number）とは、こんなルールを破らないために必要な「最小の人数」**のことです。

ルール： 「人数がこれ以上いれば、必ず『全員が赤で握手したグループ』か『全員が青で握手したグループ』ができてしまうぞ！」

例えば、$R(3, 3)$ は「赤か青のどちらかの色で、3 人が全員と握手しているグループ」ができるための最小人数です。これは 6 人です（6 人いれば、必ず赤の三角形か青の三角形ができる）。

🧱 従来の「壁」という考え方

これまで数学者たちは、この「最小人数」を推測する際、**「積み木」**のような考え方をずっと使ってきました。

• 古いルール（定理 1.1）：
  「もし『赤のグループ』を作るのが難しいなら、その人数を少し減らして『赤と青のグループ』を作る問題に置き換えて考えれば、全体の人数の上限（壁）がわかるよ」という方法です。

  これを繰り返すと、「$R(4, 4, 4)$（赤・青・緑の 3 色で、4 人グループができる人数）」の上限は「230 人」という壁が見えていました。
  「もしかしたら 229 人でもできるかも？」と疑う余地はありましたが、証明する手段がなかったのです。

🔍 新しい発見：「3 で割った余り」の魔法

この論文の著者、ルイス・ボザさんは、「積み木」の計算結果を少しだけチェックするだけで、壁を 1 つ下げることに成功しました。

そのチェック方法は、**「3 で割った余り」**を見るという、とてもシンプルなものです。

1. 計算する： 従来の方法で「230 人」という壁を出します。
2. チェックする： その数字（230）を 3 で割ってみます。余りは「2」です（1 ではありません）。
3. 条件を確認する： 関連する他の数字も、3 で割った余りが「1」ではないか確認します。
4. 結論： もし条件が揃えば、**「実は 230 人じゃなくて、229 人でもダメなんだ！」**と証明できるのです。

🌟 なぜそうなるの？（アナロジー）

これを**「三角形の迷路」**に例えてみましょう。

• もし「230 人」のパーティで、誰一人として「同じ色の 4 人グループ」を作れないと仮定します。
• その場合、各人が握手している「赤の握手」の数が、特定の計算式で決まります。
• しかし、著者の計算によると、「赤の握手でできる三角形（3 人グループ）の総数」が、3 で割り切れない数になってしまいます。
• でも、三角形は 3 人で 1 つなので、総数は必ず 3 の倍数（3 で割り切れる数）でなければなりません。
• **「3 で割り切れないはずの数が、3 の倍数でなければならない」**という矛盾が起きるのです。
• つまり、「230 人でもダメだ」という仮定が間違っていたことになります。だから、229 人が新しい上限になります。

🏆 今回の成果：3 つの新しい記録

この「3 で割るチェック」を使って、著者は以下の 3 つの有名な数値を、従来の壁から 1 つ下げることに成功しました。

1. $R(4, 4, 4)$（赤・青・緑、4 人グループ）

   • 以前の壁：230 人
   • 新しい壁：229 人
   • （「230 人いれば必ずできる」と言われていたのが、「いや、229 人でも無理かもしれない（つまり上限は 229）」と修正されました）

2. $R(3, 4, 5)$（赤・青・緑、それぞれ 3 人・4 人・5 人グループ）

   • 以前の壁：158 人
   • 新しい壁：157 人

3. $R(3, 3, 6)$（赤・青・緑、それぞれ 3 人・3 人・6 人グループ）

   • 以前の壁：92 人
   • 新しい壁：91 人

💡 まとめ

この論文は、**「巨大な数のパズルにおいて、従来の計算方法が示した『限界値』が、実は 1 つだけ余分だったことを、シンプルな『3 で割る』というチェックで見抜いた」**という画期的な成果です。

まるで、**「この建物は 230 階まで建てられると言われたが、実は 229 階で止まらなければならないと、小さなひび割れ（3 の余り）から発見した」**ようなものです。

数学の世界では、1 つの数を下げるだけでも大きな進歩であり、将来、より複雑なパズルを解くための新しい道筋を示す重要な一歩となっています。

技術概要

論文「New Upper Bounds for the Classical Ramsey Numbers R(4, 4, 4), R(3, 4, 5) and R(3, 3, 6)」の技術的サマリー

1. 問題の背景と定義

古典的なラムゼー数 $R(k_1, \dots, k_r)$ は、完全グラフ $K_N$ の辺を $r$ 色で彩色したとき、必ず $i$ 番目の色で $k_i$ 個の頂点からなる完全部分グラフ（$K_{k_i}$）が存在するような最小の整数 $N$ として定義されます。

この分野において、$r \ge 3$（3 色以上）の場合の正確な値はほとんど知られておらず、既存の最良の上界は、以下の既知の不等式（定理 1.1）を繰り返し適用することで得られるものが主流でした。

$$R(k_1, \dots, k_r) \le 2 - r + \sum_{i=1}^r R(k_1, \dots, k_i-1, \dots, k_r)$$

この不等式は、右辺が偶数かつ和の項の少なくとも一つが偶数である場合に、厳密な不等式（$\le$ ではなく $<$）となることが知られていますが、それ以外の場合にはこの不等式自体が最良の上界とみなされてきました。

2. 手法と主要な理論的進展

本論文では、上記の標準的な不等式（定理 1.1）から直接導出されない、より tight な上界を導出するための新しい基準（定理 2.1）を提案しています。

定理 2.1 の概要

特定の条件下、標準的な上界 $P(k_1, \dots, k_r)$ から 1 を引いた値が、実際のラムゼー数の上界となることを示しています。
条件は以下の通りです：

1. $P(k_1, \dots, k_r) \not\equiv 1 \pmod 3$ であること。
2. 特定のインデックス $i_0$（$k_{i_0} \ge 4$）が存在し、その部分ラムゼー数 $R(\dots, k_{i_0}-1, \dots)$ が $P(\dots, k_{i_0}-1, \dots)$ に等しく、かつ $1 \pmod 3$ ではないこと。
3. さらに、$k_{i_0}$ を 2 減らしたパラメータを持つラムゼー数 $R(\dots, k_{i_0}-2, \dots)$ も $1 \pmod 3$ ではないこと。

証明の核心:
証明は背理法に基づいています。もし $R = P$ であると仮定すると、$P-1$ 頂点を持つ彩色グラフ $G$ が存在することになります。このとき、任意の頂点 $v$ について、特定の色の次数 $d_{i_0}(v)$ が特定の値に固定され、結果として $v$ が含む特定の色の三角形の数が計算されます。
この三角形の総数を全頂点で合計すると、各三角形が 3 回数えられるため、その総数は 3 の倍数でなければなりません。しかし、上記の条件（モジュロ 3 の条件）を満たす場合、計算される総数は 3 の倍数とならない矛盾が生じます。したがって、$R \le P-1$ が成り立ちます。

3. 主要な結果（新しい上界）

定理 2.1 を適用することで、以下の古典的なラムゼー数について、従来の上界を改善した新しい値が得られました。

• $R(4, 4, 4) \le 229$
  • 従来の上界：$P_3(4) = 230$
  • 改善：1 減少
• $R(3, 4, 5) \le 157$
  • 従来の上界：$P(3, 4, 5) = 158$
  • 改善：1 減少
• $R(3, 3, 6) \le 91$
  • 従来の上界：$P(3, 3, 6) = 92$
  • 改善：1 減少
• $R(\underbrace{3, \dots, 3}_{10}, 4) \le 608,152,553$
  • 従来の上界：$608,152,554$
  • 改善：1 減少

これらの結果は、既知の値（例：$R(3,3,4)=30$, $R(3,5)=14$ など）と定理 1.1 を用いて下界を推定し、定理 2.1 の条件（特にモジュロ 3 の条件）を満たすことを確認することで導かれています。

4. 意義と限界

• 意義:
  • 3 色以上のラムゼー数において、長年更新されていなかった上界を初めて改善した数少ない成果の一つです（以前は $R_4(3) \le 62$ と $R(3,3,4)=30$ の 2 例のみ）。
  • 単なる数値計算ではなく、グラフの構造（三角形の個数とモジュロ演算の関係）に基づいた理論的な制約を利用することで、不等式の厳密性を高める新しいアプローチを示しました。
• 限界:
  • 本論文で得られた改善は、定理 2.1 の条件（特に $1 \pmod 3$ ではないという条件）を満たす場合にのみ適用可能です。
  • 著者は、$r \le 10$ の範囲において、$R(3, \dots, 3, 5)$ や $R(3, \dots, 3, 4, 4)$ などの他の組み合わせについては、定理 1.1 から導かれる上界を超える改善は得られなかったことを付記しています。

結論

本論文は、ラムゼー理論における古典的な上界不等式を、モジュロ 3 の性質と三角形の構造解析を組み合わせることで微調整し、$R(4,4,4)$、$R(3,4,5)$、$R(3,3,6)$ などの重要な数値について、それぞれ 1 ずつ低い新しい上界を確立しました。これは、ラムゼー数の精密化に向けた重要な一歩であり、将来的なより厳密な評価の基礎となる可能性があります。