组合学/拉姆齐数的界

拉姆齐定理中的数字R(r,s)（以及它们对两种以上颜色的扩展）被称为拉姆齐数。拉姆齐理论中一个主要的研究问题是找出各种r和s值的拉姆齐数。我们将在本文中推导出任何一般拉姆齐数R(r,s)的经典边界。这意味着该R(r,s)的精确值位于两个界限之间，即下界和上界。

上界

上界实际上是从拉姆齐定理的证明中推导出来的。由于R(r, s) ≤ R(r − 1, s) + R(r, s − 1)，所以这会自动给出上界，尽管不是我们期望的封闭形式。封闭形式表达式为 $R(r,s)\leq {\binom {r+s-2}{r-1}}$ 。为了推导出这一点，我们对 r 和 s 进行双重归纳。基本情况r = s = 2 很容易确定，因为 $R(2,2)=2\leq {\binom {2+2-2}{2-1}}=2$ 。现在假设表达式对于R(r − 1, s) 和 R(r, s − 1) 成立。然后 $R(r,s)\leq R(r-1,s)+R(r,s-1)\leq {\binom {r+s-3}{r-2}}+{\binom {r+s-3}{r-1}}={\binom {r+s-2}{r-1}}$ 为我们提供了上界。注意，我们在最后一个等价关系中使用了帕斯卡关系。

如果R(r − 1, s) 和 R(r, s − 1) 都是偶数，那么可以进行轻微改进。在这种情况下，不等式是严格的。

结果： 如果R(r − 1, s) + R(r, s − 1) 都是偶数，那么R(r, s) < R(r − 1, s) + R(r, s − 1)。

证明： 假设R(r, s) = R(r − 1, s) + R(r, s − 1)，其中R(r − 1, s) 和 R(r, s − 1) 都是偶数。令n = R(r − 1, s) + R(r, s − 1) − 1。现在，根据我们对n的选择，存在一个在n个顶点上的完全图，即一个K_n，它既没有红色的K_r，也没有蓝色的K_s。在讨论中固定此K_n。同时固定K_n 中的一个顶点v。

现在很明显，如果从v 出发的红色边的数量小于R(r − 1, s) − 1，而蓝色边的数量小于R(r, s − 1) − 1，那么从v 出发的总边数将小于R(r − 1, s) + R(r, s − 1) − 2，这是一个矛盾，因为v 与恰好R(r − 1, s) + R(r, s − 1) − 2 个顶点相连。因此，从v 出发的红色边的数量至少为R(r − 1, s) − 1，或者从v 出发的蓝色边的数量至少为R(r, s − 1) − 1。不失一般性，假设第一个成立。现在我们将证明从v 出发的红色边的数量不能超过R(r − 1, s) − 1。假设它们确实超过了。现在，选择与v 由红色边连接的任何R(r − 1, s) 个顶点，并考虑由这些顶点形成的K_{R(r − 1, s)}。根据拉姆齐定理，它应该包含红色的K_r-1 或者蓝色的K_s。根据我们对n 的选择，它不能包含后者。因此，它包含一个红色的K_r-1。但是，将此红色K_r-1 的顶点与v 连接起来会得到一个红色的K_r，这也是不可能的。因此，红色边的数量不能超过R(r − 1, s) − 1。因此，它们必须恰好是R(r − 1, s) − 1。然后，剩余的蓝色边数为R(r, s − 1) − 1。总之，我们可以说，我们K_n 中的每个顶点都与其他n − 1 个顶点恰好连接了R(r − 1, s) − 1 条红色边和R(r, s − 1) − 1 条蓝色边。

因此，K_n 中红色边的总数为 ${\frac {n(R(r-1,s)-1)}{2}}$ ，它必须是一个整数。但是，由于R(r − 1, s) 和 R(r, s − 1) 都是偶数，所以这是不可能的。因此，初始的等式是不可能的。所以R(r, s) < R(r − 1, s) + R(r, s − 1)。

下界

由保罗·埃尔德什给出的一个论证得出的经典下界在下面给出。该论证被称为概率方法。它为R(r,r) 提供了一个下界，缩写为R(r)。

首先要注意，如果我们在一个随机着色的K_n中给定一组r个顶点，红色或蓝色，那么K_r是单色的概率是 $2^{1-{\binom {r}{2}}}$ 。要了解这一点，请注意，有2种方法可以对 ${\binom {r}{2}}$ 条边中的每一条进行染色，因此染色总数的可能性是 $2^{\binom {r}{2}}$ 。在这些可能性中，只有2种是有利的：红色K_r或蓝色K_r。因此，我们给定的K_r是单色的概率是 $2^{1-{\binom {r}{2}}}$ 。

现在，如果在开始时没有固定一组r个顶点，那么出现单色K_r的概率是多少？有 ${\binom {n}{r}}$ 种方法可以从n个顶点中选择r个顶点。根据概率加法定律，我们可以简单地取任意r个顶点集，得到其概率如上所述为 $2^{1-{\binom {r}{2}}}$ ，然后移动到另一个r个顶点集，得到其概率为 $2^{1-{\binom {r}{2}}}$ ，依此类推；然后我们可以将所有概率加起来得到得到单色K_r的概率。但这可能发生，我们选择的两个r个顶点集都产生了单色K_r。这换句话说，这些事件不一定是互斥的。因此，加法定理不适用，总概率肯定不能保证为 ${\binom {n}{r}}2^{1-{\binom {r}{2}}}$ 。但是，根据布尔不等式，我们至少可以得出结论，K_n中存在单色K_r的概率不能超过 ${\binom {n}{r}}2^{1-{\binom {r}{2}}}$ 。

