第七部　更多的记录，更少的信息

第二十二章记录再多一些：立方体

还是那个周六。助手原来记着两条：“周六要去看电影”和“不喜欢太吵的地方”，现在又多了第三条，记作 C：“脚扭了，这几周别走远路。”有这一条在，助手就很少推荐要走一大圈的公园。过了几周，脚好了，这一条也该删了。它当初没有记错，脚好了以后才过时。

三条记录都能删，先删哪条随你。每条都可以“在”或“不在”，保留情况一共 $2 \times 2 \times 2 = 8$ 种：

还剩几条	保留情况
三条都在	${A, B, C}$
删了一条	${A, B}$ 、 ${A, C}$ 、 ${B, C}$
只剩一条	${A}$ 、 ${B}$ 、 ${C}$
三条都删	$\emptyset$

祺乐把第七章的正方形又画了一个，往右上方挪开一点，再把两个正方形对应的顶点一一连起来。“前面这个是没有 C 的四种，就是原来那个正方形；后面这个是有 C 的四种。”

八个顶点，十二条棱，是一个立方体。每条棱连着只差一条记录的两种情况，沿着它走一步，就是删掉（或加回）一条记录。第七章末尾问过：三条记录、随便先删哪条，最坏要多付几倍？说的就是这个立方体。

图 39：三条记录的八种保留情况构成一个立方体 Q_3。A 是电影约定，B 是怕吵，C 是脚扭了；每条棱代表删掉（或加回）一条记录。 — 图 39三条记录的八种保留情况构成一个立方体 $Q_{3}$ 。A 是电影约定，B 是怕吵，C 是脚扭了；每条棱代表删掉（或加回）一条记录。

去掉记录的名字，只留下“在”和“不在”： $d$ 条记录时有 $2^{d}$ 种情况，把只相差一条记录的两种情况连起来，这样的图叫 $d$ 维超立方体，记作 $Q_{d}$ 。正方形就是 $Q_{2}$ ，立方体是 $Q_{3}$ 。

这里有两个数要分清： $d$ 是可以删的记录条数， $2^{d}$ 是顶点的个数，也就是分布的个数。第五部说“最多用 $n$ 种回答”时， $n$ 指的是顶点个数，用到这里， $n$ 就是 $2^{d}$ 。

超立方体还有一个特点：沿着任何一条边走一步，保留的记录数就会加一或减一，奇偶性改变一次。绕一圈回到起点，奇偶性必须变回来，所以走的步数一定是偶数。超立方体里没有奇数长的圈，三角形、五边形都不会出现。三角形和完全图是我们为了看清一般规律才研究的，它们本身并不是删记录的图。

要剪断几条边，图才会断开

祺乐给超立方体找下界时，拿铅笔在立方体上画剪线，画一道，数一数剪断了几条棱。一张连通的图，最少要剪断几条边，才能让它断成两块？这个数叫图的边连通度，记作 $κ$ ，希腊字母，读作“卡帕”。

下界还是要靠逐一缺失：每种情况各有一种回答不许出现，其余的平分。立方体有八种情况，就要八种回答，四个去处不够用了。出题人干脆不管去处，把回答编成 $1$ 到 $8$ ，第 $i$ 种情况不许出现第 $i$ 种回答。这样的签盒和三条记录的意思已经对不上，它只是出题人故意出的难题。

把这个办法放到任意一张有 $N$ 个顶点、 $M$ 条边的连通图上：回答有 $N$ 种，第 $i$ 个顶点不许出现第 $i$ 种回答，其余平分。相邻两张表的距离都是 $\frac{1}{N - 1}$ 。

每张签上，所有顶点的回答都不会完全相同。挑一种在这张签上出现了、但又不是所有顶点都用的回答，把用这种回答的顶点放一边，其余的放另一边。连接两边的那些边，两端的回答一定不同。而把图分成两块，至少要剪断 $κ$ 条边，所以每张签上至少有 $κ$ 条边两端不同。

和第八章一样平均一下：各条边不同的机会加起来至少是 $κ$ ， $M$ 条边里最大的那个至少是 $\frac{κ}{M}$ 。除以距离 $\frac{1}{N - 1}$ ，倍数至少是 $\frac{κ ( N - 1 )}{M}$

这个论证不要求图是一个圈。圈的情形里， $κ = 2$ ， $M = N$ ，正好得到 $2 - \frac{2}{N}$ ，和第十二章一致。

立方体的四分之七

超立方体 $Q_{d}$ 有 $N = 2^{d}$ 个顶点。每个顶点连着 $d$ 个邻居，所以一共有 $\frac{d N}{2}$ 条边。它的边连通度是 $d$ ：把一个顶点单独切下来，正好要剪断 $d$ 条边；用更少的边，没法把它剪断（附录三有证明）。立方体上，从“三条都在”出发只有三种删除，把这个顶点单独切下来，剪断的就是这三条棱。

代进去： $c (Q_{d}) \geq \frac{d ( N - 1 )}{d N /2} = 2 - \frac{2}{N} = 2 - \frac{2}{2 ^{d}}$ 另一边，第十九章已经说明它一定小于 $2$ 。所以 $2 - \frac{2}{2 ^{d}} \leq c (Q_{d}) < 2$

两条记录时，左边是 $\frac{3}{2}$ ，正方形正好就是这个数。三条记录时，左边是 $2 - \frac{2}{8} = \frac{7}{4}$ ，也就是一点七五。立方体的耦合常数至少是四分之七，又小于 $2$ ，到底是多少，论文没有算出来。

图 40：立方体 Q_3：把“三条都在”这个顶点单独切下来，正好剪断 3 条边（红色）；代入下界公式得到 7/4。 — 图 40立方体 $Q_{3}$ ：把“三条都在”这个顶点单独切下来，正好剪断 $3$ 条边（红色）；代入下界公式得到 $\frac{7}{4}$ 。

韵吉问：“让电脑算呢？”

瀚林说：“八个顶点。五个顶点的完全图都超时了。”

第二十一章的办法要先把角全部列出来，四个顶点已经有 $42$ 个角，五个顶点就没算完，八个顶点更不用说。

再看那个 $\frac{7}{4}$ 。在出题人出的那组逐一缺失的签盒上，不管答案单怎样写，总有一种删除，换地方的机会至少是它单独最好时的 $\frac{7}{4}$ 倍，也就是 $175%$ ，多付了四分之三。

对逐一缺失这组特定的表，第八章“挑一个特殊顶点”的抽法仍然管用。不管图里有哪些边，每条边两端不同的机会都是 $\frac{2}{N}$ ，倍数正好是 $2 - \frac{2}{N}$ ，和下界一致。可是一组输入达到下界，只能说明常数至少这么大；要说它恰好是这个数，还得对所有输入证明同样的上界。对 $Q_{3}$ ，这一步还没有完成。

记录越多，越接近二

记录越多，下界 $2 - \frac{2}{2 ^{d}}$ 越接近 $2$ 。一条一条按顺序删的单链，图是一条路，倍数是 $1$ 。如果允许按任意顺序删，完整删除图里有大量互相交叠的圈，最坏的倍数会越来越接近 $2$ 。

在周末的小世界里，助手记着三条记录、随你按什么顺序删时，最坏的情况下，总有一步删除要多付至少四分之三，又一定不到一倍。准确的数我们还不知道。论文把它留成了一个具体的问题：能不能利用超立方体特殊的对称性，把它算出来。