动机
极值图论定理问的是:多少条边会迫使图中出现某个特定子图。Ramsey 问题则是给每条边染上一种颜色,问某一种颜色中是否必然含有完全图。两种颜色都可以有很多条边,所以仅仅知道边的总数并不能解决问题。真正有用的信息是:两个颜色类在一个顶点周围如何相互作用。
这里有两类不同的任务。上界必须对每一种染色都成立;下界则只需要一种染色,使其同时避开两个被禁止的团。我们先通过不断限制到邻点集合来建立普遍性保证,再构造一个精确的小规模障碍,并用一个有限随机试验证明更大的障碍存在。这些存在性陈述都没有给出寻找最优染色的快速算法,也没有确定所有 Ramsey 数。
以下论证只使用初等计数和有限概率,不假设任何渐近 Ramsey 估计。
定义
定义 10.5.1
(二色阈值及其量词)
对正整数 与 ,令 为最小的正整数 ,使得完全简单图 的每一种红/蓝边染色都含有 个顶点的红色团,或 个顶点的蓝色团。单个顶点的团没有边,对任一颜色的要求都自动满足。这个最小整数的存在性将在下文证明。
若一种染色中两个指定的团都不出现,则称它避开数对 。因此, 个顶点上的一种避开染色证明 ;而 个顶点上的一个普遍性论证证明 。
交换颜色的名称即得对称性 。把染色限制到顶点子集上可知:一旦普遍性在 处成立,它在任何更大的阶数处也成立。边界值 由单点约定得出。对于两个或更多顶点,给一条边染色就是在它的两种颜色中选择一种,并不要求两种颜色都出现。
定义 10.5.2
(多色边染色与单色团)
对整数 , 的一个 -染色给每条边指定 种颜色之一。若 个互不相同的顶点之间的全部 条边都同色,则称它们张成一个单色 -团。
正常顶点染色(相邻顶点必须不同色)是另一个概念;这里的颜色属于边,共用顶点的边可以同色。
定理
定理 10.5.3
(邻域递推证明有限性与二项式上界)
对 ,
所有这些有限阈值都存在,并且
特别地,对每个 都有 。
定理 10.5.4
(有限随机试验给出避开染色)
设 与 为整数。若
则 存在一种边染色,其中没有单色 -团,故 。当 时该二项式系数为零。
对每个 ,这蕴含
该判据只是充分条件;该数值不等式不成立,并不能证明每一种染色都含有被禁止的团。
定理 10.5.5
(重复限制同样证明多色保证)
对整数 与 ,令 。在
个顶点的完全图上,每一种 -染色都含有单色 -团。这是一个有限上界,并不声称它是最优的。当 时,上式之和为 。
概念视角组合
普遍性限制与有限平均回答的是相反的量词
邻域归纳处理任意染色,并迫使见证出现:它证明的是“对每一种染色都存在团”这类陈述。有限平均则遍历所有染色,证明其中至少有一种没有见证:“存在一种没有团的染色”。即使涉及同一个有限图,上界、下界与精确阈值所需要的证据也各不相同。
下面的证明正按这一分工进行:第一和第三个定理用限制证明,第二个定理用平均证明。
证明思路或证明
一个顶点把较小的阈值变成较大的阈值
归纳对 进行,并用一个中心顶点把两个较小的阈值推到较大的阈值。
证明
(邻域递推与二项式界的证明)
对 作归纳来证明有限性,起点是其中一个参数为 的情形。假设较小的阈值 与 已经存在。考虑 的任意染色,并选定一个顶点 。
若 至少有 个红邻点,则限制到其中 个。归纳性质给出:要么有大小为 的红色团,加入 之后成为红色 -团;要么有蓝色 -团,这已经回答了原问题。
否则 至多有 个红邻点。由于它的 条关联边按颜色分成两类,所以它至少有 个蓝邻点。这些蓝邻点诱导的完全图含有红色 -团,或大小为 的蓝色团;在后一种情形下加入 即可。因此 的每一种染色都含有所需的团。可行的正整数阶数构成的集合非空,故其最小元 存在且不超过 ,递推式得证。
对于显式界,使用同样的归纳,边界值为 。由 Pascal 恒等式
与 的归纳上界相加正好得到所示的系数。在对角线上, 是 中的一项,由此得到较粗的指数上界。
证明透视
中心顶点用在哪里
证明只用到归纳假设: 个顶点上的每一种染色都含红色 -团或蓝色 -团, 个顶点上的每一种染色都含红色 -团或蓝色 -团。唯一不显然的一步,是对 的 条边作抽屉计数:红邻点不足 个,蓝邻点就至少有 个。论证之所以能收尾,是因为 以相应颜色连到所保留集合的每个顶点,加入 使该颜色的较小团增大一个顶点,而另一种颜色的团本来就已达到所需大小。
这个计数是刚好够用的。在 个顶点上,中心只有 个邻点,可以恰好分成 个红邻点与 个蓝邻点,此时两个保留集合都不够大,无法使用归纳假设。这就是递推式要把两个较小阈值本身相加的原因。计算出的上界不一定能取到:递推完全舍弃了两个邻域之间如何连接的信息。
计数坏团,而不是假设它们的事件相互独立
下界来自对所有染色取平均:平均值小于一,就迫使某种染色的取值为零。
证明
(第一矩下界的证明)
把 的每条边独立地以各 的概率染成红色或蓝色。这是一个有限的均匀概率空间:全部 种染色权重相同。固定的 -子集恰好张成 条边。这些边全为红色的概率是 ;全为蓝色的概率相同。对 ,这两个事件互不相交,所以该 -子集单色的概率是 。
令 为单色 -子集的个数。把 写成 个示性随机变量之和,由有限期望的线性性得
这一计算不要求不同 -子集的事件相互独立;相互重叠的团通常共享边。若每种染色都至少含有一个坏团,则 恒不小于一,其平均值也不小于一。因此平均值严格小于一就蕴含存在 的染色。严格性很重要:平均值等于一本身并不能迫使出现零结果。
为得到指数下界,取 ,于是 。由于 -子集的个数至多等于有序 -元组的个数除以 ,
对 ,最后一个量是 ,因为 。 增加一时,其分子乘以 ,分母乘以 ,所以它始终严格小于一。这就证明了对每个 所断言的界,包括 的情形(此时 )。该证明是在明确有限的染色之中确立存在性,不需要任何无限随机构造。
每次颜色限制之后都多保留一个顶点
多色证明重复中心顶点这一步,但不再对两个参数递推,而是记录颜色。
证明
(多色保证的证明)
对非负整数 ,记 。从 个顶点出发。选取中心 ,并按其余顶点与 相连的边的颜色把它们分类。由于 , 个颜色类中必有一个至少含 个顶点。保留这样一个类,并把它的颜色记在该中心旁边。
重复此过程,直到选出 个中心 并剩下最后一个顶点 ;这是可以做到的,因为所保留的集合依次至少有 个顶点。因为所保留的集合是嵌套的,每个被选中的中心与所有后来被选中的顶点之间的边,都具有它所记录的颜色。由抽屉原理,在所记录的 个颜色中,至少有 个相同。取这 个中心和最后的顶点 。两个所选中心之间的任何边都具有较早那个中心所记录的颜色;中心到 的边也是这一颜色。因此这 个顶点之间的所有边同色。
这个嵌套集合不变量比单纯选出许多标记相同的顶点更强。标记控制的是通向所有后来保留顶点的实际的边。这也解释了为什么我们保留最后一个顶点而不给它标记:它与 个同色的中心共同构成一个团。
例题详解
例题 10.5.6
(三角形阈值恰为六)
在 的任意红/蓝染色中,选定的顶点有五个邻点,所以在某一种颜色中至少有三个邻点,不妨设为红色。若这三个邻点之间有任一条边为红色,它与中心构成红色三角形。否则这三个邻点之间的三条边都是蓝色,构成蓝色三角形。蓝邻点的情形对称,故 。
对于反向不等式,把五圈的边染成红色,其余的边全染成蓝色。红色图是一个圈,不含三角形。用模 的剩余类标记顶点,蓝色边连接差为 的顶点,构成圈 ,同样不含三角形。这一种避开染色证明 。两个论证合起来给出 。
例题 10.5.7
(把精确的小值代入递推式)
若一种染色没有红边,则其所有边都是蓝色。因此 : 个顶点就足够,而 个顶点上的全蓝染色同时避开两个所要求的团。在递推式中使用精确的三角形阈值,得
再次应用得 。这些是已证明的普遍性上界。这里没有给出与之匹配的避开构造,所以这两个不等式都不能被提升为精确值。所得结果与二项式公式 、 相同,因为代入的 与 恰好等于各自的二项式界;只有代入小于二项式系数的精确值时,递推式才会胜过公式。由对称性,参数互换后得到相应的界。
例题 10.5.8
(期望检验证明存在性,并有明显的局限)
对 与 ,单色五团的期望个数为
因此存在某种十个顶点的染色,同时避开两种颜色的五团,从而证明 。该证明不需要指出这是哪一种染色。
边界情形 、 时,同一期望等于 ,所以这一检验没有给出避开染色。然而上面的五圈构造确实同时避开了两种三角形。因此,充分的第一矩检验失败,与所期望的构造不存在,是两回事。
常见错误
反例模式
稠密的颜色不一定含有指定的团
待检验的说法:若某一种颜色得到 至少一半的边,则该颜色含有三角形。取 ,把一个五圈染成红色。红色有 条边中的 条,恰为一半,每个顶点的红度数为 ;红色三角形需要三个在圈上两两相邻的顶点,而五圈中没有这样的三个顶点。蓝色补图是圈 ,有同样的密度和同样的障碍。该说法不成立。边密度只有超过某个需要另行证明的极值阈值后才迫使三角形出现;它不能代替 Ramsey 论证,后者用的是颜色类在一个顶点处如何相遇。
常见错误
(把重叠团的概率直接相乘)
人们容易把“没有单色 -团”的概率估计为 ,仿佛不同 -子集的事件相互独立。一般而言它们并不独立。对 ,两个共用三个顶点的 -子集共用三条边;各自单色的概率是 ,但两者同时单色的概率是 ,而非 。第一矩论证只需要边的颜色相互独立以及期望的线性性。
常见错误
(把边染色与正常顶点染色混为一谈)
Ramsey 染色给边上色,对共用顶点的边没有任何限制。正常顶点染色给顶点上色,并禁止一条边的两端同色。关于色数的结论不能直接说明边染色中的单色团。
常见错误
(把界当作值,或把方向写反)
个顶点上的避开染色证明 ,永远不证明 。反过来,递推式与多色求和给出的上界不一定能取到: 并不是说 。精确值需要一个普遍性论证与一个避开染色恰好相接,就像 那样。
总结
邻域限制证明了有限的二色阈值和显式的二项式界;嵌套限制给出多色保证。精确的五圈障碍确定了三角形阈值。有限期望证明其他障碍的存在,同时明确保留严格不等式以及充分检验的局限。这些论证在本章内仍未解决大多数精确阈值和高效搜索的问题。
练习
快速检查
(证明对每个正整数 都有 ,并明确处理 的情形。)
把单点约定与没有红边这两种情形区分开来。
解答
对 ,边界约定给出 。对 , 个顶点上的任意染色要么有一条红边(这已经是红色二团),要么所有边都是蓝色,从而有蓝色 -团。这证明了上界 。
把 个顶点上的每条边都染成蓝色。没有红边,且顶点数不足以构成蓝色 -团。因此阈值大于 ,等式得证。该论证在 时同样成立:单个顶点同时避开两个二团。
快速检查
(计算多色定理对三种颜色与三角形给出的界。准确说明哪些被选中的顶点构成团。)
取 ,并保留最后一个未标记的顶点。
解答
取 、,则 ,保证的阶数为 。限制过程选出六个中心,随后是最后一个顶点。六个记录的颜色只来自三种,所以至少有两个中心所记录的颜色相同。它们之间的边由较早那个的标记决定,具有该颜色,并且它们到最后顶点的两条边也具有该颜色。这两个中心与最后的顶点构成所需的三角形。
这一数值保证有意取得较粗。该证明没有给出接近 的下界构造,也不声称这就是三色三角形的实际阈值。
快速检查
(对 证明更强的下界估计 。说明为什么它仍然只是存在性的界。)
在应用第一矩检验之前,先把对数之和与从 到 的积分作比较。
解答
因为对数函数递增,对 有 ,所以
特别地,。取 ;当 时它为正,并且 。第一矩估计给出
因此存在避开染色,其阶数证明了所需的严格下界。我们是在所有有限边染色上取平均;仅凭这一计算,并不能得到寻找成功染色的高效方法、最优阈值,或对无界 的高效避开证书。