6.3　Ramsey 理论Ramsey theory

证明. 我们对量 \(n+m\) 作归纳。当 \(n+m=2\)（即 \(n=m=1\)）时，结论平凡成立（一个顶点本身就是 \(1\) 个顶点的单色完全子图）。现设 \(n+m>2\) 且结论已对一切更小的 \(n+m\) 证明。若 \(n=1\)，结论同样平凡成立（取 \(R(1,m)=1\)，单个顶点即为 \(1\) 个顶点的蓝色完全子图）；\(m=1\) 时同理。于是可设 \(n,m\ge 2\)。

设 \(G=(V,E)\) 是至少有 \(\binom{n+m-2}{n-1}\) 个顶点的完全图，取任意顶点 \(v\in V\)。这个顶点至少与 \[\binom{n+m-2}{n-1}-1=\binom{n+m-3}{n-2}+\binom{n+m-3}{n-1}-1\] 条边相邻（此处用了 Pascal 恒等式 \(\binom{a}{b}=\binom{a-1}{b-1}+\binom{a-1}{b}\)），每条边非蓝即红。于是由鸽笼原理，要么 \(v\) 至少与 \(\binom{n+m-3}{n-2}\) 条蓝边相邻，要么 \(v\) 至少与 \(\binom{n+m-3}{n-1}\) 条红边相邻。

先假设处于前一种情形。那么我们可以找到 \(G\) 的一个完全子图 \(G'\)，它至少有 \(\binom{n+m-3}{n-2}\) 个顶点，使得 \(G'\) 的每个顶点都通过一条蓝边与 \(v\) 相连。注意 \(\binom{n+m-3}{n-2}=\binom{(n-1)+m-2}{(n-1)-1}\)，于是由归纳假设（把 \((n,m)\) 换成 \((n-1,m)\)），\(G'\) 要么含有一个有 \(n-1\) 个顶点的蓝色单色完全子图 \(G'_{\text{蓝}}\)，要么含有一个有 \(m\) 个顶点的红色单色完全子图 \(G'_{\text{红}}\)。在后一种情形我们已经完成（取 \(G_{\text{红}}:=G'_{\text{红}}\)）；在前一种情形，我们把 \(v\) 添加到 \(G'_{\text{蓝}}\) 上（并补上 \(v\) 与 \(G'_{\text{蓝}}\) 之间的所有连边，按构造它们全是蓝色），就得到 \(G\) 的一个有 \(n\) 个顶点的蓝色单色完全子图 \(G_{\text{蓝}}\)。这就处理完了 \(v\) 至少与 \(\binom{n+m-3}{n-2}\) 条蓝边相邻的情形；当 \(v\) 至少与 \(\binom{n+m-3}{n-1}\) 条红边相邻时，证明完全类似（此时在 \((n,m-1)\) 处使用归纳假设，而非 \((n-1,m)\)）。♦

证明. 我们对 \(m\) 作归纳。\(m=1\) 的情形平凡，\(m=2\) 的情形正是定理 6.9。现归纳地设 \(m>2\) 且结论已对一切更小的 \(m\) 证明。令 \[R(n_1,\dots,n_m;m):=R\bigl(R(n_1,\dots,n_{m-1};m-1),\,n_m;\,2\bigr).\] 假设我们把 \(K_{R(n_1,\dots,n_m;m)}\) 的边染成 \(m\) 个颜色类 \(E_1,\dots,E_m\)。我们把这个边 \(m\)-染色粗化成一个边 2-染色：第一色为 \(E_1\cup\dots\cup E_{m-1}\)，第二色为 \(E_m\)。由归纳假设（其实是 \(m=2\) 的定理 6.9），就这个粗化的染色而言，\(G\) 要么含有一个有 \(n_m\) 个顶点的 \(E_m\)-单色完全子图 \(G_m\)，要么含有一个有 \(R(n_1,\dots,n_{m-1};m-1)\) 个顶点的 \((E_1\cup\dots\cup E_{m-1})\)-单色完全子图 \(G_{1,\dots,m-1}\)。第一种情形已完成；第二种情形，我们把归纳假设再用一次——这次用到完全图 \(G_{1,\dots,m-1}\) 上（它已有足够多顶点，且只用到前 \(m-1\) 种颜色）。这就完成了归纳，从而完成了证明。♦

