交叉数不等式

交叉数不等式是数学的图论分支中的一条不等式,给出了一幅画在平面上时交叉数下界;这一结论又名交叉数引理。给定一幅,该下界可由其数和顶点数计算出。不等式断言,若边数与顶点数的比值大于某个常数,则交叉数不小于乘以另一个固定的常数。

交叉数不等式在超大规模集成电路设计与组合几何方面有应用。其由奥伊陶伊·米克洛什英语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] (英语).