如何估计Ramsey数的上界？

好的，我们来聊聊如何估算拉姆齐数（Ramsey numbers）的上界。这是一个相当有趣且深刻的数学问题，背后蕴含着组合学和图论的精髓。想要“去除AI痕迹”，那就得抛开那些教科书式的生硬论述，用一种更具探讨性和启发性的方式来展开。

首先，得明白拉姆齐数到底是什么。想象一下，你有足够多的人，无论他们如何组合，总能找到一个特定大小的群体，其中的每个人都认识或都不认识。这就是拉姆齐数想要表达的核心思想：在一个足够大的结构中，总能找到一个具有特定性质的子结构。

以最熟悉的拉姆齐数 $R(m, n)$ 为例，它指的是在一个至少包含 $R(m, n)$ 个顶点的完全图 $K_{R(m,n)}$ 中，无论你用两种颜色（比如红色和蓝色）给所有的边染色，总会存在一个至少有 $m$ 个顶点、所有边都是红色的子图（称为红色团，记作 $K_m$），或者一个至少有 $n$ 个顶点、所有边都是蓝色的子图（称为蓝色团，记作 $K_n$）。

现在，问题来了：这个 $R(m, n)$ 到底有多大？尤其是我们想找到它的上界。意思是，我们想找到一个比 $R(m, n)$ 可能存在的最小值还要大的数，并且这个上界要相对“容易”找到，最好能有一个普适性的方法来计算它。

最直观、也最经典的上界估计方法，是利用“鸽笼原理”和一种称为“图构造法”的策略。

让我们从一个相对简单的例子入手，估计 $R(3, 3)$ 的上界。我们知道 $R(3, 3)$ 的精确值是6，但我们想看看如何找到一个大于6的上界。

假设我们有一张包含 $N$ 个顶点的完全图 $K_N$。我们给它的边涂上红色和蓝色。现在，我们来看任意一个顶点，比如命名为 $v$。这个顶点 $v$ 连接着 $N1$ 条边，每条边都涂成了红色或蓝色。

根据鸽笼原理，如果 $N1$ 比两种颜色中的某一种的顶点数多，那么至少有一条边的颜色会占据多数。更进一步说，如果 $N1$ 足够大，我们总能找到某种“优势”。

考虑顶点 $v$。它连接到 $N1$ 条边。假设其中有 $r$ 条边是红色的，有 $b$ 条边是蓝色的，那么 $r+b = N1$。

现在，我们应用“构造法”：

假设不存在一个红色团 $K_3$ 并且也不存在一个蓝色团 $K_3$。 这是我们的目标是证明，如果 $N$ 足够大，这个假设必然会被打破。

从顶点 $v$ 出发：
如果 $v$ 连接的红色边数量 $r$ 至少是 3（即 $r ge 3$），我们来看这 $r$ 条红边所连接的另外 $r$ 个顶点。假设这 $r$ 个顶点是 $v_1, v_2, dots, v_r$。如果在这些顶点之间任意一对顶点之间存在一条红色边，比如 $(v_i, v_j)$ 是红色的，那么与 $v$ 一起，我们就得到了一个红色团 $K_3$（即 $v, v_i, v_j$）。但我们假设不存在红色团 $K_3$！所以，如果 $r ge 3$，那么在 $v_1, v_2, dots, v_r$ 这 $r$ 个顶点之间，所有的边都必须是蓝色的。如果这 $r$ 个顶点中恰好有3个，比如 $v_1, v_2, v_3$，它们之间所有的边都是蓝色的，那么我们就找到了一个蓝色团 $K_3$！
换句话说，如果 $v$ 连接的红色边数量 $r ge 3$，那么在与 $v$ 相连的红色边所指向的顶点集合中，要避免产生红色团 $K_3$，就必须在这些顶点之间产生蓝色边。如果这些顶点中的任意三个顶点之间都存在蓝色边，那么我们就有了蓝色团 $K_3$。

