“填色问题”困扰数学界60年，这个生物学家的方法会是终极答案吗？

 长按识别二维码，参加DeepTech2018半导体产业大势论坛

在平面着色问题问世 60 多年后，一位业余数学爱好者近日取得了新的突破。

平面着色问题可以追溯到 1950 年，当时，芝加哥大学学生 Edward Nelson 提出了一个看似简单的图形问题，却让数学家们花费了几十年去解答。

假设有一个图形，图形上是一系列由长度相同的线段连接起来的点，且所有点与线都在同一平面上。我们要做的是给这些点涂颜色，相连的两个点颜色不可以重复。Nelson 的问题是：给这样的图形上色，最少用几种颜色就可以完成？当图形延伸到无限多个点时，情况又如何？

图丨这个图形有826个相连的端点，必须使用至少5种颜色来填涂，才能保证相邻端点的颜色不重复

这个问题后来被称作 Hadwiger-Nelson 问题，或“填色问题”，令无数数学家兴致勃勃、争相研究，包括当时活跃多产的匈牙利数学家保罗‧厄多斯。研究者们很快就缩小了颜色数量的范围，发现延伸到无限的图形的颜色数量应该不少于4种，不多于7种。后续的研究中，一些人证明了部分结果，却没有改变4~7这一范围。

就在上周，生物学家 Aubrey de Grey，在科学预印本网站arxiv.org上发表了一篇文章——《平面上的颜色数至少是5种》。

文章指出，图上仅用4种颜色着色是不够的。这一发现是“填色问题”被提出以来的第一个重大进展。Grey说，“我真是幸运，为一个已经问世60多年的问题提出解决方案可是稀奇事！”

图丨Aubrey de Grey，他作为联合创始人在美国加州建立了SENS研究基金会——一个研究和推广永生理念、试图通过再生性药物阻止衰老的NGO组织

Aubrey de Grey看起来不像是数学先驱。他是一个旨在开发“扭转衰老负面影响”的技术组织的联合创始人兼首席科学家。在玩棋盘游戏时，他想到了“填色问题”的解决方案。

对于一个业余数学家来说，在一个长期悬而未决的问题上取得重大进展是不寻常的，但并非前无古人。

20世纪70年代，Marjorie Rice——一位没有数学背景的家庭主妇，靠着在“凸五边形密铺”问题上做出的贡献，红遍了美国的科学专栏。她在可以无缝连接的五边形中添加了4种新的形状。耶路撒冷希伯来大学的数学家吉尔卡莱说，非专业数学家取得重大突破是令人欣慰的，因为这样可以多角度增加人们的数学经验。

图丨Marjorie Rice发现的4种“凸五边形密铺”图形

最著名的填色问题当属“四色定理”——任何一张地图只用4种颜色就能使具有共同边界的国家着上不同的颜色。这些国家的确切大小和形状并不重要，所以数学家们可以将“四色定理”转化为图论问题。即将每个国家都转化成端点，有共同边界的国家就是由一条直线连接的两个点。

图丨解释填色问题的图表

Hadwiger-Nelson 问题与“四色问题”稍有不同。它不考虑地图上有限的端点，而是会延伸到平面上无限个端点。如果两个端点恰好相隔一个单位长度，就表示两个点像地图上的国家那样“接壤”。要找到颜色数的下限，需要先构建一个具有有限端点、需要一定数量颜色的图形。这就是Aubrey de Grey做的工作。

Aubrey de Grey创建图形的灵感来自于“莫泽图”（Moser spindle），该图以数学兄弟Leo Moser和William Moser的名字命名。“莫泽图”只有7个端点和11条边，其端点的最小颜色数为4。 通过少量的计算机辅助， Grey将“莫泽图”和其他一系列端点融合成一个有着20425个端点的庞大图形，这个图形无法仅用4种颜色着色。后来他将图形缩小到1581个端点，并用计算机检查发现，的确用4种颜色是不够的。

图丨莫泽图

任何需要5种颜色的图形的发现都是一项重大成就，数学家希望找到一个满足这一点的小一点的图形。也许找到一个更小的或最小的五色图可以让研究人员更深入地了解Hadwiger-Nelson问题，从而可以证明五种颜色（或六、七种）足够填涂平面上的所有点。

Aubrey de Grey已经向加州大学洛杉矶分校的数学家陶哲轩提出申请，希望将寻找最小五色图纳入群体合作项目中，这个群体合作项目大约在10年前就开始了，当时剑桥大学的数学家Timothy Gowers想找到一种方法来促进大规模的数学在线合作。群体合作项目的工作是公开完成的，任何人都可以为之做出贡献。最近，Aubrey de Grey又参与合作，在孪生素数问题的研究上取得重大进展。

图丨Aubrey de Grey的有着1581个端点的图形

陶哲轩说，并非每一个数学问题都适合成为群体合作项目，但是Aubrey de Grey可以参与解决填色问题，毕竟它易于理解并能迅速展开研究，而且其中还有一个明显的成功标准：降低非四色图中端点的数量。果然很快，俄亥俄州立大学数学家Dustin Mixon和他的合作者Boris Alexeev发现了一个有1577个端点的图。上周六（4月14日），德克萨斯大学奥斯汀分校的计算机科学家Marijn Heule将图形缩小为874个端点，之后端点数量又减少到了826个。

研究人员的努力给60年前的Hadwiger-Nelson问题带来了全新的展望。西澳大学数学家Gordon Royle说：“像这种问题，最终的解决方案可能得运用非常有深度的数学理论，或者只是某个人的奇思妙想。”

-End-

编辑：黄张瀛 校审：黄珊

参考：

https://www.quantamagazine.org/decades-old-graph-problem-yields-to-amateur-mathematician-20180417/

关注公众号：拾黑（shiheibook）了解更多

[广告]赞助链接：

四季很好，只要有你，文娱排行榜：https://www.yaopaiming.com/
让资讯触达的更精准有趣：https://www.0xu.cn/