未解决问题，组合数学与离散数学，1930年提出

拉姆齐数 R(5,5) 的精确值

未解决

确定对角拉姆齐数 $R(5, 5)$ 的精确值：即求最小的正整数 $n$ ，使得对完全图 $K_n$ 的边进行任意 $2$ -染色都必含一个同色的 $K_5$ 副本（等价地，任意 $n$ 顶点简单图必含规模为 $5$ 的团或规模为 $5$ 的独立集）。

研究前沿截至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, 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 [预印本,未经同行评审]