跳转到内容

交叉数不等式

维基百科,自由的百科全书

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

交叉数不等式在超大规模集成电路设计与组合几何方面有应用。其由奥伊陶伊·米克洛什英语Miklós Ajtai瓦茨拉夫·赫瓦塔尔英语Václav Chvátal蒙提·纽邦英语Monty Newborn塞迈雷迪·安德烈四人[1]以及汤姆森·雷顿英语F. Thomson Leighton[2]分别独立发现

叙述及历史

[编辑]

交叉数不等式说明,若无向简单图恰有个顶点和条边,且,则交叉数(即将画在平面上时,边的交点数的最小可能值)满足不等式

式中的常数为截至2019年所知最优。此为伊尔·艾克曼(Eyal Ackerman)的结果。[3] 先前常数较弱的结果,可见Pach & Tóth (1997)Pach et al. (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] (英语).