MathLabs

解法:卡恩与卡莱利用弗兰克尔–威尔逊定理反驳博苏克猜想

第 4/7 步:卡恩与卡莱的构造:把完全图的割看作 Rd\mathbb{R}^d 中的点
通俗地说

取 mm 个带标号的点,画出它们之间所有可能的边(一个完全图);每一种把这些点分成相等两半的方式都定义了一个"割"——即在两半之间穿越的边的集合。卡恩与卡莱把每个割看作一个由所有边编号的 (0,1)(0,1) 向量,生活在一个维数 dd(等于边的总数)的空间中,并用所有这样的割构成的整个族,作为博苏克猜想的检验案例。

V={1,…,m}, m=4k;W={pairs of V};K={S(A,B):{A,B} partitions V, ∣A∣=2k}V=\{1,\ldots,m\},\ m=4k;\quad W = \{\text{pairs of } V\};\quad \mathcal K = \{S(A,B) : \{A,B\} \text{ partitions } V,\ |A|=2k\}
详细分析

设 V={1,…,m}V = \{1, \ldots, m\},其中 m=4km = 4k、kk 为素数幂,设 WW 为 VV 中所有 (m2)\binom{m}{2} 个无序元素对——即 VV 上完全图的边——所以 d:=∣W∣=(m2)d := |W| = \binom{m}{2} 就是所处空间的维数。对 VV 的每一个划分为两个各含 2k2k 个元素的等份 {A,B}\{A,B\},设 S(A,B)⊂WS(A,B) \subset W 为一端在 AA、另一端在 BB 的边构成的集合(即 AA 与 BB 之间的"割");注意对任何这样的划分都有 ∣S(A,B)∣=(2k)2=m2/4|S(A,B)| = (2k)^2 = m^2/4。设 K={S(A,B):{A,B}\mathcal K = \{S(A,B) : \{A,B\} 是 V}V\} 的一个均衡划分,这是 WW 的一族子集,共 (m2k)/2\binom{m}{2k}/2 个,每个都被等同于 Rd\mathbb{R}^d 中的一个 (0,1)(0,1) 向量。

由于 K\mathcal K 中每个集合的大小都恰好为 m2/4m^2/4,K\mathcal K 的所有点都位于 Rd\mathbb{R}^d 中以全 12\tfrac12 点为中心的同一个球面上,并且根据第2步的距离公式,它们两两之间的距离完全由 ∣S(A,B)∩S(C,D)∣|S(A,B) \cap S(C,D)| 决定:两个割彼此靠近,恰好对应它们的跨界边集合有很大重叠。最小的重叠——从而是达到 K\mathcal K 直径的最大距离——经过对 A,B,C,DA, B, C, D 的容斥原理直接计算可知,恰好发生在 ∣A∩C∣=k|A \cap C| = k 时,这正设定了第3步的定理所要控制的交集条件。

本步骤中的术语
图的割
给定一个图的顶点被划分为两部分 A,BA, B,割 S(A,B)S(A,B) 是一个端点在 AA、另一个端点在 BB 的边构成的集合;割的大小计算的是有多少条边在两侧之间"跨越"。
本步骤用到的知识