鸽笼原理说,足够大的集合无法在不重复的情况下分配出去。Ramsey 理论问的是更丰富的不可避免的结构:无论怎样用两种颜色给大完全图的边着色,总有一组顶点,它们之间的所有边都同色。本节证明这样的顶点组一定存在,估计图至少要多大,并精确确定第一个非平凡的值。本节用到归纳法、二项式系数,以及前面各计数章节的双重计数技巧。
定义
定义 2.11.1
(单色团与 Ramsey 数)
设 为 个顶点的完全图。 的红蓝着色为每条边指定红色或蓝色之一。若顶点集 中任意两点之间的边都是红色,称 为红团;蓝团同理;含 个顶点的团称为 -团。对整数 ,Ramsey 数 是最小的 ,使得 的每个红蓝着色都含有红 -团或蓝 -团。这个最小值存在,是下面定理的一部分。若 的某个着色既无红 -团也无蓝 -团,称它为 的见证。
由定义立即得到两条性质。红蓝可以互换,所以 。-团没有边,所以单独一个顶点既是红 -团也是蓝 -团:。
概念视角结构
同一个图中的团与独立集
只保留红边。 的红蓝着色就等同于 个顶点上的一个图 :红边是 的边,蓝边是 的非边。红 -团就是 中大小为 的团,蓝 -团就是大小为 的独立集,即 个彼此之间没有 的边的顶点。因此 是最小的 ,使得 个顶点上的每个图都含大小为 的团或大小为 的独立集。用这种语言,对称性 就是取补图;下面 的见证是 -圈,它不含三角形,而它的补图仍是 -圈。
存在性与二项式上界
定理 2.11.2
(两色 Ramsey 定理)
对所有整数 , 存在,并且
此外,对所有 ,
证明
(经由一个顶点对 作归纳)
对 作归纳,并假定 与 存在( 或 的基本情形已知,都等于 )。令 ,取 的任意红蓝着色,并固定一个顶点 。它有 个邻点,分为以红边与 相连的集合 和以蓝边与 相连的集合 。若 且 ,则 ,矛盾。所以 或 。
情形 。 内有红 -团或蓝 -团。若是后者,已达成目标。若是前者,加入 即得红 -团,因为 与 的每个顶点都以红边相连。
情形 。 对称地, 内有红 -团,或有蓝 -团,加入 即成蓝 -团。
无论哪种情形,该着色都含有红 -团或蓝 -团,所以 存在且至多为 。
证明透视
一个顶点的两项任务
固定的顶点 做了两件事。第一,它的 条边按颜色分成 与 ;选取 ,正是为了迫使其中一侧足够大:若两侧都低于各自的门槛,便有 。这是容量不同的鸽笼原理,两个容量分别为 与 。第二, 是被加入到其颜色类内所找到的团的顶点;只有当团的颜色与 引出的边的颜色一致时,扩充才成立: 内的红 -团可以扩充,而 内的蓝 -团则无需扩充。
归纳假设应用于 或 所诱导的子图,它仍是带红蓝着色的完全图;所以与 Ramsey 数比较的是 与 ,而不是 。每一步使 减少一,最终到达 或 的基本情形,归纳因而完成。矛盾只用到 ,所以论证对 个顶点不作任何断言;例如对 ,九个顶点其实已经足够。
证明
(用 Pascal 法则作归纳)
当 或 时,界分别为 或 ,成立。对 ,假定 与 的界成立。由递推式与 Pascal 法则,
例如 ,。
以见证和计数得到下界
下界 需要 的一个既无红 -团也无蓝 -团的着色。第一个简单的族是 :一条红边就是红 -团,所以没有红 -团的着色,所有边都是蓝色;而全蓝的 没有蓝 -团,故 ,与上界合起来得 。
对一般的 ,很难直接找出见证;而概率式的计数论证不需要构造就能给出下界。
定理 2.11.3
(计数下界)
设 。若 ,则 。
证明
(对所有 元集用并集界)
把 的每条边独立地染成红色或蓝色,使全部 个着色等可能。固定的 个顶点张成 条边。恰有 个着色使它成为红团,同样多个使它成为蓝团,所以它单色的概率为 。对 个集合用并集界,某个 元集单色的概率至多为 。因此存在一个着色没有单色 -团,它就是 的见证。
例题
例题 2.11.4
()
上界:由定理,。直接论证:在 的任意着色中,顶点 有五个邻点,所以至少有三条边同色,设为红色,连到 。若 中有一条是红色,它与 构成红三角形;否则 是蓝三角形。
下界:把 的顶点记为 ,当 时边 为红色,当 时为蓝色。红边构成 -圈 ,蓝边构成 -圈 。-圈不含三角形,所以没有单色三角形。于是 ,从而 :任何六个人之中,总有三人两两认识,或三人两两不认识。
例题 2.11.5
( 的上界)
由递推式,。二项式界同样给出 。这些都只是上界。确切值已知为 ,但证明它需要比递推式更精细的论证,这里不作介绍。
例题 2.11.6
(用计数法得到 与 的下界)
当 ,因子为 。取 ,,,所以 。取 ,,,论证到此为止。当 ,因子为 。取 ,,,所以 ;取 ,,论证到此为止。这些界对小的 很弱;方法的价值在于对每个 都适用,见下一例。
例题 2.11.7
(计数界中的指数)
取 ,。利用 得 。当 时为 ;当 时更小,因为 比 增长得更快。所以对所有 有 。例如 时为 。
常见错误与细节
常见错误
(递推式是不等式)
递推式是不等式,不是等式:并没有声称 等于 。证明只表明 个顶点已经足够。
常见错误
(一个着色只确定一个方向)
确定 需要两个方向。上界说明 的每个着色都含团;下界则需要较小完全图上一个具体的、不含这种团的着色。只说明 的某个着色含三角形,对 没有任何说明。
常见错误
(团的颜色必须与 引出的边一致)
单色团指其顶点之间的所有边同色,并不是说这些顶点与某个外部顶点以该色的边相连。在递推式的证明中,从 到 的红边与 内部的边扮演不同角色:只有当 内找到的团的颜色与 到 的边的颜色一致时,才能用 扩充该团。
反例模式
三种颜色时六个顶点不够
断言:既然 , 的边无论用多少种颜色着色,都有单色三角形。取例题中顶点 上的红、蓝两个 圈,加上顶点 ,把它的五条边涂成绿色。红与蓝照旧没有三角形;绿边全都经过顶点 ,任何三条都围不成三角形。定理只涉及两种颜色。同一个顶点论证可以修补三色的情形: 的一个顶点有 条边,所以某种颜色连到 个邻点;它们之间若有一条该色的边就闭合成三角形,否则它们只用两种颜色, 就适用。
计数论证只证明存在性,并不给出具体着色。它说明某个着色没有单色 -团,却没有说明是哪一个。
Ramsey 数由对 取最小值定义。若 的每个着色都有单色团,则对 , 的每个着色也有(限制到 个顶点上),所以这个性质对 单调,“最小的 ”有明确定义。
练习
快速检查
(证明对每个 都有 。)
解答 · 答案
取 的任意红蓝着色。若有一条边为蓝色,它就是蓝 -团。否则所有边都是红色,全部 个顶点构成红 -团。所以 。把 的所有边染红,既没有蓝边,顶点数又少于 ,所以既无红 -团也无蓝 -团;故 ,即 。
快速检查
(把 的顶点集分成 ,,连接 与 的边染红,两端同在 或同在 的边染蓝。找出所有单色三角形,并说明结果如何与 相符。)
解答 · 答案
红边连接 与 ,所以红图是二分图,没有三角形。全蓝的三角形必须完全在 内或完全在 内(同时含两侧顶点的三角形含有 – 的边,那是红色)。 与 各是一个蓝三角形,没有其他的。所以恰有两个单色三角形,都是蓝色。由 , 的每个着色至少有一个,这里恰有两个,与之相符。
快速检查
(利用递推式与 证明 ,并计算 的二项式上界。)
解答 · 答案
由递推式,,其中 见正文。二项式界为 。
快速检查
(对 应用计数下界:证明 在 时成立而在 时不成立,并把结论与真值 比较。)
解答 · 答案
当 时,,所以 。当 时,,不小于 ,论证到此为止。它只证明 ,而真值为 ;计数法对小的 远不够精确。
快速检查
(把两人分为认识或不认识。直接证明在任意 人之中,有三人两两认识,或有四人两两不认识。)
解答 · 答案
在这 人的完全图中,认识的人之间连红边,不认识的人之间连蓝边,并固定一个人 。设 有 个熟人和 个陌生人。若 ,则这 个熟人之中,或有两人彼此认识(与 构成三人两两认识),或所有人两两不认识(至少四人两两不认识)。若 ,则 ;在 的六个或更多陌生人之中,由 ,有三人两两认识或三人两两不认识;三个两两不认识的人加上 即得四个两两不认识的人。每种情形结论都成立。