交叉数不等式

交叉数不等式是数学的图论分支中的一条不等式，给出了一幅图画在平面上时交叉数的下界；这一结论又名交叉数引理。给定一幅图，该下界可由其边数和顶点数计算出。不等式断言，若边数$e$与顶点数$n$的比值大于某个常数，则交叉数不小于$e^{3}/n^{2}$乘以另一个固定的常数。

交叉数不等式在超大规模集成电路设计与组合几何方面有应用。其由奥伊陶伊·米克洛什、瓦茨拉夫·赫瓦塔尔、蒙提·纽邦、塞迈雷迪·安德烈四人以及汤姆森·雷顿分别独立发现。

叙述及历史

交叉数不等式说明，若无向简单图$G$恰有$n$个顶点和$e$条边，且$e>7n$，则交叉数${\text{cr}}(G)$（即将$G$画在平面上时，边的交点数的最小可能值）满足不等式

$\operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.$

式中的常数$29$为截至2019年所知最优。此为伊尔·艾克曼（Eyal Ackerman）的结果。 先前常数较弱的结果，可见Pach & Tóth (1997)和Pach 等人 (2006)。 条件中的常数$7$也可以缩少至更佳的$4$，但代价是$29$要换成较差的$64$。此版本的证明见后文。

注意式中交叉数${\text{cr}}(G)$与两两交叉数${\text{pair-cr}}(G)$不同。如Pach & Tóth (2000)指出，两两交叉数${\text{pair-cr}}(G)$系指相交边对的最小可能数，而交叉数${\text{cr}}(G)$系指由任意两边所成交叉点的最小可能数，从而${\text{pair-cr}}(G)\leq {\text{cr}}(G)$。（一些作者可能假定图的画法中不允许两条边交叉多于一次，因此需要作出区分。）

应用

雷顿研究交叉数，是为了理论计算机科学中，超大型集成电路设计方面的应用。

此后，Székely (1997)发现此不等式在关联几何方面有应用，能够简短地证明一些重要定理，例如塞迈雷迪－特罗特定理，其在已知平面上的点数和直线数时，给出关联数（即点线对$(p,\ell )$的数目，其中$p\in \ell$）的上界。证明方法是，先构造一幅图，其顶点即为平面上的点，而边则为同一直线上相邻两个关联点之间的线段。倘若关联数大于塞迈雷迪－特罗特的上界，则利用交叉数不等式可证，该图的交叉数必多于直线的二元组数，但此为不可能（因为两条直线只能交于独一点）。此不等式同样适用于证明贝克定理，即若平面上$n$个点中，不存在线性多（即$n/C$）个点共线，则其两两连线产生平方多（即$n^{2}/K$）条不重合的直线，其中$C$和$K$为正常数。 塔马尔·戴伊类似地证明了几何k-集数的上界。

证明

引理

先利用欧拉公式证明以下初步估计：若图G恰有n个顶点和e条边，则

$\operatorname {cr} (G)\geq e-3n.$

考虑$G$的一个仅得${\text{cr}}(G)$个交叉的画法。可以在每个交叉删走其中一条边，从而消除所有交叉。于是，剩下的边组成一幅平面图（因为不再有交叉），其边数至少为$e-{\text{cr}}(G)$，顶点数则仍旧为$n$。根据平面图的欧拉公式，$e-{\text{cr}}(G)\leq 3n$，所以上述估计成立。（更准确来说，对于$n\geq 3$，有$e-{\text{cr}}(G)\leq 3n-6$。）

交叉数不等式

有了上述引理，就可以利用概率方法证明原来的交叉数不等式。设$p\ (0<p<1)$为待定的概率参数，依如下步骤构造$G$的随机子图$H$：1. 以概率$p$独立随机选取$G$的各个顶点；2. 若$G$中一条边的两个顶点皆被选中，则在子图中构造连接这两个顶点的边。分别以$e_{H}$、$n_{H}$和${\text{cr}}_{H}$表示$H$的边数、顶点数和交叉数。由于$H$是$G$的子图，$G$的画法已含有$H$的画法。由引理，得

$\operatorname {cr} _{H}\geq e_{H}-3n_{H}.$

取期望值，可知

$\mathbb {E} [\operatorname {cr} _{H}]\geq \mathbb {E} [e_{H}]-3\mathbb {E} [n_{H}].$

由于$G$中每个顶点选入$H$中的概率为$p$，有$\mathbb {E} [n_{H}]=pn$。类似知$G$中每条边入选$H$的概率为$p^{2}$（因为其两端皆要入选$H$），所以$\mathbb {E} [e_{H}]=p^{2}e$。最后，在$G$的画法中，每个交叉有$p^{4}$的概率落入$H$，因为每个交叉牵涉四个顶点。（若从同一个顶点出发画出两条边有交叉，则不妨将两条边第一次相交以后的部分对调，从而令交叉的数目变少。由于所考虑的画法仅得${\text{cr}}(G)$个交叉，无法再减少交叉，所以每个交叉必由两条无公共端点的边组成。）因此，$\mathbb {E} [cr_{H}]=p^{4}{\text{cr}}(G)$，于是上式可写成

$p^{4}\operatorname {cr} (G)\geq p^{2}e-3pn.$

现在取$p=4n/e<1$（已设$e>4n$），移项化简得不等式

$\operatorname {cr} (G)\geq {\frac {e^{3}}{64n^{2}}}.$

以上论证对于$e>7.5n$的情况可以将常数由$64$改进到$33.75$。

推广

若图的围长大于$2r$且$e\geq 4n$，Pach，Spencer & Tóth (2000)将不等式改进成

$\operatorname {cr} (G)\geq c_{r}{\frac {e^{r+2}}{n^{r+1}}}.$

卡里姆·阿迪普拉西托将不等式推广到高维情况： 若$\Delta$为单体复形，且其$d$维面数为$f_{d}(\Delta )$，$(d-1)$维面数为$f_{d-1}(\Delta )$，满足$f_{d}(\Delta )>(d+3)f_{d-1}(\Delta )$，则当$\Delta$映射到$\mathbf {R} ^{2d}$（将图画在平面上的高维类比）时，相交的$d$维面对的数目至少为

${\frac {f_{d}^{d+2}(\Delta )}{(d+3)^{d+2}f_{d-1}^{d+1}(\Delta )}}.$