同样地，如果 $v$ 连接的蓝色边数量 $b$ 至少是 3（即 $b ge 3$），我们来看这 $b$ 条蓝边所连接的另外 $b$ 个顶点。如果在这 $b$ 个顶点之间存在任意一对顶点之间存在一条蓝色边，比如 $(v_i, v_j)$ 是蓝色的，那么与 $v$ 一起，我们就得到了一个蓝色团 $K_3$（即 $v, v_i, v_j$）。但我们假设不存在蓝色团 $K_3$！所以，如果 $b ge 3$，那么在 $v_1, v_2, dots, v_b$ 这 $b$ 个顶点之间，所有的边都必须是红色的。如果这 $b$ 个顶点中恰好有3个，比如 $v_1, v_2, v_3$，它们之间所有的边都是红色的，那么我们就找到了一个红色团 $K_3$！

关键点来了：

我们来看顶点 $v$ 连接的边的数量 $N1$。
如果 $N1 ge 3 + 3 = 6$，那么根据鸽笼原理，无论 $r$ 和 $b$ 是多少，$r+b = N1 ge 6$，那么必然会出现以下两种情况之一：
1. $r ge 3$：这时，与 $v$ 相连的红色边的指向的顶点集合中，如果存在任意三个顶点，它们之间的边全是红色的，那么我们就得到了红色团 $K_3$。反之，如果这些顶点之间的边都是蓝色的，并且有3个这样的顶点，我们就得到了蓝色团 $K_3$。
2. $b ge 3$：同理，如果与 $v$ 相连的蓝色边的指向的顶点集合中，如果存在任意三个顶点，它们之间的边全是蓝色的，那么我们就得到了蓝色团 $K_3$。反之，如果这些顶点之间的边都是红色的，并且有3个这样的顶点，我们就得到了红色团 $K_3$。

这样看来，我们似乎有点绕了。让我们换个角度，用一个更直接的构造性证明来寻找上界。

我们想证明 $R(m, n) le X$，其中 $X$ 是我们要找的上界。考虑一个 $K_X$ 图，其顶点集为 $V$。我们给边着色。

选择任意一个顶点 $v$。它连接到 $X1$ 条边。
假设与 $v$ 相连的红色边至少有 $m1$ 条。设这些边连接到顶点集 $V_r = {v_1, v_2, dots, v_{m1}}$。如果在 $V_r$ 中的任意两个顶点之间都存在一条红色边，那么与 $v$ 一起，我们就构成了一个红色团 $K_m$（$v$ 和 $V_r$ 中的任意 $m1$ 个顶点）。但如果我们假设不存在红色团 $K_m$ 呢？那么，在 $V_r$ 中的任意两个顶点之间，边就必须是蓝色的。如果 $V_r$ 中恰好有 $n1$ 个顶点，并且它们之间的边都是蓝色的，那么我们就得到了一个蓝色团 $K_n$！

同理，假设与 $v$ 相连的蓝色边至少有 $n1$ 条。设这些边连接到顶点集 $V_b = {u_1, u_2, dots, u_{n1}}$。如果在 $V_b$ 中的任意两个顶点之间都存在一条蓝色边，那么与 $v$ 一起，我们就构成了一个蓝色团 $K_n$（$v$ 和 $V_b$ 中的任意 $n1$ 个顶点）。但如果我们假设不存在蓝色团 $K_n$ 呢？那么，在 $V_b$ 中的任意两个顶点之间，边就必须是红色的。如果 $V_b$ 中恰好有 $m1$ 个顶点，并且它们之间的边都是红色的，那么我们就得到了一个红色团 $K_m$！

我们希望找到一个 $X$ 使得上面的推理能够确保产生至少一个我们想要的团。

考虑顶点 $v$ 连接的边。有 $X1$ 条边。设 $r$ 条是红色的，$b$ 条是蓝色的，则 $r+b = X1$。

