交叉數不等式

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

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

敍述及歷史

交叉數不等式說明，若無向簡單圖${\displaystyle G}$ 恰有${\displaystyle n}$ 個頂點和${\displaystyle e}$ 條邊，且${\displaystyle e>7n}$ ，則交叉數${\displaystyle {\text{cr}}(G)}$ （即將${\displaystyle G}$ 畫在平面上時，邊的交點數的最小可能值）滿足不等式

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.}$ 

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

注意式中交叉數${\displaystyle {\text{cr}}(G)}$ 與兩兩交叉數${\displaystyle {\text{pair-cr}}(G)}$ 不同。如Pach & Tóth (2000)指出，兩兩交叉數${\displaystyle {\text{pair-cr}}(G)}$ 係指相交邊對的最小可能數，而交叉數${\displaystyle {\text{cr}}(G)}$ 係指由任意兩邊所成交叉點的最小可能數，從而${\displaystyle {\text{pair-cr}}(G)\leq {\text{cr}}(G)}$ 。（一些作者可能假定圖的畫法中不允許兩條邊交叉多於一次，因此需要作出區分。）^[6]

應用

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

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

證明

引理

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

${\displaystyle \operatorname {cr} (G)\geq e-3n.}$ 

考慮${\displaystyle G}$ 的一個僅得${\displaystyle {\text{cr}}(G)}$ 個交叉的畫法。可以在每個交叉刪走其中一條邊，從而消除所有交叉。於是，剩下的邊組成一幅平面圖（因為不再有交叉），其邊數至少為${\displaystyle e-{\text{cr}}(G)}$ ，頂點數則仍舊為${\displaystyle n}$ 。根據平面圖的歐拉公式，${\displaystyle e-{\text{cr}}(G)\leq 3n}$ ，所以上述估計成立。（更準確來說，對於${\displaystyle n\geq 3}$ ，有${\displaystyle e-{\text{cr}}(G)\leq 3n-6}$ 。）

交叉數不等式

有了上述引理，就可以利用概率方法（英语：probabilistic method）證明原來的交叉數不等式。設${\displaystyle p\ (0<p<1)}$ 為待定的概率參數，依如下步骤構造${\displaystyle G}$ 的隨機子图${\displaystyle H}$ ：1. 以概率${\displaystyle p}$ 独立随机选取${\displaystyle G}$ 的各个顶点；2. 若${\displaystyle G}$ 中一条边的两个顶点皆被选中，则在子图中构造连接这两个顶点的边。分別以${\displaystyle e_{H}}$ 、${\displaystyle n_{H}}$ 和${\displaystyle {\text{cr}}_{H}}$ 表示${\displaystyle H}$ 的邊數、頂點數和交叉數。由於${\displaystyle H}$ 是${\displaystyle G}$ 的子圖，${\displaystyle G}$ 的畫法已含有${\displaystyle H}$ 的畫法。由引理，得

${\displaystyle \operatorname {cr} _{H}\geq e_{H}-3n_{H}.}$ 

取期望值，可知

${\displaystyle \mathbb {E} [\operatorname {cr} _{H}]\geq \mathbb {E} [e_{H}]-3\mathbb {E} [n_{H}].}$ 

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

${\displaystyle p^{4}\operatorname {cr} (G)\geq p^{2}e-3pn.}$ 

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

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{64n^{2}}}.}$ 

以上論證對於${\displaystyle e>7.5n}$ 的情況可以將常數由${\displaystyle 64}$ 改進到${\displaystyle 33.75}$ 。^[3]

推廣

若圖的圍長大於${\displaystyle 2r}$ 且${\displaystyle e\geq 4n}$ ，Pach，Spencer & Tóth (2000)將不等式改進成^[9]

${\displaystyle \operatorname {cr} (G)\geq c_{r}{\frac {e^{r+2}}{n^{r+1}}}.}$ 

卡里姆·阿迪普拉西托將不等式推廣到高維情況：^[10] 若${\displaystyle \Delta }$ 為單體複形，且其${\displaystyle d}$ 維面數為${\displaystyle f_{d}(\Delta )}$ ，${\displaystyle (d-1)}$ 維面數為${\displaystyle f_{d-1}(\Delta )}$ ，滿足${\displaystyle f_{d}(\Delta )>(d+3)f_{d-1}(\Delta )}$ ，則當${\displaystyle \Delta }$ 映射到${\displaystyle \mathbf {R} ^{2d}}$ （將圖畫在平面上的高維類比）時，相交的${\displaystyle d}$ 維面對的數目至少為

${\displaystyle {\frac {f_{d}^{d+2}(\Delta )}{(d+3)^{d+2}f_{d-1}^{d+1}(\Delta )}}.}$ 

參考資料

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. Leighton, T., Complexity Issues in VLSI, Foundations of Computing Series, Cambridge, MA: MIT Press, 1983 （英语） .
3. 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] （英语）.