现在，如果 ${\binom {n}{r}}2^{1-{\binom {r}{2}}}<1$ ，那么这告诉我们，K_n中存在单色K_r的概率小于1，因此K_n中不存在单色K_r。这只是另一种说法，即 $R(r)>n$ 。

现在固定 *r* 并令 *N* 为满足以下不等式的 *n* 的最小值： ${\binom {n}{r}}2^{1-{\binom {r}{2}}}\geq 1$ 。由于满足此不等式的数字集合非空；*R*(*r*) 本身就是一个例子，并且有下界；*r* 和任何小于 *r* 的数字都是不属于此集合的下界，因此保证存在最小值。

还要注意的是， $R(r)\geq N$ ，因为如果 $R(r)<N$ ，那么 $R(r)\leq N-1$ 。但这与 $R(r)>N-1$ 相矛盾，因为 ${\binom {N-1}{r}}2^{1-{\binom {r}{2}}}<1$ 。因此 $R(r)\geq N$ 。

所以，

R(r)\geq N=(N^{r})^{\frac {1}{r}}>\left({\binom {N}{r}}r!\right)^{\frac {1}{r}}\geq (2^{{\binom {r}{2}}-1}r!)^{\frac {1}{r}}=2^{{\frac {r}{2}}-{\frac {1}{2}}-{\frac {1}{r}}}(r!)^{\frac {1}{r}}

现在使用斯特林公式对阶乘进行近似，该公式适用于 *r* 的较大值；即 $r!\approx {\sqrt {2\pi r}}\,\left({\frac {r}{e}}\right)^{r}$ 。因此对于较大的 *r*，简化后得到，

R(r)>{\frac {r2^{\frac {r}{2}}}{e{\sqrt {2}}}}(\left({\frac {\pi }{2}}\right)^{\frac {1}{2r}}r^{\frac {1}{2r}})

.

由于右边的括号内的项始终大于 1，因此我们可以得出结论：对于较大的 *r*， $R(r)>{\frac {r2^{\frac {r}{2}}}{e{\sqrt {2}}}}$ 。

已知的拉姆齐数

下表显示了 *r* 和 *s* 的值在 10 以内的 *R*(*r*,*s*)。如果精确值未知，则表中列出了已知的最佳边界。对于小于 3 的 *r* 和 *s* 的值，*R*(*r*,*s*) 由 *R*(*1*,*s*) = *1* 和 *R*(*2*,*s*) = *s* 给出，适用于所有 *s* 的值。拉姆齐数研究进展的标准调查是由斯塔尼斯拉夫·拉德齐斯佐夫斯基编写的，他还与布伦丹·麦凯一起找到了 *R*(4,5) 的精确值。

r,s	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	9	14	18	23	28	36	40–42
4	1	4	9	18	25	36–41	49–61	59–84	73–115	92–149
5	1	5	14	25	43–48	58–87	80–143	101–216	133–316	149–442
6	1	6	18	36–41	58–87	102–165	115–298	134–495	183–780	204–1171
7	1	7	23	49–61	80–143	115–298	205–540	217–1031	252–1713	292–2826
8	1	8	28	56–84	101–216	134–495	217–1031	282–1870	329–3583	343-6090
9	1	9	36	73–115	133–316	183–780	252–1713	329–3583	565–6588	581–12677
10	1	10	40–42	92–149	149–442	204–1171	292–2826	343-6090	581–12677	798–23556

对角线存在一个微不足道的对称性。

此表摘自由Stanisław Radziszowski编制的更大的表格。

多色示例：R(3,3,3) = 17

多色Ramsey数是使用3种或更多种颜色的Ramsey数。只有一个非平凡的多色Ramsey数其确切值已知，即R(3,3,3) = 17。

假设你有一个使用3种颜色（红色、黄色和绿色）对完全图的边进行着色。进一步假设边着色没有单色三角形。选择一个顶点v。考虑与顶点v有绿色边的顶点集。这被称为v的绿色邻域。v的绿色邻域不能包含任何绿色边，因为否则将存在一个由该绿色边的两个端点和顶点v组成的绿色三角形。因此，在v的绿色邻域上诱导的边着色只有两种颜色，即黄色和红色。由于R(3,3) = 6，v的绿色邻域最多可以包含5个顶点。类似地，v的红色和黄色邻域最多可以包含5个顶点。由于除v本身之外的每个顶点都在v的绿色、红色或黄色邻域之一中，整个完全图最多可以有1 + 5 + 5 + 5 = 16个顶点。因此，我们有R(3,3,3) ≤ 17。

要看到R(3,3,3) ≥ 17，只需在16个顶点的完全图上绘制一个使用3种颜色对边进行着色，该着色避免了单色三角形。事实证明，在K₁₆上恰好有两种这样的着色，即所谓的非扭曲着色和扭曲着色。两种着色都在右图中显示，顶部的非扭曲着色，底部的扭曲着色。在图中的两种着色中，注意顶点都被标记，并且顶点v₁₁到v₁₅在左边和右边都绘制了两次，以便简化绘图。

因此，R(3,3,3) = 17。

已知在K₁₅上恰好有两种使用3种颜色的边着色，它们避免了单色三角形，这些着色可以通过分别从K₁₆上的非扭曲着色和扭曲着色中删除任何顶点来构建。

还已知在K₁₄上恰好有115种使用3种颜色的边着色，它们避免了单色三角形，前提是我们认为颜色排列不同的边着色是相同的。