6.2 排列的组合学
(Combinatorics of Arrangements)

定理 6.2.1. 在由 \(n\) 条直线构成的简单排列中，顶点、边和面的数量分别为 \(V = \binom{n}{2}\)，\(E = n^2\)，以及 \(F = \binom{n}{2} + n + 1\)，并且没有任何非简单排列的数量会超过这些值。

证明: 顶点数为 \(\binom{n}{2}\) 可以直接通过简单排列的定义得到。在简单排列中，每对直线恰好产生一个顶点。关于 \(E\) 的公式可以通过数学归纳法来证明。 假设任意 \(n-1\) 条直线构成的简单排列 \(\mathcal{A}\) 都有 \((n-1)^2\) 条边。在 \(\mathcal{A}\) 中插入一条新直线 \(L\)。 它将 \(\mathcal{A}\) 中 \(n-1\) 条直线都分成两段，并且 \(L\) 本身被 \(\mathcal{A}\) 分割成 \(n\) 条新边。因此 \(E = (n-1)^2 + (n-1) + n\)，简化后就是 \(n^2\)。

面的数量 \(F\) 可以通过欧拉公式(定理 4.1.1) \(V - E + F = 2\) 推导出 。 但是我们不能直接应用此公式，因为它计算的是平面图(plane graphs)，而在一般意义下，排列 \(\mathcal{A}\) 并不是一个平面图。我们至少有两种处理方法， 通过将所有直线连接到一个新顶点将 \(\mathcal{A}\) 转换为图，或者重新审视欧拉定理的证明。在这里我们选择后者。 回想一下，我们是通过在多面体的一个面上刺破一个内点并将其展平到平面上来证明欧拉定理的。如果我们刺破顶点 \(v\) ，将失去一个顶点，公式变为 \(V - E + F = 1\)， 并且展平过程会拉伸所有与 \(v\) 关联的边使其延伸至无穷远。这种展平可以通过立体投影实现。比如，以 \(v\) 为包围球体的北极，骨架上的任何其他点 \(p\) 都将被映射到通过 \(v\) 和 \(p\) 的直线与支撑南极的平面相交的位置上。得到的就是一个在拓扑上等价于直线排列的无界对象。因此 \(V - E + F = 1\) 对排列成立。 再代入 \(V\) 和 \(E\) 的值，得到 \(F = 1 + n^2 - n(n-1)/2 = (n^2 + n + 2)/2\)，这正是定理给出的公式。

最后，我们非形式化地论证简单排列是这些组合量的最坏情况。如果 \(k > 2\) 条直线交于一个顶点，我们可以像图6.2(a) 所示那样，稍微"扰动"这些直线来打破重合点。 这会导致 \(V\)、\(E\) 和 \(F\) 的值增大，从图中(a) 的阴影区域就可以明显看出。如果两条直线平行，我们还是通过扰动来打破它。如图 6.2(b) 所示，这将使得 \(V\) 增加 1， \(E\) 增加 2，\(F\) 增加 1。打破退化情况只会增加排列的组合复杂度，因此非简单排列不可能是一个最坏情况。

虽然尚未得到证实，但根据直觉，所有排列中的退化项都可以同时被打破。正式地证明这一点会让我们偏离主题太远。□

定理 6.2.2. 在由 \(n\) 条直线构成的线排列中，与其中一条直线相交的所有面内的边总数为 \(O(n)\)，特别的 \(z_n \le 6n\)。

证明: 为了简化表述，我们需要做出三个假设: ① 包含新直线的排列是简单的 ② 我们要寻找关于直线 \(h\) 的区域该直线是水平的 ③ 不存在竖直的直线。 我不会花时间来论证这些假设，因为在不处理这些特殊情况的前提下，证明过程就已经很困难了。有一个充分条件，最坏情况是简单排列的，因此为了获得上界，假设这一点不失一般性。

由于没有竖直的直线，我们就可以将 \(Z(h)\) 中每个面的边划分为左边和右边。如果一个点是面 \(C\) 左边上的点，那么其右侧紧邻的点就是 \(C\) 内部的点。因此左边上的点构成了 \(C\) 的左边界。 右边是指那些不是左边的边。根据我们的简单性假设，没有直线与 \(h\) 平行。因此有界面 \(C\) 的最高点和最低点是唯一的，它们为左边和右边提供了清晰的分隔点。 在图 6.3 中，区域面的左边用虚线高亮表示。

由于左边和右边的作用是对称的。所以我们只需证明对 \(z_n\) 有贡献的左边数量 \(l_n \le 3n\) 即可。在图 6.3 中，有 9 条左边，且 \(n = 5\)。

