未解決問題、組合せ論と離散数学、1930年に提起

ラムゼー数 R(5,5) の値

未解決

対角ラムゼー数 $R(5, 5)$ の正確な値を決定せよ。すなわち、完全グラフ $K_n$ の辺の任意の $2$ -彩色が単色の $K_5$ を含む（同値な言い換えとして、 $n$ 頂点の任意の単純グラフがサイズ $5$ のクリークまたはサイズ $5$ の独立集合を含む）ような最小の正の整数 $n$ を求めよ。

研究の最前線 2026年時点

2026年現在、最良の評価は $43 \le R(5, 5) \le 46$ である。下界の $43$ は既知の $656$ 個の $(5, 5, 42)$ -グラフ（ $328$ 個のグラフとその補グラフの対）から得られており、大規模なヒューリスティック探索でも $(5, 5, 43)$ -グラフが一つも見つかっていないことから、マッケイとラジショフスキは $R(5, 5) = 43$ と予想している。上界の $R(5, 5) \le 46$ はアンゲルトヴェイトとマッケイ（2024年プレプリント）によるもので、辺・三角形・4頂点部分グラフの密度に関する線形計画法と $(4, 5, k)$ -部分グラフの大規模並列拡張を組み合わせている。

既知の最良の結果

正確な値は $43 \le R(5, 5) \le 46$ を満たす（下界は1989年のエクソー、上界は2024年のアンゲルトヴェイトとマッケイのプレプリントによる）。
同型でない $(4, 5, 24)$ -グラフはちょうど $350,904$ 個存在し、それらの近傍貼り合わせ条件が $n \ge 43$ に対する仮想的な $(5, 5, n)$ -グラフを強く制約する。

使われた手法と限界

手法	達成したこと	限界
部分グラフ密度の線形計画法と近傍拡張（マッケイ・ラジショフスキ、アンゲルトヴェイト・マッケイ）	$(5, 5, n)$ -グラフの任意の頂点の隣接集合と非隣接集合がそれぞれ $(4, 5, d)$ -グラフと $(5, 4, n - 1 - d)$ -グラフでなければならないことを用いて、 $n = 49, 48, 47$ を排除した。	$n$ が $43$ に近づくと頂点次数 $d$ が $19 \le d \le 22$ の範囲に入り、 $(4, 5, d)$ -グラフの同型類の総数が数兆個規模へと爆発する。

未解決の問い

マッケイとラジショフスキが予想した通り $R(5, 5) = 43$ であるか。
既知の $656$ 個の $(5, 5, 42)$ -グラフは、単色の $K_5$ を避ける極値的な $42$ 頂点グラフのすべてを尽くしているか。

参考文献

Geoffrey Exoo (1989). A lower bound for r(5, 5) · DOI:10.1002/jgt.3190130113
Brendan D. McKay, Stanisław P. Radziszowski (1997). Subgraph counting identities and Ramsey numbers · DOI:10.1006/jctb.1996.1741
Vigleik Angeltveit, Brendan D. McKay (2024). R(5,5) <= 46 · arXiv:2409.15709 [プレプリント・未査読]