如何证明三变量拉姆塞数R(3,3,3)=17？

嘿，结合你已经懂二元拉姆塞数的基础，我来一步步给你讲清楚三元拉姆塞数$R(m,n,k)$的定义，以及$R(3,3,3)=17$的完整证明思路～

三元拉姆塞数是二元拉姆塞数的扩展，针对3种颜色的边染色完全图：
$R(m,n,k)$是满足以下条件的最小正整数$N$：只要对$N$个顶点的完全图$K_N$的每条边用3种颜色（比如红、蓝、绿）任意染色，图中必然会出现一个单色的完全子图——要么是红色的$K_m$，要么是蓝色的$K_n$，要么是绿色的$K_k$。

对你问的$R(3,3,3)$来说，它就是最小的$N$：只要把$K_N$的边用3种颜色染，就一定能找到红三角形、蓝三角形或者绿三角形中的一种。

证明拉姆塞数通常要做两件事：先证它不超过某个数，再证它大于前一个数，从而锁定精确值。这里就是要证$R(3,3,3) \leq 17$，同时$R(3,3,3) > 16$。

2.1 第一步：证明$R(3,3,3) \leq 17$ #

我们可以利用你已经知道的二元拉姆塞数$R(3,3)=6$，加上鸽巢原理来推导：

• 任取$K_{17}$中的一个顶点$v$，它和其他16个顶点相连，共16条边，用3种颜色染色。根据鸽巢原理，16条边分到3种颜色里，至少有一种颜色的边数不少于$\lceil 16/3 \rceil = 6$条（毕竟3×5=15，不够16）。
• 假设这6条边都是红色，它们连接的6个顶点构成一个$K_6$。现在看这个$K_6$的边染色：
  • 如果这个$K_6$里存在一条红边，那这条红边的两个端点加上顶点$v$，就构成了一个红三角形；
  • 如果这个$K_6$里没有红边，那它的边只能是蓝、绿两种颜色——而我们已知二元拉姆塞数$R(3,3)=6$，也就是说2色染的$K_6$里必然存在蓝三角形或者绿三角形。
• 不管哪种情况，$K_{17}$里都一定有单色三角形，所以$R(3,3,3) \leq 17$。

2.2 第二步：证明$R(3,3,3) > 16$ #

这一步需要构造一个16个顶点的完全图$K_{16}$的3色边染色方案，让它里面完全没有单色三角形。这个构造用到了有限域的知识：

• 把$K_{16}$的16个顶点对应到有限域GF(16)的16个元素。GF(16)的乘法群是15阶循环群，我们可以把这个群分成3个互不相交的5阶子群$H_1,H_2,H_3$；
• 对任意两个不同的顶点$a,b$，计算$d = a - b$（这里的减法是GF(16)中的加法逆运算），如果$d$不等于0，就看$d$属于哪个5阶子群，给边$ab$染对应的颜色；
• 为什么这个方案里没有单色三角形？假设存在三个顶点$a,b,c$，它们之间的三条边都是同一种颜色，那$a-b$、$b-c$、$c-a$就都属于同一个5阶子群。但在GF(16)中，$(a-b)+(b-c)+(c-a)=0$，而5阶子群里的元素满足$x^5=1$，三个这样的非零元相加为0会导出矛盾（和有限域的多项式性质冲突），所以不可能存在这样的单色三角形。

这个构造说明$K_{16}$可以3色染边且无单色三角形，所以$R(3,3,3) > 16$。

结合上面两步，我们得到$16 < R(3,3,3) \leq 17$，所以$R(3,3,3)$的精确值就是17。

内容的提问来源于stack exchange，提问作者Safder Aree