我们采用数学归纳法来证明。归纳基础是显而易见的 \(l_0 \le 0\)，即，空的线排列没有左边。假设 \(l_{n-1} \le 3n - 3\) 成立。令 \(\mathcal{A}\) 是一个满足我们假设的 \(n\) 条直线的排列。 我们从 \(\mathcal{A}\) 中移除一条直线，应用归纳假设，然后再把它放回去。我们选择移除的那条直线是与 \(h\) 的交点最靠右的那条，称之为 \(r\)。如图 6.3 中的 \(L_5\)。 根据简单性假设，没有两条直线是平行的，因此每条直线都与 \(h\) 相交。令 \(\mathcal{A}'\) 为排列 \(\mathcal{A} \setminus \{r\}\)，即，从 \(\mathcal{A}\) 中移除 \(r\) 后的排列。 它有 \(n - 1\) 条直线，因此归纳假设成立。现在我们的目标是证明将 \(r\) 插回 \(\mathcal{A}'\) 最多只能使 \(l_{n-1}\) 增加 3。 证明的剩余部分将通过如下条件来确立这点: 插入 \(r\) 引入了一条新的左边，并且最多将两条旧的左边分为二段。 所谓的"旧"是指重新插入 \(r\) 之前的 \(\mathcal{A}'\)，"新"指的是插入 \(r\) 之后的 \(\mathcal{A}\)。

图 6.4 展示了与图 6.3 中 \(\mathcal{A}\) 相对应的 \(\mathcal{A}'\)。我们用上撇字母标记所有面，显而易见的对应面使用相同的字母。 \(r = L_5\) 的插入将 \(\mathcal{A}'\) 中的面 \(G'\) 分割成 \(\mathcal{A}\) 中的面 \(F, E\)，它裁剪了面 \(A', B', C', D'\) 形成 \(A, B, C, D\)。 插入的效果很复杂。例如，\(B\) 和 \(B'\) 的左边数相同，\(C\) 比 \(C'\) 少一条左边，而 \(F\) 比 \(G'\) 多一条左边。 幸运的是我们有两个条件，让情况比初看起来更简单。(a) 我们只需要增长量的一个上界，而不是精确计算 (b) 左边的变化比对右边的变化更简单。 后面我们将看到的，条件(b)源于我们选择最右侧的直线来获得左边的界限。

\(r\) 是 \(\mathcal{A}\) 中与 \(h\) 有最右侧交点的直线，将该交点记为 \(x = r \cap h\)。\(x\) 必须位于 \(\mathcal{A}'\) 中被 \(h\) 穿过的最右侧面内，如图 6.4 中的 \(G'\) 所示。 最右侧的直线 \(r\) 将从左侧界定 \(\mathcal{A}\) 的最右侧面，如图 6.3 中的 \(F\) 所示。因为 \(r\) 包含 \(x\)，且从 \(x\) 向右的射线必须位于最右侧面内。 所以，\(r\) 将包含至少一条新的左边。此外，\(r\) 在 \(\mathcal{A}\) 中不包含任何其他左边，如图 6.3 所示，\(r\) 确实包含几条新的右边。 因为 \(\mathcal{A}\) 中任何包含多于一条左边的直线 \(\alpha\)，例如图 6.3 中的 \(L_3\) 必然被一条直线 \(\beta\)，例如 \(L_4\) 切割， \(\beta\) 将 \(\alpha\) 右侧支撑的面分隔开。因此，\(\beta\) 将会在 \(\alpha\) 的右侧与 \(h\) 相交。因此，\(\alpha\) 不可能具有与 \(h\) 的最右侧交点。这就是我们选择 \(r\) 的原因。

既然 \(r\) 恰好包含一条新的左边，我们只需要界定被 \(r\) 分割两段的旧左边的数量。例如，图 6.4 中 \(G'\) 的左边就被 \(h\) 穿过(包含在 \(L_4\) 中)。 它被图 6.3 中的 \(r = L_5\) 分割成 \(E\) 的一条左边和 \(F\) 的一条左边缘。这种分割只能发生在 \(\mathcal{A}'\) 中 \(h\) 上的最右侧面内，因为对于与 \(r\) 相交的所有其他面， \(r\) 只是对其进行"裁剪(clips)"而不是"分割(split)"。因为，如果 \(r\) 分割了一条左边，那么由这些左边支撑的右侧两个面必须在 \(h\) 上跨越 \(r\)， 这意味着其中一个是在最右侧，因为 \(r\) 具有与 \(h\) 的最右侧交点。进而，这意味着被分割的旧边必须是最右侧面的一部分。

因此，\(r\) 只能分割最右侧区域面的边。因为这个面是凸的，所以 \(r\) 最多只能穿过它两次，如图 6.3，\(r\) 仅与 \(G' = E \cup F\) 的边界相交一次。因此，\(r\) 最多只能分割两条旧的左边。

综上所述，\(r\) 增加一条新的左边，并且最多分割两条旧的左边，使得 \(l_{n-1}\) 最多增加 3，因此 \(l_n \le 3n\)。□