如果 $r ge m1$，我们考虑这 $m1$ 个顶点。如果它们之间任意两个顶点都连红边，则有红色 $K_m$（包含 $v$）。如果它们之间任意两个顶点都连蓝边，并且我们能凑够 $n1$ 个这样的顶点，就有蓝色 $K_n$。这有点复杂。

Let's try the standard Ramsey number upper bound formula, which is derived from this constructive thinking.

The crucial insight comes from the Ramsey number recursion:

$R(m, n) le R(m1, n) + R(m, n1)$

Let's break down why this is true, again using our constructive approach.
Suppose we have a $K_N$ graph. Pick a vertex $v$. It has $N1$ neighbors. Let's color the edges incident to $v$.
There are $N1$ edges originating from $v$.
Suppose $k$ of these edges are colored red, and $N1k$ edges are colored blue.

Now, consider the set of $k$ neighbors connected to $v$ by red edges. Let this set be $N_r$.
If within $N_r$, there exists a red edge between any two vertices, then together with $v$, these two vertices form a red $K_3$.
Crucially, if within $N_r$, there is no red edge between any pair of vertices, it means that all edges within $N_r$ must be blue.
If this set $N_r$ contains at least $n$ vertices, i.e., $k ge n$, then these $n$ vertices must all be connected by blue edges (since we assumed no red edges within $N_r$). This forms a blue $K_n$.

Similarly, consider the set of $N1k$ neighbors connected to $v$ by blue edges. Let this set be $N_b$.
If within $N_b$, there exists a blue edge between any two vertices, then together with $v$, these two vertices form a blue $K_3$.
If within $N_b$, there is no blue edge between any pair of vertices, it means that all edges within $N_b$ must be red.
If this set $N_b$ contains at least $m$ vertices, i.e., $N1k ge m$, then these $m$ vertices must all be connected by red edges (since we assumed no blue edges within $N_b$). This forms a red $K_m$.

Now, to ensure that we always find either a red $K_m$ or a blue $K_n$, we need to choose $N$ wisely.

We want to guarantee that either the set $N_r$ (if it has size at least $m$) contains a red $K_m$, or the set $N_b$ (if it has size at least $n$) contains a blue $K_n$.

This is where the recursive formula comes from.
Let's say we are trying to prove $R(m, n) le R(m1, n) + R(m, n1)$.
Let $N = R(m1, n) + R(m, n1)$. Consider a $K_N$ graph. Pick a vertex $v$.
The degree of $v$ is $N1$. Let $k$ be the number of red edges from $v$, and $N1k$ be the number of blue edges from $v$.

Case 1: $k ge R(m1, n)$.
The $k$ neighbors connected by red edges form a subgraph. If among these $k$ neighbors, we find a red $K_{m1}$, then together with $v$, we have a red $K_m$. Why? Because if we pick any $m1$ vertices from the $k$ neighbors of $v$ that are connected by red edges, and those $m1$ vertices already form a red $K_{m1}$ among themselves, then adding $v$ to it doesn't create a new red $K_m$. This line of reasoning is slightly off.

Let's restate the core idea for the recursion $R(m, n) le R(m1, n) + R(m, n1)$:
Consider a vertex $v$.
If $v$ is connected to at least $R(m1, n)$ vertices by red edges, let this set of neighbors be $S_r$. If there is a red $K_{m1}$ within $S_r$, we are done (we have a red $K_m$ by adding $v$). If there is no red $K_{m1}$ within $S_r$, then by definition of $R(m1, n)$, this means that $S_r$ must contain a blue $K_n$.
If $v$ is connected to at least $R(m, n1)$ vertices by blue edges, let this set of neighbors be $S_b$. If there is a blue $K_{n1}$ within $S_b$, we are done (we have a blue $K_n$ by adding $v$). If there is no blue $K_{n1}$ within $S_b$, then by definition of $R(m, n1)$, this means that $S_b$ must contain a red $K_m$.

