交叉數不等式

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

交叉數不等式在超大规模集成电路設計與組合幾何方面有應用。其由奧伊陶伊·米克洛什英语Miklós Ajtai瓦茨拉夫·赫瓦塔爾英语Václav Chvátal蒙提·紐邦英语Monty Newborn塞邁雷迪·安德烈四人[1]以及湯姆森·雷頓英语F. Thomson Leighton[2]分別獨立發現

敍述及歷史 编辑

交叉數不等式說明,若無向簡單圖 恰有 個頂點和 條邊,且 ,則交叉數 (即將 畫在平面上時,邊的交點數的最小可能值)滿足不等式

 

式中的常數 為截至2019年所知最優。此為伊爾·艾克曼(Eyal Ackerman)的結果。[3] 先前常數較弱的結果,可見Pach & Tóth (1997)和Pach 等人 (2006)。[4][5] 条件中的常數 也可以縮少至更佳的 ,但代價是 要換成較差的 。此版本的證明見後文。

注意式中交叉數 兩兩交叉數 不同。如Pach & Tóth (2000)指出,兩兩交叉數 係指相交邊對的最小可能數,而交叉數 係指由任意兩邊所成交叉點的最小可能數,從而 。(一些作者可能假定圖的畫法中不允許兩條邊交叉多於一次,因此需要作出區分。)[6]

應用 编辑

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

此後,Székely (1997)發現此不等式在關聯幾何方面有應用,能夠簡短地證明一些重要定理,例如塞邁雷迪-特羅特定理,其在已知平面上的點數和直線數時,給出關聯數(即點線對 的數目,其中 )的上界。證明方法是,先構造一幅圖,其頂點即為平面上的點,而邊則為同一直線上相鄰兩個關聯點之間的線段。倘若關聯數大於塞邁雷迪-特羅特的上界,則利用交叉數不等式可證,該圖的交叉數必多於直線的二元組數,但此為不可能(因為兩條直線只能交於獨一點)。此不等式同樣適用於證明貝克定理英语Beck's theorem (geometry),即若平面上 個點中,不存在線性多(即 )個點共線,則其兩兩連線產生平方多(即 )條不重合的直線,其中  為正常數。[7]塔馬爾·戴伊英语Tamal Dey類似地證明了幾何k-集英语K-set (geometry)數的上界。[8]

證明 编辑

引理 编辑

先利用歐拉公式證明以下初步估計:若圖G恰有n個頂點和e條邊,則

 

考慮 的一個僅得 個交叉的畫法。可以在每個交叉刪走其中一條邊,從而消除所有交叉。於是,剩下的邊組成一幅平面圖(因為不再有交叉),其邊數至少為 ,頂點數則仍舊為 。根據平面圖的歐拉公式 ,所以上述估計成立。(更準確來說,對於 ,有 。)

交叉數不等式 编辑

有了上述引理,就可以利用概率方法英语probabilistic method證明原來的交叉數不等式。設 為待定的概率參數,依如下步骤構造 隨機子图 :1. 以概率 独立随机选取 的各个顶点;2. 若 中一条边的两个顶点皆被选中,则在子图中构造连接这两个顶点的边。分別以   表示 的邊數、頂點數和交叉數。由於  的子圖, 的畫法已含有 的畫法。由引理,得

 

期望值,可知

 

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

 

現在取 (已設 ),移項化簡得不等式

 

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

推廣 编辑

若圖的圍長大於  Pach,Spencer & Tóth (2000)將不等式改進成[9]

 

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

 

參考資料 编辑

  1. ^ Ajtai, M.; Chvátal, V.; Newborn, M. M.; Szemerédi, E., Crossing-free subgraphs, Theory and practice of combinatorics, North-Holland Mathematics Studies 60, North-Holland, Amsterdam: 9–12, 1982, MR 0806962 (英语) .
  2. ^ 2.0 2.1 Leighton, T., Complexity Issues in VLSI, Foundations of Computing Series, Cambridge, MA: MIT Press, 1983 (英语) .
  3. ^ 3.0 3.1 Ackerman, Eyal, On topological graphs with at most four crossings per edge, Computational Geometry, 2019, 85: 101574, 31, MR 4010251, arXiv:1509.01932 , doi:10.1016/j.comgeo.2019.101574 (英语) .
  4. ^ Pach, János; Tóth, Géza, Graphs drawn with few crossings per edge, Combinatorica, 1997, 17 (3): 427–439, MR 1606052, doi:10.1007/BF01215922 (英语) .
  5. ^ Pach, János; Radoičić, Radoš; Tardos, Gábor; Tóth, Géza, Improving the crossing lemma by finding more crossings in sparse graphs, Discrete and Computational Geometry, 2006, 36 (4): 527–552, MR 2267545, doi:10.1007/s00454-006-1264-9  (英语) .
  6. ^ Pach, János; Tóth, Géza, Which crossing number is it anyway?, Journal of Combinatorial Theory, Series B, 2000, 80 (2): 225–246, doi:10.1006/jctb.2000.1978 (英语) .
  7. ^ Székely, L. A., Crossing numbers and hard Erdős problems in discrete geometry, Combinatorics, Probability and Computing, 1997, 6 (3): 353–358, MR 1464571, doi:10.1017/S0963548397002976 (英语) .
  8. ^ Dey, T. K., Improved bounds for planar k-sets and related problems, Discrete and Computational Geometry, 1998, 19 (3): 373–382, MR 1608878, doi:10.1007/PL00009354  (英语) 
  9. ^ Pach, J.; Spencer, J.; Tóth, G., New bounds on crossing numbers, Discrete and Computational Geometry, 2000, 24 (4): 623–644, MR 1799605, doi:10.1145/304893.304943 (英语) .
  10. ^ Adiprasito, Karim. Combinatorial Lefschetz theorems beyond positivity. 2018-12-26. arXiv:1812.10454v3  [math.CO] (英语).