第五部　从无穷到有限

第十九章为什么一定比二小

清单变成有限的以后，还能推出：每一张固定的图，耦合常数都严格小于 $2$ 。

一个已有的结果

我们先借用前人的一个结果。有一种对所有分布同时适用的抽签方法：任意两张距离为 $d$ 的表，用它抽出来的回答不同的机会，都不超过 $\frac{2 d}{1 + d}$ 这种方法是怎样做到的，第二十三章会讲。现在只看它给出的倍数： $\frac{2 d}{1 + d} \div d = \frac{2}{1 + d}$ 。只要 $d$ 大于零，这个数就小于 $2$ 。

可是它不能直接说明“每张图都小于 $2$ ”。因为 $d$ 可以非常非常小，这时 $\frac{2}{1 + d}$ 会无限接近 $2$ 。一般的输入里，两张表可以要多近有多近。

角上的距离不会太小

有限极值归约解决了这个问题：我们不必担心一般的输入，只需要看清单上的角。

角上的权重是一个方程组的解。看那个“三对子”的角：三个对子的权重记作 $x$ 、 $y$ 、 $z$ ，三个顶点各给出一个方程： $x + y = 1, x + z = 1, y + z = 1$ 三式相加得 $2 (x + y + z) = 3$ ，所以 $x + y + z = \frac{3}{2}$ ，再减去每一个方程，得到 $x = y = z = \frac{1}{2}$ 。解出来是分数，分母是 $2$ 。

一般也是这样。方程的系数都是 $0$ 或 $1$ ，用消元法一步步解下去，解出来的权重都是分数，而且有一个公共的分母。这个分母是由系数算出来的一个整数，数学上叫方程组的行列式；它可能带负号，我们只看它的大小，记作 $g$ 。也就是说，角上的每个权重都是 $\frac{1}{g}$ 的整数倍。

两个顶点之间的距离，是一些权重直接相加，所以它也是 $\frac{1}{g}$ 的整数倍：如果不是零，至少就是 $\frac{1}{g}$ 。

距离不能太小，倍数就不能太接近 $2$ 。距离 $d$ 至少是 $\frac{1}{g}$ ，所以 $\frac{2}{1 + d} \leq \frac{2}{1 + \frac{1}{g}} = \frac{2 g}{g + 1} < 2$

顶点数 $n$ 固定时，这样的方程组只有有限多种， $g$ 也就有一个最大可能值，记作 $Δ_{n}$ （ $Δ$ 是希腊字母，读作“德尔塔”）。于是每一张 $n$ 个顶点的图都满足 $c (G) \leq \frac{2 Δ _{n}}{Δ _{n} + 1} < 2$ 最后，再用前面“切层”和“混合”的两步，把这个保证从角推广到所有输入。

放回周末的小世界，不管有几条记录、要照顾哪些删除，只要情况的数目是固定的，最坏也到不了多付一倍。

小图上的精确值

$Δ_{n}$ 到底有多大？两个未知数时，上面方框里的 $a_{1}, b_{1}, a_{2}, b_{2}$ 都是 $0$ 或 $1$ ，分母 $a_{1} b_{2} - b_{1} a_{2}$ 只能是 $- 1$ 、 $0$ 或 $1$ ，所以 $Δ_{2} = 1$ 。论文用一个关于行列式的经典不等式证明了：三个未知数时，分母不超过 $2$ ；四个未知数时，不超过 $3$ （附录三）。“三对子”的分母 $2$ ，正好碰到三个未知数时的上限。四个未知数时的上限 $3$ ，也有一个角碰得到，就是韵吉改写过的那道难题。

停下来算一算

第十五章里，韵吉把第八章那道难题改写成了四个三人组。把它们的权重记作： ${2, 3, 4}$ 为 $x$ ， ${1, 3, 4}$ 为 $y$ ， ${1, 2, 4}$ 为 $z$ ， ${1, 2, 3}$ 为 $w$ 。

每个顶点给出一个方程：包含它的三人组，权重加起来等于 $1$ 。写出四个方程，照“三对子”的办法解出 $x$ 、 $y$ 、 $z$ 、 $w$ 。分母是多少？
两个顶点之间的距离是多少？代进 $\frac{2}{1 + d}$ ，得多少？

答案见附录二。

展开本章“停下来算一算”的答案

四个顶点各给一个方程：

$y + z + w = 1, x + z + w = 1, x + y + w = 1, x + y + z = 1.$

四式相加得 $3 (x + y + z + w) = 4$ ，所以 $x + y + z + w = \frac{4}{3}$ ，再减去每一个方程，得到 $x = y = z = w = \frac{1}{3}$ 。分母是 $3$ 。
任意两个顶点之间，含一个、不含另一个的三人组只有一组，距离是 $\frac{1}{3}$ 。 $\frac{2}{1 + \frac{1}{3}} = \frac{3}{2}$ 。

代进去，两个、三个、四个顶点的图，倍数分别不超过 $\frac{2 \times 1}{1 + 1} = 1, \frac{2 \times 2}{2 + 1} = \frac{4}{3}, \frac{2 \times 3}{3 + 1} = \frac{3}{2}$

图 35：前人那种抽签方法的倍数 2/1+d：d 越小越接近 2。角上的距离至少是 1/g，三个点分别对应两个、三个、四个顶点的图。 — 图 35前人那种抽签方法的倍数 $\frac{2}{1 + d}$ ： $d$ 越小越接近 $2$ 。角上的距离至少是 $\frac{1}{g}$ ，三个点分别对应两个、三个、四个顶点的图。

现在可以回答祺乐在这一部开头的问题了。 $K_{4}$ 里含有正方形，所以至少是 $\frac{3}{2}$ ；四个顶点的图又都不超过 $\frac{3}{2}$ 。所以 $c (K_{4}) = \frac{3}{2}$

在正方形上加两条对角线，要求确实变多了，最坏的倍数却没有再增加。对角线可能会影响某些表的倍数，只是整张图最坏的那个数恰好没变。

由此，所有不超过四个顶点的图都有了准确的答案：

没有圈（森林）： $1$ ；
最长的圈是三角形： $\frac{4}{3}$ ；
有一个四个顶点的圈： $\frac{3}{2}$ 。

这个 $\frac{3}{2}$ 是理论这条路推出来的，一路靠的是切层、角、混合和行列式的上限。祺乐问这个问题的时候，瀚林那边走的是另一条路：把四个顶点的角一个一个列出来，放到 $K_{4}$ 上，让电脑逐个算最好的倍数，每个结果还要留下能检查的凭据。那条路上一共有多少个角，算出来的最大值是多少，第六部再讲。

更大的图

顶点更多时， $\frac{2 Δ _{n}}{Δ _{n} + 1}$ 这个上界不一定准确，它只保证“一定小于 $2$ ”。随着 $n$ 变大，这个上界会越来越接近 $2$ 。

另一方面，把逐一缺失的表放到 $n$ 个顶点的完全图上，每张签上至少有 $n - 1$ 对顶点回答不同（最少的情况是一个顶点和其余的都不同），用第八章同样的办法可以算出 $c (K_{n}) \geq 2 - \frac{2}{n}$ 。我们证明了 $n \leq 4$ 时等号成立；五个顶点以上的完全图，准确的值还不知道。

图 36：记分牌：这一部填上了 K_4，它也是 3/2，和正方形一样；每一张固定的图，耦合常数都严格小于 2。 — 图 36记分牌：这一部填上了 $K_{4}$ ，它也是 $\frac{3}{2}$ ，和正方形一样；每一张固定的图，耦合常数都严格小于 $2$ 。