Now, to guarantee that one of these cases happens for any coloring, we need to pick $N$ large enough.
If we set $N = R(m1, n) + R(m, n1)$, then the degree of $v$ is $N1$.
Let $k$ be the number of red edges from $v$.
If $k ge R(m1, n)$, then we are in the first scenario. The set $S_r$ has size at least $R(m1, n)$. If it contains a red $K_{m1}$, we form a red $K_m$. If it does not contain a red $K_{m1}$, it must contain a blue $K_n$. In either case, we find one of the desired monochromatic cliques.
If $k < R(m1, n)$, then the number of blue edges from $v$ is $N1k > (R(m1, n) + R(m, n1)) 1 (R(m1, n) 1) = R(m, n1)$. So, the number of blue edges is at least $R(m, n1)$. We are in the second scenario. The set $S_b$ has size at least $R(m, n1)$. If it contains a blue $K_{n1}$, we form a blue $K_n$. If it does not contain a blue $K_{n1}$, it must contain a red $K_m$. In either case, we find one of the desired monochromatic cliques.

This recursion allows us to establish general upper bounds.
For example, let's reestimate $R(3, 3)$:
$R(3, 3) le R(2, 3) + R(3, 2)$.
By symmetry, $R(m, n) = R(n, m)$, so $R(2, 3) = R(3, 2)$.
What is $R(2, 3)$? It means that in any graph with $R(2, 3)$ vertices, there's either a red $K_2$ (two connected vertices by a red edge) or a blue $K_3$.
Consider a graph with 3 vertices. If we color the edges, we either get three edges of the same color (blue $K_3$) or we get at least one red edge (red $K_2$). So $R(2, 3) = 3$.
Then, $R(3, 3) le 3 + 3 = 6$. This gives us the upper bound of 6, which matches the actual value.

Generalizing this recursion gives a very famous and widely used upper bound:

$R(m, n) le inom{m+n2}{m1}$

Let's try to derive this. We use induction.
Base cases:
$R(2, 2) = 2$. Formula: $inom{2+22}{21} = inom{2}{1} = 2$. Matches.
$R(m, 2) = m$. Formula: $inom{m+22}{m1} = inom{m}{m1} = m$. Matches.
$R(2, n) = n$. Formula: $inom{2+n2}{21} = inom{n}{1} = n$. Matches.

Now, assume the formula holds for all pairs $(m', n')$ such that $m'+n' < m+n$.
We know $R(m, n) le R(m1, n) + R(m, n1)$.
By the induction hypothesis:
$R(m1, n) le inom{(m1)+n2}{(m1)1} = inom{m+n3}{m2}$
$R(m, n1) le inom{m+(n1)2}{m1} = inom{m+n3}{m1}$

So, $R(m, n) le inom{m+n3}{m2} + inom{m+n3}{m1}$.
Using Pascal's identity: $inom{N}{k} + inom{N}{k+1} = inom{N+1}{k+1}$.
Here, $N = m+n3$, $k = m2$.
So, $inom{m+n3}{m2} + inom{m+n3}{m1} = inom{(m+n3)+1}{(m1)} = inom{m+n2}{m1}$.

Therefore, $R(m, n) le inom{m+n2}{m1}$. This is a very significant upper bound.

Let's consider an example for a better understanding of the bound.
For $R(4, 4)$:
The exact value is unknown, but the upper bound is $inom{4+42}{41} = inom{6}{3} = frac{6 imes 5 imes 4}{3 imes 2 imes 1} = 20$.
So, we know $R(4, 4) le 20$.

Can we do better? Yes, this bound is often quite loose. For instance, for $R(3, 3)$, the bound is 6, which is tight. But for $R(5, 5)$, the bound is $inom{5+52}{51} = inom{8}{4} = frac{8 imes 7 imes 6 imes 5}{4 imes 3 imes 2 imes 1} = 70$. The actual value is known to be between 35 and 43. So, the bound 70 is quite far off.

