物理科学

一个老问题会产生一个新的见解吗?也许是对四色定理的一个优雅的证明?

四色问题是最著名的数学问题之一。它抗拒了一百多年的证据才最终屈服;最终,有了一个有效的证明,但它依赖于一千多个小时的计算机时间。吉姆·蒂利的研究表明,戏剧性的简化最终可能成为可能。他发现了一个四色定理的最小反例必须证明的性质——坎佩-锁定,并根据广泛的调查,提出了一个猜想,伯克霍夫钻石是唯一的坎佩-锁定结构。

图着色涉及到给称为图的数学对象的顶点分配标签或颜色。四色问题是代数图理论发展的原始动力之一。图形着色用于许多现实世界的问题中,例如在安排体育赛事、计划考试时间表和安排座位计划时尽量减少冲突,甚至在有许多角落的建筑中放置闭路电视摄像机,以尽量减少摄像机重叠。它也为数独谜题提供了基础。

图1所示。代表二十面体的12个顶点的平面三角剖分的一种适当的颜色。单红-蓝肯普链显示突出。

4色的问题
1852年,英国著名数学家和逻辑学家奥古斯都·德·摩根的学生弗朗西斯·格思里提出了四色问题。他提出的问题是关于满足某些条件的地图,例如不包含任何孔,并将每个地区(例如国家或州)连接起来,这样就没有一个地区存在于两个或多个不相邻的部分。格思里声称,对于这样的地图,永远不会超过四种颜色,这样就不会有两个相邻的区域是相同的颜色。

目前,四色问题是用图来表示的,而不是用图中的着色区域来表示,而是用图中的一个着色顶点来表示。四色定理的所有证明都证明了一个最小反例是不存在的。(最小反例是一个最小的平面图,它的顶点需要四种以上的颜色。)只有三角剖分的平面图需要考虑,因为任何非三角剖分的图都可以通过插入边来转换成三角剖分的图。如果得到的三角剖分是四色的,那么原始图形也是四色的。能够将自己的审查限制在三角测量中是非常有用的。

把地图转换成图形;地区成为顶点。

对证据的早期尝试
在那些提供证明的人中,阿尔弗雷德·布雷·肯普,一位英国律师和业余数学家,是他的名声最坏的人,他的努力失败了。1879年,他宣布了他的成功,他的“证据”发表在了美国数学杂志.然而,11年后,另一位英国数学家珀西·希伍德绘制了一幅地图,他用4种颜色绘制了最终区域,坎普的方法在最终区域失败了。尽管失败了,肯普留下了一个有用的工具——肯普链条。它是一个极大的、连通的子图(每个顶点都可以通过一条沿边的路径从其他任何顶点到达),其中所有顶点都使用两种颜色。肯普链已经证明在给图着色和重新着色方面是有用的。参见图1。

这将是一个惊人的简化
如果伯克霍夫钻石是四色性的关键。

最后证明
第一个有效的证据是由肯尼斯·阿佩尔和沃尔夫冈·哈肯在1976年宣布的。它需要一千多个小时的计算机时间来验证他们的论点的特定方面。这种依赖于计算机代码(可能包含人为导致的错误)而不是“人为”证明的概念,并没有让数学社区的大部分人满意。阿佩尔和哈肯的证明在整体结构上是优雅的,但细节是丑陋的。

1996年,由罗伯逊、桑德斯、西摩和托马斯四名数学家组成的团队完善了这个证明,但他们仍然依靠计算机代码来完成证明。2010年,Steinberger提供了另一种变体。然而,对于为什么四色定理是正确的,仍然没有一个完全令人满意的答案。(这个猜想一经证明,就获得了“定理”的地位。)

阿尔弗雷德·布雷·肯普,英国律师
和业余数学家。

寻找另一种证明
四色问题是如此的容易表达和理解,以至于它吸引了成千上万的业余数学家的兴趣,他们都相信他们可以找到一个简单的经典证明,从而出名。吉姆·蒂利(Jim Tilley)的父亲,一位物理学家,1978-1984年间担任加拿大皇家军事学院(Royal Military College)校长,就是这样一个梦想家。每当他感到有了突破,他就叫儿子吉姆检查他的工作。吉姆总能找到缺点。然而,尽管他最初怀疑父亲的努力不会有结果,但他对四色问题产生了热情,并开始深入研究它。

Kempe-locking
吉姆·蒂利的研究使他发现了一个新的性质,四色定理的最小反例必须证明这个性质。他把它命名为“肯珀锁”。他意识到,这很可能与最小反例必须展示的另一个性质不相容,即一个图是如何连通的(一个图在分崩离析之前必须移除多少个顶点)。

蒂利的肯珀锁定是三角剖分中与边相关的属性。这个概念从删除一条边开始xy相邻顶点xy.如果对于每一个4色的结果图,其中的颜色xy是一样的,在肯普链上没有颜色互换的序列导致的颜色x使不同于…的颜色y,则原三角剖分称为相对于边的Kempe-lockedxy.Tilley证明了四色定理的最小反例必须是关于它的每条边的Kempe-locked;最小反例中的每条边都必须具有这种着色特性。

