交叉數不等式

交叉數不等式是數學的圖論分支中的一條不等式，給出了一幅圖畫在平面上時交叉數的下界；這一結論又名交叉數引理。給定一幅圖，該下界可由其邊數和頂點數計算出。不等式斷言，若邊數$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 )}}.$