证明. 设 \(G=G(V,E)\) 是 \(N+1\) 个顶点 \(V:=[1,N+1]\) 上的完全图，并按如下方式把它边 \(m\)-染色为 \(E=E_1\cup\dots\cup E_m\)：让 \(E_j\) 是那些满足 \(|a-b|\in A_j\) 的边 \((a,b)\) 组成的集合（即一条边的颜色由它两端点之差的“所属区间块” \(A_j\) 决定）。由推论 6.12，当顶点数 \(N+1\ge R(k+1,\dots,k+1;m)\) 时，图 \(G\) 必含有一个有 \(k+1\) 个顶点的完全子图 \(G'\)，它对某个 \(r\) 是 \(E_r\)-单色的。若把 \(G'\) 的顶点按大小排成 \(v_0j\)，量 \(c(v_i-v_j)\)（即差 \(v_i-v_j\) 所属的颜色）彼此相等，都等于 \(r\)。于是令 \[x_j:=v_j-v_{j-1}\in A_r\quad(j=1,\dots,k),\] 便有 \(x_1+\dots+x_k=v_k-v_0\in A_r\)，故 \(\{x_1,\dots,x_k,x_1+\dots+x_k\}\subseteq A_r\)，结论得证。♦

命题 6.16 的证明. 为简化记号，本证明中我们用“等差数列”一词泛指格 \(\mathbb{Z}^d\) 中任何真等差数列 \(a+[0,n-1]\cdot v\) 或 \(a+[1,n-1]\cdot v\)，其中 \(a\in[0,n-1]^d\)，\(v\in[0,1]^d\)。

我们使用两个归纳循环。外层循环对 \(n\) 归纳。\(n=1\) 时结论平凡，故设 \(n>1\) 且结论已对 \(n-1\)（以及任意的 \(m,s\)）证明。特别地，由上面的讨论（命题 6.16 ⇒ 定理 6.15），可知我们对 \(n-1\) 而言可以使用定理 6.15。

现在开启内层循环，对 \(s\) 归纳。当 \(s=1\) 时，结论由 \(n-1\) 情形的定理 6.15 推出（把 \([1,n-1]\) 平移成 \([0,n-2]\)）；故设 \(2\le s\le m\) 且结论已对 \(s-1\)（同一 \(n\)、任意 \(m\)）证明。我们令 \[\tilde d:=\tilde d(n,m,s):=d_1+d_2,\quad d_1:=\tilde d(n,m,s-1),\quad d_2:=d\bigl(n-1,\,m^s n^{s d_1}\bigr).\] 设 \([0,n-1]^{\tilde d}=E_1\cup\dots\cup E_m\) 是把它划分成 \(m\) 个不同颜色类。假设没有任何 \(E_j\) 含有长度为 \(n\) 的等差数列。我们的任务便是证明：存在 \(s\) 个不同的类 \(E_{j_1},\dots,E_{j_s}\)、\(a\in[0,n-1]^{\tilde d}\) 以及 \(v_1,\dots,v_s\in[0,1]^{\tilde d}\)，使得 \(a+[1,n-1]\cdot v_i\subseteq E_{j_i}\) 对一切 \(1\le i\le s\) 成立。