More advanced upper bounds exist, often derived using probabilistic methods or more sophisticated graph constructions.

Probabilistic Method:
This method, pioneered by Paul Erdős, offers a different way to find upper bounds. The idea is to assign colors to edges randomly and then show that with a nonzero probability, the coloring avoids monochromatic cliques. This implies that a monochromatic clique must exist for a sufficiently large number of vertices.

Let's consider $R(k, k)$, which is the smallest $N$ such that any 2coloring of $K_N$ contains a monochromatic $K_k$.
Consider a random coloring of $K_N$. We want to show that the probability of not having a monochromatic $K_k$ is small for large $N$.
The number of $K_k$ subgraphs in $K_N$ is $inom{N}{k}$.
For a specific $K_k$ subgraph, say $K$, what is the probability that all its edges are colored red? There are $inom{k}{2}$ edges in $K_k$. The probability that all are red is $(1/2)^{inom{k}{2}}$.
Similarly, the probability that all edges of $K$ are blue is $(1/2)^{inom{k}{2}}$.
So, the probability that a specific $K_k$ is monochromatic is $2 imes (1/2)^{inom{k}{2}} = (1/2)^{inom{k}{2}1}$.

Let $X_i$ be an indicator random variable for the $i$th $K_k$ subgraph being monochromatic. The total number of monochromatic $K_k$ is $X = sum_{i=1}^{inom{N}{k}} X_i$.
The expected number of monochromatic $K_k$ is $E[X] = sum_{i=1}^{inom{N}{k}} E[X_i] = inom{N}{k} imes 2 imes (1/2)^{inom{k}{2}}$.

If we can make this expected value less than 1, then there must be some colorings where no $K_k$ is monochromatic. This is a bit backwards. We want to show that for a given $N$, every coloring has a monochromatic $K_k$.
The probabilistic method is often used to show that $R(k, k) > f(k)$ for some function $f(k)$.

A common probabilistic bound for $R(k, k)$ is $R(k, k) le inom{2k2}{k1}$. This comes from a different analysis, often involving constructing specific graphs.

The more refined probabilistic argument for $R(k,k)$ leading to an upper bound of $inom{2k2}{k1}$ is as follows:
Let $N = 2k2$. Consider a random coloring of $K_N$.
Pick a vertex $v$. It has $N1 = 2k3$ neighbors.
Let $r$ be the number of red neighbors and $b$ be the number of blue neighbors, $r+b = 2k3$.
If $r ge k1$, consider the $k1$ red neighbors. If any pair of them are connected by a red edge, we have a red $K_3$. If all pairs are connected by blue edges, we have a blue $K_2$. This doesn't seem to lead to the $inom{2k2}{k1}$ bound directly.

The standard result derived from a more careful probabilistic argument is that $R(k, k) le 2^{2k}$. This is a very loose bound.

The bound $inom{2k2}{k1}$ is actually related to a construction by Erdős, proving that $R(k, k) > 2^{k/2}$.

Let's stick to the constructive proof and its generalization using the recursion for clearer understanding of how upper bounds are estimated.

The recursive formula $R(m, n) le R(m1, n) + R(m, n1)$ is the cornerstone for calculating upper bounds. The challenge lies in finding tight bounds for the base cases ($R(m, 2)$ and $R(2, n)$ are $m$ and $n$ respectively) and then applying the recursion.

Consider $R(3, 4)$.
$R(3, 4) le R(2, 4) + R(3, 3)$.
We know $R(2, 4) = 4$ and $R(3, 3) = 6$.
So, $R(3, 4) le 4 + 6 = 10$.
This means in any graph of 10 vertices, we are guaranteed to find either a red $K_3$ or a blue $K_4$.

