交叉數不等式是數學的圖論分支中的一条不等式，給出了一幅图画在平面上时交叉數的下界；这一结论又名交叉数引理。給定一幅圖，該下界可由其邊數和頂點數計算出。不等式斷言，若邊數e与頂點數n的比值大于某个常数，則交叉數不小于e^3/n^2乘以另一个固定的常数。
交叉數不等式在超大规模集成电路設計與組合幾何方面有應用。其由、、、塞邁雷迪·安德烈四人以及分別獨立發現。
敍述及歷史
交叉數不等式說明，若無向簡單圖G恰有n個頂點和e條邊，且e>7n，則交叉數 \text{cr}(G)（即將G畫在平面上時，邊的交點數的最小可能值）滿足不等式
:\operatorname{cr}(G) \geq \frac{e^3}{29 n^2}.
式中的常數29為截至2019年所知最優。此為伊爾·艾克曼（Eyal Ackerman）的結果。
先前常數較弱的結果，可見和。
条件中的常數7也可以縮少至更佳的4，但代價是29要換成較差的64。此版本的證明見後文。
注意式中交叉數\text{cr}(G)與兩兩交叉數\text{pair-cr}(G)不同。如指出，兩兩交叉數\text{pair-cr}(G)係指相交邊對的最小可能數，而交叉數\text{cr}(G)係指由任意兩邊所成交叉點的最小可能數，從而\text{pair-cr}(G) \leq \text{cr}(G)。（一些作者可能假定圖的畫法中不允許兩條邊交叉多於一次，因此需要作出區分。）
應用
雷頓研究交叉數，是為了理論計算機科學中，超大型積體電路設計方面的應用。
類似地證明了數的上界。
證明
引理
先利用歐拉公式證明以下初步估計：若圖恰有個頂點和條邊，則
: \operatorname{cr}(G) \geq e - 3n.
考慮G的一個僅得\text{cr}(G)個交叉的畫法。可以在每個交叉刪走其中一條邊，從而消除所有交叉。於是，剩下的邊組成一幅平面圖（因為不再有交叉），其邊數至少為e-\text{cr}(G)，頂點數則仍舊為n。根據平面圖的歐拉公式，e-\text{cr}(G) \le 3n，所以上述估計成立。（更準確來說，對於n \ge 3，有e-\text{cr}(G) \le 3n-6。）
交叉數不等式
有了上述引理，就可以利用證明原來的交叉數不等式。設p \ (0 為待定的概率參數，依如下步骤構造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 - 3 p n.
現在取p = 4n/e （已設e > 4n），移項化簡得不等式
: \operatorname{cr}(G) \geq \frac{e^3}{64 n^2}.
以上論證對於e> 7.5n的情況可以將常數由64改進到33.75。
:\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)}.
參考資料
评论 (0)