科学家最近证明，在这个包含826个顶点的图中，需要至少5种颜色以保证被线段连接的亮点颜色均不相同。
沉寂了近60年的“平面色数”问题在上个月终于出现了关键进展，令人惊奇的是，取得这一突破的不是专业数学家，而是一名研究衰老问题的生物学家。业余数学爱好者，是怎样做到这一点的？
撰文 | Evelyn Lamb
翻译 | 潘磊
审校 | 吴非
1950年，芝加哥大学的学生爱德华·尼尔森问了一个看起来很简单，却困扰无数数学家数十年的问题：想象一幅由点和连接点的线段构成的图，图中所有线段的长度一致，且都落在平面上。现在给图中所有的点上色，要求线段两段的点不能同色。问题来了：如果图上有无限多的点，那么最少需要多少种颜色？
现在，这个寻找平面图色数的问题被称作Hadwiger-Nelson问题，它激起许多数学家的兴趣，包括著名的匈牙利数学家Paul Erdős，他是20世纪最高产的数学家之一。数学家们很快缩小了色数范围，得出无限点图的解下界是4，上界是7。之后几十年，其他研究者陆续证出一些局部解，但是4到7的范围无人改写。
直到今年，突破性的成果才出现。令人惊奇的是，带来这一突破的不是数学家，而是一名生物学家。上个月，研究衰老的英国生物学家Aubrey de Grey在论文预发表网站arxiv.org上投了一篇标题为“The Chromatic Number of the Plane Is at Least 5.”（平面色数问题的解不会小于5）的论文。De Grey此前因预测现代人类能够活到1000岁而闻名。在这篇论文中，他证明了不可能用4种颜色完成上色，这是Hadwiger-Nelson问题在沉寂了数十年后的第一步关键进展。“我可真是太幸运了，”de Grey 说道，“想出一个60年问题的解，这可不是每天都能做到的。”
研究生物的数学开拓者
De Grey成了一位看似不可能的数学领域开拓者。他的本职是“逆转衰老负面影响”（SENS）研究机构的联合创建人兼首席科学家。从棋牌游戏中，他找到了解决平面色数问题的灵感。De Grey曾经是一名颇有实力的黑白棋（Othello）选手，通过比赛他还结交了一些同样热衷于这项运动的数学研究者。他正是从这些数学家口中听到了图论，到现在de Grey仍时不时在业余时间研究这类问题。他说：“有时我需要脱离开生物学工作去休息，这时我会去思考数学。”趁着去年的圣诞假期，他找到了研究数学问题的机会。
虽然几率不大，但业余数学爱好者能在一个长期悬而未决的问题上取得重要进展，这种事确有发生。20世纪70年代，一位没有数学背景的家庭主妇Marjorie Rice在《科学美国人》杂志上偶然看到一篇讨论平面密铺五边形的专栏，于是她对这个问题产生了兴趣。最终，她在这个问题下添加了四种新的五边形。Gil Kalai是希伯来大学的数学家，他认为非专业的数学研究者能创造出重大突破是一件好事。“这能为数学研究带来更多视角。”
四色猜想可能是是世界上最著名的染色问题。假设地图上每个国家都是一个连续的区块，那么任何地图都能够只用四种颜色来着色，使得没有两个相邻的国家颜色相同。各个国家区域的实际大小和形状对问题并不重要，所以数学家可以把它转化成图论的语言——点阵和连接的线段，如果两个国家毗邻就把两个点连接起来。
Hadwiger-Nelson问题和四色猜想则有一些不同。它讨论的不是可以在地图上呈现的有限点阵，而是把范围拓展到平面上无限的点。如果两个点恰好相隔一个单位距离，就用线段连接这两个点。要寻找平面色数的下界，需要构造出一个必须用某个数量颜色染色的有限点阵，这也是de Grey所做的。
他的点图构造基于莫泽图（Moser spindle）。Moser取自数学家兄弟Leo Moser和William Moser的姓氏。莫泽图包含7个点和11条边界，其最小染色数为4。通过一些计算机辅助， Grey将莫泽图和另一种点阵精巧地融合成一个有着20425个端点的庞大图形，这个图形无法用4种颜色完全染色。接着他将图形规模缩小至1581个点，并且用计算机检查确定仅用4种颜色不可行。
加入Polymath计划？
找到任何一种最小染色数为5的图形是一个重大的突破，但是数学家总期望找到有着相同性质却更简单的图形。也许在发现更小的或找到最小的五色图的过程中，研究人员能更深入地理解Hadwiger-Nelson问题，从而有机会去证明五种颜色（或六、七种）能完全着色平面上的所有点。
De Grey 已向加州大学洛杉矶分校的陶哲轩教授提出申请，期望将寻找最小五色点图问题加入Polymath计划。这个合作项目已有十年之久，源于剑桥大学数学家Timothy Gowers促进大规模的数学在线合作的想法。Polymath计划中的工作完全开放，任何人都能参与思考研究。
陶哲轩说，并非所有数学问题都适合Polymath，但是de Grey的工作有我们需要的特点。问题容易理解，能迅速开展研究，而且每一步进展能有明确的标准：缩小非4色点图的点阵规模。很快，俄亥俄州立大学的Dustin Mixon与合作者Boris Alexeev发现了一种包含1577点的图。随后，德克萨斯大学奥斯汀分校的计算机科学家Marijn Heule又将顶点数先后缩小至874和826个。
有着60年历史的hadwiger-Nelson问题值得拿出来，再好好研究一番。“对于类似的问题或猜想，最终答案有可能涉及难以想像的深奥数学理论，”西澳大学数学家Gordon Royle说，“或者，仅仅是个人的奇思妙想，就改写了染色问题的下界。”
原文链接：
https://www.quantamagazine.org/decades-old-graph-problem-yields-to-amateur-mathematician-20180417/
发表于 2018-5-13 23:04
收藏
分享