哈德维格-纳尔逊问题

哈德维格-纳尔逊问题(英语:Hadwiger–Nelson problem),是指在平面上为每点填色,最少要多少种颜色,才能使若两点距离为1,其颜色必定不相同呢?用图论的语言可这样叙述:设G为,G的顶点是平面上的所有点,两个顶点相邻若且唯若它们在平面上的距离为1,求G的点色数。这个问题等于求任意G的有限子集的最大点色数[1]

这个问题的下界是5,上界是7。

只有三种颜色无法完成的证明如下:平面上任取一点A,设其颜色为x,以其为圆心,分别以1和为半径做圆。在半径的圆上任取一点B,以其为圆心1为半径做圆,交以A为圆心1为半径的圆与C和D,则C与D的距离为1,所以A、C、D颜色必须各不相同,设C、D的颜色分别为y、z。B、C、D的颜色也必须各不相同,所以B的颜色只能是x,所以以A为圆心为半径的圆上所有的点的颜色都必须为x,在其上选择两个相距为1的点,它们的颜色相同,与题设矛盾。

另一方面,将平面划成以外接圆直径略少于1的正六边形密铺,以七种颜色填上,使得一个正六边形和相邻的六个正六边形的颜色不同。这样的密铺符合距离为1的点颜色不相同,所以上界是7。

历史

这个问题由E. Nelson在1950年提出,马丁·加德纳在1960年的《科学美国人》杂志公开发表。Hugo Hadwiger在1945年曾发表一个相关的定理[2][3]

2018年,业余数学家兼生物学家奥布里·大卫·尼古拉斯·杰士伯·德格雷找到了[4]一个1581个点的、不可4染色的、所有边长度为1的图。其证明是基于计算机辅助的。

变化

  • 三维空间:上界15,下界6
  • 限制某种颜色的集的性质。例如要求每种颜色的集都是勒贝格可测的,则下界为5。[5]

相关连结

参考资料

  1. ^ de Bruijn, N.G.; Erdős, P. (1951). "A colour problem for infinite graphs and a problem in the theory of relations". Nederl. Akad. Wetensch. Proc. Ser. A 54: 371–373.
  2. ^ Hadwiger, Hugo (1945). "Überdeckung des euklidischen Raumes durch kongruente Mengen". Portugal. Math. 4: 238–242.
  3. ^ Jensen, Tommy R.; Toft, Bjarne (1995). Graph Coloring Problems. Wiley-Interscience Series in Discrete Mathematics and Optimization, 150–152.
  4. ^ de Grey, Aubrey D. N. J. The chromatic number of the plane is at least 5. arXiv:1804.02385 [math]. 2018-04-07 [2018-04-18]. (原始内容存档于2021-01-14). 
  5. ^ Croft, Hallart T.; Falconer, Kenneth J.; Guy, Richard K. (1991). Unsolved Problems in Geometry. Springer-Verlag, Problem G10.

参考文献

  • Chilakamarri, K. B. (1993). "The unit-distance graph problem: a brief survey and some new results". Bull Inst. Combin. Appl. 8: 39–60.