1. 交叉数不等式

定义图 $G$ 的交叉数 $\mathrm{cr}(G)$ 为将图 $G$ 画在平面上时边的交叉点的最小数目. 我们想知道的是, 给定一个有很多边的图, 它的交叉数至少有多大?

定理 1.1 (交叉数不等式 Ajtai, Chvátal, Newborn 和 Szemerédi(1982); Leighton (1984)). 如果 $G=(V,E)$ 是满足 $|E|\ge 4|V|$ 的图, 则存在常数 $c>0$ 使 $\mathrm{cr}(G)\ge c|E{|}^3/|V{|}^2$ .

根据该定理我们直接推导出结论: 任意一个带有 $\Omega \left(n^2\right)$ 边的 $n$-顶点图都有 $\Omega \left(n^4\right)$ 交叉点.

证明. 对于任何至少有一个圈的连通平面图, 我们有 $3|F|\le 2|E|$, 其中 $|F|$ 表示图的面 (也称作区域) . 每个面与至少三个边相邻且每个边与最多两个面相邻, 两次计数我们可以得到该不等式. 应用 Euler 公式 ¹, 我们得到 $|E|\le 3|V|-6$. 因此, 对任意平面图 (包括那些非连通或没有圈的平面图) $G$ 一定有 $|E|\le 3|V|$. 所以, 如果 $|E|>3|V|$ 则有 $\mathrm{cr}(G)>0$.

假设图 $G$ 满足 $|E|>3|V|$. 我们可以通过删除每条造成交叉的边来得到平面图, 因此我们有 $|E|-\mathrm{cr}(G)\le 3|V|$. 所以对于任意图 $G$, 我们有$$\mathrm{cr}(G)\ge |E|-3|V|.$$(1.1)为了证明所需的不等式, 我们借助概率方法. 令 $p\in [0,1]$ 是一待定的实数, $G^{\prime }=\left(V^{\prime },E^{\prime }\right)$ 是一个以概率 $p$ 随机 (i.i.d.) 保留 $G$ 的每个顶点得到的图. 根据 (1.1) 我们知道对于任意的 $G^{\prime }$ 一定有 $\mathrm{cr}\left(G^{\prime }\right)\ge \left|E^{\prime }\right|-3\left|V^{\prime }\right|$. 因此, 如果我们两边取期望, 不等式仍成立: $$\mathbb{E}\mathrm{cr}\left(G^{\prime }\right)\ge \mathbb{E}\left|E^{\prime }\right|-3\mathbb{E}\left|V^{\prime }\right|.$$因为当且仅当保留边的两个端点时边仍存在, 所以有 $\mathbb{E}\left|E^{\prime }\right|=p^2|E|$ . 类似地我们有 $\mathbb{E}\left|V^{\prime }\right|=p|V|$. 同样的想法, 我们得到不等式 $p^4\mathrm{cr}(G)\ge \mathbb{E}\mathrm{cr}\left(G^{\prime }\right)$ (两条边的四个顶点都保留时交叉点才保留, 大于号是因为会出现顶点重复的情况) . 因此我们有$$\mathrm{cr}(G)\ge p^{-2}|E|-3p^{-3}|V|$$最后我们通过设置 $p\in [0,1]$ 得到我们想要的不等式. 具体来说, 取 $p$ 满足 $4p^{-3}|V|=p^{-2}|E|$. 根据条件 $|E|\ge$ $4|V|$, 这是可以做到的.

$\square$

1.	^ Euler 公式: 设 $G$ 是连通的平面图, $v,e,f$ 分别是其顶点数、边数和面数, 则 $v-e+f=2$