8.1　图的交叉数The crossing number of a graph

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 定义 / 定理 / 例 / 分步推演 / 注记）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

第 8 章引言：关联几何

关联几何（incidence geometry）研究的是点、线、球面等基本几何对象之间的关联关系（即“某个点是否落在某条线上”这类从属关系）。通过经典的组合技巧——把某种关联配置的数目用两种不同方式各数一遍（即双重计数，double counting）——人们可以得到关于这些关联的有用且非平凡的信息。在许多情形下，关联几何的工具配合一个巧妙的双重计数论证，能为困难问题提供一种简单却强大的处理方法。本章的目标就是展示若干这样的应用，其中包括加性组合学中的几个。

本章内容安排如下。我们先给出一个关于图的交叉数的结果，它带有拓扑学的味道。接着用这个结果给出著名的 Szemerédi–Trotter 点线关联定理的简洁证明。随后两节里，我们用该定理证明 Erdős–Szemerédi 和积问题的若干界，并重新证明 Andrew 关于凸多边形内格点数目的定理。再往后，我们引入胞腔分解（cell decomposition）方法，用它处理 \(\mathbb{R}^d\) 中的 Erdős 相异距离问题。最后，我们讨论复数情形下 Erdős–Szemerédi 和积问题的一个变体。

8.1　图的交叉数

在本章中，除非另有说明，点指的是平面 \(\mathbb{R}^2\) 中的一个点，线指的是 \(\mathbb{R}^2\) 中的一条直线。所谓曲线（curve），我们指的是把紧区间 \([0,1]\) 经由一个连续单射嵌入¹到 \(\mathbb{R}^2\) 中所得的像。

¹ 在应用中，人们处理的是非常具体的曲线，例如圆弧或直线段，因此若愿意，我们完全可以把曲线类限制为这类对象。这样一来，就不必援引拓扑学中那些困难的结果，比如 Jordan 曲线定理（它隐含在我们对 Euler 公式的运用之中）。

考虑一个图 \(G=G(V,E)\)；回忆我们约定图都是无向的，且没有自环（loop）或重复边（repeated edge）。\(G\) 的一个画法（drawing）是 \(G\) 在平面 \(\mathbb{R}^2\) 中的任意一种表示：把 \(V\) 中每个顶点对应到一个互不相同的点，把 \(E\) 中每条边 \((u,v)\) 对应到 \(\mathbb{R}^2\) 中一条连接 \(u\) 与 \(v\) 的曲线。这样一个画法的交叉数（crossing number），是指那些没有公共端点、而对应曲线却彼此相交的边对的数目。图 \(G\) 的交叉数，则是所有画法中交叉数的最小值。在这里以及之后，我们用 \(\operatorname{cross}(G)\) 记这一参数。

人们预期：如果 \(G\) 的边很多，那么它的交叉数就应当很大。下面这条定理印证了这一直觉，它由 Ajtai、Chvátal、Newborn 与 Szemerédi [1] 证明，并由 Leighton [224] 独立证明。

逐步拆解证明的每一步

1. 第一段：平面图边数的上界。 由 Euler 公式 \(|V|-|E|+|F|=2\)（\(F\) 是面数），每个面至少由 \(3\) 条边围成，而每条边至多被 \(2\) 个面共用，故 \(3|F|\le 2|E|\)，即 \(|F|\le \tfrac23|E|\)。代回 Euler 公式：\(2=|V|-|E|+|F|\le |V|-|E|+\tfrac23|E|=|V|-\tfrac13|E|\)，整理得 \(|E|\le 3|V|-6\le 3|V|\)。这就是“平面图至多 \(3|V|\) 条边”。
2. 第一段：每个交叉删一条边。 取 \(G\) 的最优画法，它恰有 \(\operatorname{cross}(G)\) 个交叉。每遇到一个交叉，就删掉参与该交叉的某一条边——最多删 \(\operatorname{cross}(G)\) 条，剩下的画法再无交叉，于是变成平面图。平面图边数 \(\le 3|V|\)，所以 \(|E|-\operatorname{cross}(G)\le 3|V|\)，即得 (8.1)。
3. 第二段：抽样建小图。 抛一枚“正面概率 \(p\)”的硬币给每个顶点，正面则保留。保留下来的顶点集 \(V'\)，连同两端都保留的边，构成诱导子图 \(G'\)。(8.1) 对任何图都成立，所以对随机的 \(G'\) 也成立：\(\operatorname{cross}(G')\ge |E'|-3|V'|\)。这是一个随机不等式，两边取期望仍成立。
4. 第二段：算三个期望。 顶点幸存概率 \(p\Rightarrow \mathbb{E}|V'|=p|V|\)；一条边幸存要两端都在，概率 \(p\cdot p=p^2\Rightarrow \mathbb{E}|E'|=p^2|E|\)；一个交叉牵涉 4 个顶点，全幸存概率 \(p^4\)，所以原画法在 \(G'\) 上留下的交叉数期望是 \(p^4\operatorname{cross}(G)\)。注意 \(\operatorname{cross}(G')\) 只会更小（它是最优画法的交叉数），故 \(\mathbb{E}\operatorname{cross}(G')\le p^4\operatorname{cross}(G)\)。
5. 第二段：串起来并选最优 \(p\)。 由 \(p^4\operatorname{cross}(G)\ge p^2|E|-3p|V|\)，得 \(\operatorname{cross}(G)\ge p^{-2}|E|-3p^{-3}|V|\)。代入 \(p=4|V|/|E|\) 验证：\(p^{-2}|E|=\dfrac{|E|^3}{16|V|^2}\)，\(3p^{-3}|V|=\dfrac{3|E|^3}{64|V|^2}\)，相减得 \(\dfrac{4|E|^3-3|E|^3}{64|V|^2}=\dfrac{|E|^3}{64|V|^2}\)。♦