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

交叉数不等式在超大规模集成电路设计与组合几何方面有应用。其由奥伊陶伊·米克洛什（英语：Miklós Ajtai）、瓦茨拉夫·赫瓦塔尔（英语：Václav Chvátal）、蒙提·纽邦（英语：Monty Newborn）、塞迈雷迪·安德烈四人^[1]以及汤姆森·雷顿（英语：F. Thomson Leighton）^[2]分别独立发现。

交叉数不等式说明，若无向简单图${\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 ))).}$