Kempe-locking是一个特别严格的条件,当三角剖分变得更大时,这个条件就会变得更难满足。蒂利开始研究是否有什么共同的三角法,有肯珀锁定边。他最早对肯珀-锁定的研究让他找到了伯克霍夫钻石。

图2。端点顶点的伯克霍夫菱形配置xy
图3。两个平面图,一个是6个顶点上的4连通三角剖分,一个是17个顶点上的5连通三角剖分。

比尔科夫钻石
1913年,g.d. Birkhoff发现地图上10个国家的某种配置(由6个国家组成的边界圈,由4个国家组成)有一个重要的属性。如果该配置存在于地图中,并且移除该配置的子地图是4色的,那么整个地图将是4色的。因此,最小反例不能包含那个特定的配置。它被称为伯克霍夫钻石。蒂利发现了肯珀锁住的边缘xy似乎只有当xy也是伯克霍夫钻石图形版本的端点。参见图2。

这个猜想很容易陈述,可以理解,也很有趣,并且为为什么所有的平面图都是四色的提供了一个令人信服的解释。

由于没有遇到任何没有Birkhoff钻石的Kempe-locking配置,他推测Birkhoff钻石是唯一的“基本的”Kempe-locking配置,它不包含较小的Kempe-locking配置作为子图。然而,蒂利发现他无法证明他的批判性猜想。令人沮丧的是,如果这个猜想是真的,它将直接证明四色定理。(要成为最小反例,三角剖分必须包含Birkhoff菱形子图,但如果包含,就不可能是最小反例。)

压倒性的支持理由
蒂利没有去证明他的猜想,而是做了另一件最好的事。他决定扮演一个实验主义者的角色,建立一个压倒性的案例来支持他的猜想。他将所有相关的平面三角划分为两类:一类是至少需要移除四个顶点才能使图形分解(4连通),另一类是至少需要移除五个顶点才能使图形分解(5连通)。参见图3。对Tilley的广泛搜索有帮助的是,他必须只检查每个同构类(结构相同的图)中的一个成员。Tilley研究了多达15个顶点上的所有8044个4-连通平面三角形的同构类和多达24个顶点上的所有9733个5-连通平面三角形的同构类。他只发现了三个坎佩锁定的三角测量。每条被发现的肯佩锁边都有一颗伯克霍夫钻石,而且每条都是四连三角剖分。5连通三角组中没有。

肯尼斯·阿佩尔和沃尔夫冈·哈肯。

Tilley通过检查16个顶点上的所有30,926个同构类和17个顶点上的所有158,428个同构类,扩展了他在4-连通三角形中的搜索。计算时间的限制意味着他将搜索限制在10万个随机生成的非同构三角的样本中,每个样本对应于18、19和20个顶点上的类。扩展后的搜索结果是另外45个坎佩-锁定三角形,但结果与最初的搜索完全相同:三角形中的每条坎佩-锁定边都有一个相关的伯克霍夫钻石。

从这里在哪里?
蒂利的广泛搜索很容易就证实了伯克霍夫钻石是坎佩-锁定的基本构型。他彻底验证了自己的猜想,但尚未得到证实。如果(或当)Tilley的猜想被证明是正确的,也就是说,只有Birkhoff钻石是四色性的关键,这将是一个惊人的简化问题:一个单一的配置可以解释它的一切——数学上的优雅。

证明四色猜想需要许多杰出的数学家的努力。蒂利关于伯克霍夫钻石是唯一的坎佩-锁定结构的猜想可能更难证明。然而,实验证据是强有力的。理论家可能会说,“为什么要麻烦呢?”蒂利的回答是,永不满足的好奇心会胜出:“毕竟,这个猜想很容易陈述、理解,也很有趣,并且为为什么所有的平面图都是四色的提供了一个令人信服的解释。”

个人反应

最初是什么激发了你对四色问题的热情,并促使你如此深入地研究它?

这是我父亲在退休后对这个问题的困扰,他希望利用我来征求他的意见。

您在这一领域的未来研究计划是什么?

我最近回顾了一篇复杂的论文,涉及到一个完全不同的四色问题的方法。就这篇论文而言,我认为它有缺陷。然而,它有希望。我可能会想和你合作。

本文是在研究团队的批准下创建的。这是一个合作制作,由那些特色的支持,免费援助,全球分发。

想读更多这样的文章吗?

注册到我们的邮件列表,阅读对你最重要的话题。
报名!

留下一个回复

您的电子邮件地址将不会被公布。必填字段已标记

感谢您表示有兴趣加入我们的邮寄名单和社区。下面您可以选择您希望我们与您互动的方式,我们将随时为您更新我们的最新内容。

您可以更改您的偏好或取消订阅,请点击任何您收到的电子邮件页脚的取消订阅链接,或通过以下方式与我们联系audience@www.graceymay.com在任何时候,如果您对我们如何处理您的数据有任何问题,请查看我们的隐私协议。

您想了解更多关于我们的服务吗?

我们使用MailChimp作为我们的营销自动化平台。通过点击下面提交此表格,您确认您提供的信息将被转移到MailChimp进行处理隐私政策条款。

订阅我们的免费刊物