我们把 \([0,n-1]^{\tilde d}=[0,n-1]^{d_1}\times[0,n-1]^{d_2}\)（即把 \(\tilde d\) 个坐标拆成前 \(d_1\) 个与后 \(d_2\) 个）。对每个 \(x\in[0,n-1]^{d_2}\)，考察划分 \([0,n-1]^{d_1}=E_{1,x}\cup\dots\cup E_{m,x}\)，其中 \[E_{j,x}:=\{y\in[0,n-1]^{d_1}:(y,x)\in E_j\}.\] 由于没有 \(E_j\) 含长度 \(n\) 的等差数列，故 \(E_{j,x}\) 也都不含。由 \(d_1\) 的定义和内层归纳假设，对每个 \(x\)，存在不同的颜色类 \(j_{1,x},\dots,j_{s-1,x}\)、点 \(a_x\in[0,n-1]^{d_1}\) 与方向 \(v_{1,x},\dots,v_{s-1,x}\in[0,1]^{d_1}\)，使得 \[a_x+[1,n-1]\cdot v_{i,x}\subseteq E_{j_{i,x}}\tag{6.1}\] 对一切 \(1\le i\le s-1\) 成立。注意 \(a_x\) 本身必属于另一个不同于 \(j_{1,x},\dots,j_{s-1,x}\) 的颜色类 \(j_{s,x}\)，否则其中某个 \(E_{j,x}\) 就会含有一条长度为 \(n\) 的等差数列（把端点 \(a_x\) 补上）。若令 \(v_{s,x}:=0\)，则 (6.1) 对 \(i=s\) 也成立——只不过此时数列 \(a_x+[1,n-1]\cdot v_{i,x}\) 不是真的（退化为一点）。这一点将由那 \(d_2\) 个坐标来弥补。

映射 \(x\mapsto(j_{1,x},\dots,j_{s,x},a_x,v_{1,x},\dots,v_{s-1,x})\) 是从 \([0,n-1]^{d_2}\) 到一个基数至多为 \(m^s n^{s d_1}\) 的集合的映射。于是它诱导出 \([0,n-1]^{d_2}\) 的一个划分 \([0,n-1]^{d_2}=F_1\cup\dots\cup F_{m^s n^{s d_1}}\)（某些 \(F_t\) 可能为空）。由 \(d_2\) 的定义与外层归纳假设（再次把 \([1,n-1]\) 平移成 \([0,n-2]\)），我们断定某个颜色类 \(F_t\) 含有一条等差数列 \(a_*+[1,n-1]\cdot v_*\)，其中 \(a_*\in[0,n-1]^{d_2}\)，\(v_*\in[0,1]^{d_2}\)。这意味着存在不同的 \(j_{1,(t)},\dots,j_{s,(t)}\in[1,m]\)、\(a_{(t)}\in[0,n-1]^{d_1}\) 与 \(v_{1,(t)},\dots,v_{s,(t)}\in[0,1]^{d_1}\)（其中 \(v_{s,(t)}=0\)），使得 \(a_{(t)}+[1,n-1]\cdot v_{i,(t)}\subseteq E_{j_{i,x}}\) 对所有 \(x\in a_*+[1,n-1]\cdot v_*\) 与 \(1\le i\le s\) 成立。但若现在令 \(a:=(a_{(t)},a_*)\in[0,n-1]^{\tilde d}\) 与 \(v_i:=(v_{i,(t)},v_*)\in[0,1]^{\tilde d}\)，则可见 \(a+[1,n-1]\cdot v_i\subseteq E_{j_i}\) 对一切 \(1\le i\le s\) 成立，且每条 \(a+[1,n-1]\cdot v_i\) 都是长度为 \(n-1\) 的真等差数列（因为 \(v_*\ne0\) 保证了 \(v_i\ne0\)，即便 \(v_{s,(t)}=0\)）。这就闭合了归纳循环，结论得证。♦

注记 6.18 的论证. 设 \(C_1\) 为最受欢迎的颜色（即元素最多的颜色），\(a_1,\dots,a_{m_1}\) 是被 \(C_1\) 染色的元素。显然 \(m_1\ge N/k\)。由鸽笼原理，存在一个元素 \(x\in Z\)，使得至少有 \(\dbinom{m_1}{2}\big/N\) 对 \((a_i,a_j)\)（\(i♦