交叉数不等式

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

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

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

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

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

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

引理

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

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

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

交叉数不等式

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

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

取期望值，可知

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

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

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

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

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

以上论证对于${\displaystyle e>7.5n}$ 的情况可以将常数由${\displaystyle 64}$ 改进到${\displaystyle 33.75}$ 。^[3]

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

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

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

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