Can we improve this using other bounds?
We know $R(3, 4) le inom{3+42}{31} = inom{5}{2} = 10$. It seems the recursion is giving the same bound in this case.

Let's try $R(4, 4)$.
$R(4, 4) le R(3, 4) + R(4, 3)$.
Since $R(3, 4) = R(4, 3)$, we need $R(3, 4)$.
From earlier, we established $R(3, 4) le 10$. Let's assume for a moment $R(3,4)$ is indeed 10.
Then $R(4, 4) le 10 + 10 = 20$. This matches the binomial bound $inom{6}{3}=20$.

The process of estimating upper bounds for Ramsey numbers is essentially an iterative application of the recursion $R(m, n) le R(m1, n) + R(m, n1)$, combined with known values for simpler cases (usually $R(k, 2)$ or $R(2, k)$).

Step 1: Identify the target Ramsey number $R(m, n)$.
Step 2: Use the basic upper bound formula if known or simpler bounds. The most fundamental is $R(m, n) le inom{m+n2}{m1}$. This can be obtained through induction as demonstrated.
Step 3: Apply the recursive formula. $R(m, n) le R(m1, n) + R(m, n1)$. To use this, we need bounds for the smaller arguments.
Step 4: Iteratively apply the recursion. Keep breaking down the problem until we reach known base cases, like $R(k, 2)=k$.
Step 5: Sum up the bounds. The final sum provides an upper bound for the original $R(m, n)$.

Example: Estimating $R(5, 5)$

1. $R(5, 5) le R(4, 5) + R(5, 4)$
2. $R(4, 5) = R(5, 4)$. So we need $R(4, 5)$.
3. $R(4, 5) le R(3, 5) + R(4, 4)$
4. $R(3, 5) le R(2, 5) + R(3, 4)$
5. $R(2, 5) = 5$.
6. $R(3, 4) le R(2, 4) + R(3, 3)$
7. $R(2, 4) = 4$.
8. $R(3, 3) = 6$.
9. So, $R(3, 4) le 4 + 6 = 10$.
10. $R(3, 5) le 5 + 10 = 15$.
11. Now we need $R(4, 4)$. As we saw, $R(4, 4) le 20$.
12. $R(4, 5) le 15 + 20 = 35$.
13. Finally, $R(5, 5) le 35 + 35 = 70$.

This iterative process demonstrates how we build up upper bounds. The initial binomial bound $inom{m+n2}{m1}$ is often the starting point for these calculations when specific values of smaller Ramsey numbers aren't immediately known or when we want a general formula.

Key takeaway for estimating upper bounds: The core idea is to guarantee the existence of a monochromatic clique by ensuring that in any graph of a certain size, if we pick an arbitrary vertex, the set of its neighbors connected by edges of the same color is "large enough" to either contain a monochromatic clique directly or, by its complement, to force the existence of one. The recursion $R(m, n) le R(m1, n) + R(m, n1)$ formalizes this "large enough" condition by summing the requirements for smaller problems. The binomial coefficient $inom{m+n2}{m1}$ is a consequence of repeatedly applying this recursion and using the base cases. More advanced bounds require more complex constructive arguments or probabilistic techniques.

命题：
。

证明：根据Ramsey数的定义，只需要证明：

阶完全图用 种颜色染完之后，总存在同色三角形.

用数学归纳法进行证明. 当 时， 结论成立.

假设结论对 的情形成立，即

下证结论对 的情形成立.

设 为 阶完全图, 用 种颜色对 的边染色, 连接顶点 的边的条数是

所以

由抽屉原理, 有至少 条由 连出的边同色, 比如叫红色.

由红边连接 的那些点导出的完全子图记为 , 则 .

如果 中不含红边, 由归纳假设, 中必有同色三角形.

如果 中含红边 , 则可以得到红色三角形 . 因此 必有同色三角形.

---

很久没看组合数学了，不保证上面证明过程正确.