交叉數不等式

交叉數不等式是數學的圖論分支中的一条不等式，給出了一幅图画在平面上时交叉數的下界；这一结论又名交叉数引理。給定一幅圖，該下界可由其邊數和頂點數計算出。不等式斷言，若邊數与頂點數的比值大于某个常数，則交叉數不小于乘以另一个固定的常数。

交叉數不等式在超大规模集成电路設計與組合幾何方面有應用。其由、、、塞邁雷迪·安德烈四人.以及.分別獨立發現。

敍述及歷史
交叉數不等式說明，若無向簡單圖恰有個頂點和條邊，且，則交叉數（即將畫在平面上時，邊的交點數的最小可能值）滿足不等式

式中的常數為截至2019年所知最優。此為伊爾·艾克曼（Eyal Ackerman）的結果。.
先前常數較弱的結果，可見和。..
条件中的常數也可以縮少至更佳的，但代價是要換成較差的。此版本的證明見後文。

注意式中交叉數與兩兩交叉數不同。如指出，兩兩交叉數係指相交邊對的最小可能數，而交叉數係指由任意兩邊所成交叉點的最小可能數，從而。（一些作者可能假定圖的畫法中不允許兩條邊交叉多於一次，因此需要作出區分。）.

應用
雷頓研究交叉數，是為了理論計算機科學中，超大型積體電路設計方面的應用。

此後，發現此不等式在關聯幾何方面有應用，能夠簡短地證明一些重要定理，例如塞邁雷迪－特羅特定理，其在已知平面上的點數和直線數時，給出關聯數（即點線對的數目，其中）的上界。證明方法是，先構造一幅圖，其頂點即為平面上的點，而邊則為同一直線上相鄰兩個關聯點之間的線段。倘若關聯數大於塞邁雷迪－特羅特的上界，則利用交叉數不等式可證，該圖的交叉數必多於直線的二元組數，但此為不可能（因為兩條直線只能交於獨一點）。此不等式同樣適用於證明，即若平面上個點中，不存在線性多（即）個點共線，則其兩兩連線產生平方多（即）條不重合的直線，其中和為正常數。.
類似地證明了數的上界。

證明
 引理 
先利用歐拉公式證明以下初步估計：若圖恰有個頂點和條邊，則



考慮的一個僅得個交叉的畫法。可以在每個交叉刪走其中一條邊，從而消除所有交叉。於是，剩下的邊組成一幅平面圖（因為不再有交叉），其邊數至少為，頂點數則仍舊為。根據平面圖的歐拉公式，，所以上述估計成立。（更準確來說，對於，有。）
 交叉數不等式 
有了上述引理，就可以利用證明原來的交叉數不等式。設為待定的概率參數，依如下步骤構造的隨機子图：1. 以概率独立随机选取的各个顶点；2. 若中一条边的两个顶点皆被选中，则在子图中构造连接这两个顶点的边。分別以、和表示的邊數、頂點數和交叉數。由於是的子圖，的畫法已含有的畫法。由引理，得

取期望值，可知

由於中每個頂點选入中的概率為，有。類似知中每條邊入选的概率為（因為其兩端皆要入选），所以。最後，在的畫法中，每個交叉有的概率落入，因為每個交叉牽涉四個頂點。（若從同一個頂點出發畫出兩條邊有交叉，則不妨將兩條邊第一次相交以後的部分對調，從而令交叉的數目變少。由於所考慮的畫法僅得個交叉，無法再減少交叉，所以每個交叉必由兩條無公共端點的邊組成。）因此，，於是上式可寫成



現在取（已設），移項化簡得不等式



以上論證對於的情況可以將常數由改進到。

推廣
若圖的圍長大於且，將不等式改進成.

卡里姆·阿迪普拉西托將不等式推廣到高維情況： 若為單體複形，且其維面數為，維面數為，滿足，則當映射到（將圖畫在平面上的高維類比）時，相交的維面對的數目至少為

參考資料

Category:拓撲圖論
Category:不等式
Category:數學定理