今年一月份，一篇论文解开了由传奇数学家保罗·埃尔德什（Paul Erdős）提出的一道超图问题。这个问题看似只需要把连线组合成三角形，却用了近五十年才被解决。
作者｜Leila Sloman
翻译｜孟凡琼
审校｜王昱
托马斯·柯克曼（Thomas Kirkman）是19世纪时英国教会的一名牧师，同时也是一位数学家。他在1850年提出了“柯克曼的女学生问题”：假设一所学校里的15个女生在连续七天里，每天分成三人一组去散步，问怎么安排分组才能使任意两个女生不被重复分到同一组？
对于当代的数学家，这个问题可以用“超图”（hypergraph）来直观地表示。在数学中，对于普通的图，一条边只能连接两个点，而在超图中，“边”可以被看成是一个或多个点的集合。
含有7个点（v）和四条边（e）的无方向的超图（图片来源：Kilom691）
在这个问题中，15个女生可以被看作15个点，而每一个散步的三人组就是连接三个女生对应的点而组成的一个三角形。通过这样的转化，柯克曼的问题实际上也是在问：如何把这15个点连接成三角形，才能使每个点都与其他所有点相连，且保证任意两个三角形没有公共边？这是因为，如果有两个三角形有至少一条公共边，那么这条边所连接的两个女生就被重复分到了同一小组。这也意味着，每个女生每天都要和新的两个人一起散步，所以在七天后，每个人正好与其他14个女生都组成过一次小组。
用超图表示柯克曼女学生问题的其中一个解，每个图表示一天的安排，字母A-O分别表示15个学生（图片来源：Samuel Velasco/Quanta Magazine）
在柯克曼提出这个问题后的一百多年里，数学家们对这类问题产生了极大的兴趣。在1973年，传奇的匈牙利数学家保罗·埃尔德什（Paul Erdős）提出了一个类似的问题。他问是否有可能构建一个超图，使它同时满足看似不兼容的两个条件。
第一个条件是：这个超图是一个三角形稠密图（triangle-densegraph），也就是任意两个点都在且仅在一个三角形中，这与柯克曼的女学生问题类似（可以验证一下，对于上图中的任意一对点，只有一个三角形同时包含它们）。第二个条件迫使这些三角形以一种非常精确的方式分散开来（具体来说，对于超图中任意一小组三角形，它们包含的点的数量需要比三角形的数量多至少三个）。
来自美国加州理工学院（California Institute of Technology）的数学家大卫·康伦（David Conlon）表示：“这会带来一些微妙的矛盾。”因为这样的超图整体上是稠密的，但是根据条件二，它每个部分的点又不能连接地过于密集。
今年一月，四位数学家用一份长达50页的复杂论文，证明了只要有足够的点，满足这两个条件的超图就是可以构建的。他们分别是美国麻省理工大学的博士生梅塔布·索尼（Mehtaab Sawhney）和阿斯温·沙赫（Ashwin Sah）、美国哈佛大学数学科学与应用中心（CMSA）的博士后研究员迈克尔·西姆金（Michael Simkin）和来自奥地利科技学院（Institute of Science and Technology Austria）的数学家马修·关（Matthew Kwan）。
伯明翰大学的数学家阿兰·洛（Allan Lo）表示：“他们为得到这一结论经历了大量的技术性问题，这很令人惊讶。”康伦对此也表示赞同，并表示这是一份令人印象深刻的成果。
为了满足埃尔德什的刁钻要求，研究团队建立了一个系统，并从选择三角形的随机过程开始，一点点改进它。“这份证明中所包含的复杂改进的次数之多，实际上是非常惊人的。”康伦说。
研究团队的策略是用单独的三角形小心地构建出整个超图。比如，依然用15个女学生的问题作为例子，首先连接图中的每一对点。
15个点连接后的图像，共有105条线，在女学生问题中，需要用它们构造出35个独立的三角形（图片来源：Merrill Sherman/Quanta Magazine）
现在我们的目标是在这些线上勾画出满足两个条件的三角形。第一，任意两个三角形不能有公共边，满足这一要求的系统又被叫做施泰纳三元系（Steiner triple systems）；第二，保证每一个小的三角形集合都利用到足够多的点，来保证连线的分散。
为了更好地理解研究人员是如何做的，我们可以用积木来类比一下。
图片来源：pixabay
假设现在不是用线构造三角形，而是要用乐高积木拼房子。刚开始拼的几个建筑为结构进行了加固，装饰也非常精致，所以用掉了很多的积木。当完成这一步之后，把这些房子放在一边，作为你的“吸收器（absorber）”，它们的作用类似于一种结构化的储备材料。下一步，需要用剩余的积木建造房子，这一步可以随意一些。当剩余的乐高逐渐减少时，你可能会发现自己有一些用不到的零星的积木，或者发现新建的房屋结构不稳定。但是，由于之前的建筑用了过多的积木而非常牢固，你可以从这个吸收器中抽出一些积木使用，而不至于导致建筑坍塌。
我们回到需要构造三角形的施泰纳三元系中。在这个系统中，你的吸收器是一个连线的集合。你需要谨慎地选择这个集合，从而保证即使少了其中几条线，剩余的线依然可以组合成符合条件的三角形。像乐高的例子一样，你开始用吸收器之外的线勾画三角形，当你发现自己无法连成合适的三角形时，就可以使用一些吸收器集合中的线。完成这一步后再把吸收器中剩余的线连成三角形，从而完成整个图的构建。
然而，像这样的吸收法并不是一直有效。为了解决这些情况，数学家对它进行了各种改进。例如，吸收法一个非常强大的变体叫做迭代吸收，用这个方法可以将连线分成一个嵌套的集合序列，这样每个边的集合都可以看成是下一个更大的集合的吸收器。康伦表示：“在过去大约十年中，这方面已经实现了巨大的发展。”
然而，即便使用迭代吸收的方法，埃尔德什的问题依然难以解决。研究人员很快就弄清楚了其中的原因，他们表示：“还有一些困难的技术性问题，但它们同时也非常有趣。”举例来说，在其他应用迭代吸收的问题中，比如在施泰纳三元系中用三角形覆盖了一部分线之后，你可以把这一部分看成已经解决的部分然后暂时忘掉它。然而，埃尔德什的条件却限制了这样做的可能性。在这个问题中，有些难以解决的三角形组常包含来自多个吸收器的点。“对于一个在500个步骤前选择的三角形，你需要记起来当时是怎么想的。”索尼这样描述。
最终，研究团队发现如果他们谨慎地地选择三角形，就不需要一直记录每个细节了。索尼说：“更好的方法是，用合适的概率去选择相对小的合集，比如只考虑含100个三角形的合集。”
这四位数学家认为，他们所使用的方法可以拓展到更多问题上。目前，他们已经开始着手用相似的策略解决一个关于拉丁方阵的难题（拉丁方阵类似于数独游戏的简化版：在nn的方格中，填入1～n，使每行和每列没有重复的值）。“在这之外，还有几个问题最终可能要用到吸收法，”关表示说，“在数学组合学，尤其是设计理论的很多问题中，随机程序都是非常强大的工具。”比如，从上世纪60年代到如今仍然没有解决的瑞瑟-布鲁阿尔迪-施泰因猜想（Ryser-Brualdi-Steinconjecture）也是一个关于拉丁方阵的问题。
智利大学数学模型中心（University of Chile CMM）的副主任麻谷·施泰因（Maya Stein）表示：“虽然吸收法可能仍需改进才能解决这个猜想，但它也已经发展很多了，能看到这些方法如何逐步演化是一件令人非常高兴的事。”
