查看“︁交叉數不等式”︁的源代码

'''交叉數不等式'''是數學的[[圖論]]分支中的一条[[不等式]]，給出了一幅[[图 (图论)|图]]画在平面上时[[交叉數]]的[[上界和下界|下界]]；这一结论又名'''交叉数引理'''。給定一幅[[圖 (數學)|圖]]，該下界可由其[[图论术语#边|邊]]數和[[图论术语#顶点|頂點]]數計算出。不等式斷言，若邊數<math>e</math>与頂點數<math>n</math>的比值大于某个常数，則交叉數不小于<math>e^3/n^2</math>乘以另一个固定的常数。

交叉數不等式在[[超大规模集成电路]]設計與[[離散幾何學|組合幾何]]方面有應用。其由{{link-en|奧伊陶伊·米克洛什|Miklós Ajtai}}<!--遵循[[施魏策爾·米克洛什數學競賽]]的先例和[[WP: 外語譯音表/匈牙利語]]暫譯-->、{{link-en|瓦茨拉夫·赫瓦塔爾|Václav Chvátal}}<!--遵循[[瓦茨拉夫·哈維爾]]的先例和[[WP: 外語譯音表/捷克語]]暫譯-->、{{link-en|蒙提·紐邦|Monty Newborn}}<!--遵循[[蒙提·歐伍]]和[[歐陽文風]]中Newborn譯為紐邦的先例-->、[[塞邁雷迪·安德烈]]四人<ref>{{citation
 | last1 = Ajtai | first1 = M. 
 | last2 = Chvátal | first2 = V. 
 | last3 = Newborn | first3 = M. M.
 | last4 = Szemerédi | first4 = E. | author4-link = 塞邁雷迪·安德烈
 | contribution = Crossing-free subgraphs
 | mr = 806962
 | pages = 9–12
 | publisher = North-Holland, Amsterdam
 | series = North-Holland Mathematics Studies
 | title = Theory and practice of combinatorics
 | volume = 60 
 | year = 1982
 | language = en
}}.</ref>以及{{link-en|湯姆森·雷頓|F. Thomson Leighton}}<!--遵循[[第一代開爾文男爵威廉·湯姆森]]和[[提摩西·雷頓]]的先例--><ref name="leighton">{{citation
 | last = Leighton | first = T. 
 | location = Cambridge, MA
 | publisher = MIT Press
 | series = Foundations of Computing Series
 | title = Complexity Issues in VLSI
 | year = 1983
 | language = en}}.</ref>分別[[重复独立发现发明列表|獨立發現]]。

==敍述及歷史==
交叉數不等式說明，若[[无向图|無向]][[图_(数学)#简单图|簡單圖]]<math>G</math>恰有<math>n</math>個頂點和<math>e</math>條邊，且<math>e>7n</math>，則[[交叉數]]<math> \text{cr}(G)</math>（即將<math>G</math>畫在平面上時，邊的交點數的最小可能值）滿足[[不等|不等式]]
:<math>\operatorname{cr}(G) \geq \frac{e^3}{29 n^2}.</math>

式中的常數<math>29</math>為截至2019年所知最優。此為伊爾·艾克曼（Eyal Ackerman）<!--遵循[[大衛·哈伯]]中Eyal Podell譯為伊爾·波戴爾和[[格雷厄姆·阿克曼]]的先例暫譯-->的結果。<ref name="pt">{{citation
 | last = Ackerman | first = Eyal
 | arxiv = 1509.01932
 | doi = 10.1016/j.comgeo.2019.101574
 | journal = Computational Geometry
 | mr = 4010251
 | page = 101574, 31
 | title = On topological graphs with at most four crossings per edge
 | volume = 85
 | year = 2019
 | language = en}}.</ref>
先前常數較弱的結果，可見{{harvtxt|Pach|Tóth|1997}}和{{harvtxt|Pach|Radoičić|Tardos|Tóth|2006}}。<ref>{{citation
 | last1 = Pach | first1 = János
 | last2 = Tóth | first2 = Géza
 | doi = 10.1007/BF01215922
 | issue = 3
 | journal = Combinatorica
 | mr = 1606052
 | pages = 427–439
 | title = Graphs drawn with few crossings per edge
 | volume = 17
 | year = 1997
 | language = en}}.</ref><ref>{{citation
 | last1 = Pach | first1 = János 
 | last2 = Radoičić | first2 = Radoš
 | last3 = Tardos | first3 = Gábor
 | last4 = Tóth | first4 = Géza
 | doi = 10.1007/s00454-006-1264-9
 | issue = 4
 | journal = Discrete and Computational Geometry
 | mr = 2267545
 | pages = 527–552
 | title = Improving the crossing lemma by finding more crossings in sparse graphs
 | volume = 36
 | year = 2006| doi-access = free 
 | language = en
 }}.</ref>
条件中的常數<math>7</math>也可以縮少至更佳的<math>4</math>，但代價是<math>29</math>要換成較差的<math>64</math>。此版本的證明見後文。

注意式中交叉數<math>\text{cr}(G)</math>與'''兩兩交叉數'''<math>\text{pair-cr}(G)</math>不同。如{{harvtxt|Pach|Tóth|2000}}指出，兩兩交叉數<math>\text{pair-cr}(G)</math>係指相交邊對的最小可能數，而交叉數<math>\text{cr}(G)</math>係指由任意兩邊所成交叉點的最小可能數，從而<math>\text{pair-cr}(G) \leq \text{cr}(G)</math>。（一些作者可能假定圖的畫法中不允許兩條邊交叉多於一次，因此需要作出區分。）<ref name="jp">{{citation
 | last1 = Pach | first1 = János
 | last2 = Tóth | first2 = Géza
 | doi = 10.1006/jctb.2000.1978
 | journal = Journal of Combinatorial Theory, Series B
 | title = Which crossing number is it anyway? 
 | volume = 80
 | year = 2000| issue = 2
 | pages = 225–246
 | language = en
 }}.</ref>

==應用==
雷頓研究交叉數，是為了理論計算機科學中，[[超大型積體電路]]設計方面的應用。<ref name="leighton"/>

此後，{{harvtxt|Székely|1997}}發現此不等式在[[關聯幾何]]方面有應用，能夠簡短地證明一些重要定理，例如[[塞邁雷迪－特羅特定理]]，其在已知平面上的點數和直線數時，給出關聯數（即點線對<math>(p, \ell)</math>的數目，其中<math>p \in \ell</math>）的[[上界和下界|上界]]。證明方法是，先構造一幅圖，其頂點即為平面上的點，而邊則為同一直線上相鄰兩個關聯點之間的線段。倘若關聯數大於塞邁雷迪－特羅特的上界，則利用交叉數不等式可證，該圖的交叉數必多於直線的二元組數，但此為不可能（因為兩條直線只能交於獨一點）。此不等式同樣適用於證明{{link-en|貝克定理|Beck's theorem (geometry)}}，即若平面上<math>n</math>個點中，不存在線性多（即<math> n/C</math>）個點共線，則其兩兩連線產生平方多（即<math>n^2/K</math>）條不重合的直線，其中<math>C</math>和<math>K</math>為正常數。<ref>{{citation
 | last = Székely | first = L. A.
 | doi = 10.1017/S0963548397002976
 | issue = 3
 | journal = Combinatorics, Probability and Computing
 | mr = 1464571
 | pages = 353–358
 | title = Crossing numbers and hard Erdős problems in discrete geometry
 | volume = 6
 | year = 1997
 | language = en}}.</ref>
{{link-en|塔馬爾·戴伊|Tamal Dey}}<!--遵循[[薩凡卡爾·戴伊]]的先例和[[WP:外語譯音表]]暫譯-->類似地證明了{{link-en|幾何''k''-集|K-set (geometry)}}數的上界。<ref>{{citation
 | last = Dey | first = T. K. | authorlink = Tamal Dey
 | doi = 10.1007/PL00009354
 | issue = 3
 | journal = Discrete and Computational Geometry
 | mr = 1608878
 | pages = 373–382
 | title = Improved bounds for planar {{mvar|k}}-sets and related problems
 | volume = 19
 | year = 1998| doi-access = free
 | language = en
 }}</ref>

==證明==
=== 引理 ===
先利用[[平面图_(图论)#歐拉公式|歐拉公式]]證明以下初步估計：若圖{{mvar|G}}恰有{{mvar|n}}個頂點和{{mvar|e}}條邊，則

: <math>\operatorname{cr}(G) \geq e - 3n.</math>

考慮<math>G</math>的一個僅得<math>\text{cr}(G)</math>個交叉的畫法。可以在每個交叉刪走其中一條邊，從而消除所有交叉。於是，剩下的邊組成一幅[[平面圖 (圖論)|平面圖]]（因為不再有交叉），其邊數至少為<math>e-\text{cr}(G)</math>，頂點數則仍舊為<math>n</math>。根據平面圖的[[平面图_(图论)#歐拉公式|歐拉公式]]，<math>e-\text{cr}(G) \le 3n</math>，所以上述估計成立。（更準確來說，對於<math>n \ge 3</math>，有<math>e-\text{cr}(G) \le  3n-6</math>。）
=== 交叉數不等式 ===
有了上述引理，就可以利用{{link-en|概率方法|probabilistic method}}證明原來的交叉數不等式。設<math>p \ (0 < p < 1)</math>為待定的[[概率]]參數，依如下步骤構造<math>G</math>的[[隨機圖|隨機]][[子图]]<math>H</math>：1. 以概率<math>p</math>独立随机选取<math>G</math>的各个顶点；2. 若<math>G</math>中一条边的两个顶点皆被选中，则在子图中构造连接这两个顶点的边。分別以<math>e_H</math>、<math>n_H</math>和<math>\text{cr}_H</math>表示<math>H</math>的邊數、頂點數和交叉數。由於<math>H</math>是<math>G</math>的子圖，<math>G</math>的畫法已含有<math>H</math>的畫法。由引理，得

:<math>\operatorname{cr}_H \geq e_H - 3n_H.</math>

取[[期望值]]，可知

:<math>\mathbb{E}[\operatorname{cr}_H] \geq \mathbb{E}[e_H] - 3 \mathbb{E}[n_H].</math>

由於<math>G</math>中每個頂點选入<math>H</math>中的概率為<math>p</math>，有<math>\mathbb{E}[n_H] =pn</math>。類似知<math>G</math>中每條邊入选<math>H</math>的概率為<math>p^2</math>（因為其兩端皆要入选<math>H</math>），所以<math>\mathbb{E}[e_H]=p^2 e</math>。最後，在<math>G</math>的畫法中，每個交叉有<math>p^4</math>的概率落入<math>H</math>，因為每個交叉牽涉四個頂點。（若從同一個頂點出發畫出兩條邊有交叉，則不妨將兩條邊第一次相交以後的部分對調，從而令交叉的數目變少。由於所考慮的畫法僅得<math>\text{cr}(G)</math>個交叉，無法再減少交叉，所以每個交叉必由兩條無公共端點的邊組成。）因此，<math>\mathbb{E}[cr_H]=p^4\text{cr}(G)</math>，於是上式可寫成

: <math> p^4 \operatorname{cr}(G) \geq p^2 e - 3 p n.</math>

現在取<math>p = 4n/e < 1</math>（已設<math>e > 4n</math>），移項化簡得不等式

: <math> \operatorname{cr}(G) \geq \frac{e^3}{64 n^2}.</math>

以上論證對於<math>e> 7.5n</math>的情況可以將常數由<math>64</math>改進到<math>33.75</math>。<ref name="pt"/>

==推廣==
若圖的[[圍長 (圖論)|圍長]]大於<math>2r</math>且<math>e\ge 4n</math>，{{harvtxt|Pach|Spencer|Tóth|2000}}將不等式改進成<ref>{{citation
 | last1 = Pach | first1 = J. 
 | last2 = Spencer | first2 = J.
 | last3 = Tóth | first3 = G.
 | doi = 10.1145/304893.304943
 | issue = 4
 | journal = Discrete and Computational Geometry
 | mr = 1799605
 | pages = 623–644
 | title = New bounds on crossing numbers
 | volume = 24
 | year = 2000
|language=en}}.</ref>
:<math>\operatorname{cr}(G) \geq c_r\frac{e^{r+2}}{n^{r+1}}.</math>
[[卡里姆·阿迪普拉西托]]<!--遵循[[卡里姆·本澤馬]]的先例，並按[[WP: 外語譯音表/印尼語]]暫譯-->將不等式推廣到高維情況：<ref>{{Cite arxiv|last=Adiprasito|first=Karim|date=2018-12-26|title=Combinatorial Lefschetz theorems beyond positivity|class=math.CO|eprint=1812.10454v3|language=en}}</ref> 若<math>\Delta</math>為[[單體複形]]，且其<math>d</math>維面數為<math>f_d(\Delta)</math>，<math>(d-1)</math>維面數為<math>f_{d-1}(\Delta)</math>，滿足<math>f_d(\Delta)> (d+3)f_{d-1}(\Delta)</math>，則當<math>\Delta</math>映射到<math>\mathbf{R}^{2d}</math>（將圖畫在平面上的高維類比）時，相交的<math>d</math>維面對的數目至少為

<math>\frac{f_d^{d+2}(\Delta)}{(d+3)^{d+2}f_{d-1}^{d+1}(\Delta)}.</math>

==參考資料==
{{reflist|30em}}

{{圖論}}
[[Category:拓撲圖論]]
[[Category:不等式]]
[[Category:數學定理]]