哈德维格-纳尔逊问题

Hadwiger-Nelson problem.png

哈德维格-纳尔逊问题（英语：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.