解法:卡恩与卡莱利用弗兰克尔–威尔逊定理反驳博苏克猜想
通俗地说
取 个带标号的点,画出它们之间所有可能的边(一个完全图);每一种把这些点分成相等两半的方式都定义了一个"割"——即在两半之间穿越的边的集合。卡恩与卡莱把每个割看作一个由所有边编号的 向量,生活在一个维数 (等于边的总数)的空间中,并用所有这样的割构成的整个族,作为博苏克猜想的检验案例。
详细分析
设 ,其中 、 为素数幂,设 为 中所有 个无序元素对——即 上完全图的边——所以 就是所处空间的维数。对 的每一个划分为两个各含 个元素的等份 ,设 为一端在 、另一端在 的边构成的集合(即 与 之间的"割");注意对任何这样的划分都有 。设 是 的一个均衡划分,这是 的一族子集,共 个,每个都被等同于 中的一个 向量。
由于 中每个集合的大小都恰好为 , 的所有点都位于 中以全 点为中心的同一个球面上,并且根据第2步的距离公式,它们两两之间的距离完全由 决定:两个割彼此靠近,恰好对应它们的跨界边集合有很大重叠。最小的重叠——从而是达到 直径的最大距离——经过对 的容斥原理直接计算可知,恰好发生在 时,这正设定了第3步的定理所要控制的交集条件。
- 图的割
- 给定一个图的顶点被划分为两部分 ,割 是一个端点在 、另一个端点在 的边构成的集合;割的大小计算的是有多少条边在两侧之间"跨越"。