超图揭示了 50 年老问题的解决方案

1850 年，数学家托马斯·彭宁顿·柯克曼（ Thomas Penyngton Kirkman ）在没有履行其作为英格兰教会牧师的主要职责时，描述了他的“女学生问题”：“一所学校的 15 名年轻女士连续 7 天连续三人走出: 必须每天安排，以免两个人并排走两次。”

对于现代数学家来说，最好将这类问题想象为一个超图——一组以三个或三个以上为一组收集的节点。 15个女生是节点，每组“三并排”可以看成一个三角形，用三条线，或者说边，连接三个节点。

柯克曼的问题本质上是询问这些三角形是否存在将所有女学生相互连接的排列，但附加的限制是没有两个三角形共享一条边。边缘共享意味着两个女学生必须不止一次地一起走。这个限制意味着每个女孩每天都和两个新朋友一起散步一周，这样每一对可能的配对都恰好聚在一起一次。

15 个节点之间的所有可能连接。

这里的目标是在这些线的顶部绘制三角形，使三角形满足两个要求：首先，没有两个三角形共享一条边。 （满足此要求的系统称为施泰纳三重系统。）其次，确保每个小的三角形子集都使用足够多的节点。

研究人员这样做的方式也许最好用一个类比来理解。

假设您不是用边缘制作三角形，而是用乐高积木建造房屋。你建造的前几座建筑很奢华，有结构加固和精致的装饰。一旦你完成了这些，把它们放在一边。它们将充当“吸收器”——一种结构化的库存。

现在开始用你剩下的砖块建造建筑物，没有太多计划。当您的乐高积木供应减少时，您可能会发现自己有一些散落的积木，或者结构不健全的房屋。但是由于吸收器建筑物过于过度和加固，您可以到处拔出一些砖块并使用它们而不会招致灾难。

在施泰纳三重系统的情况下，您正在尝试创建三角形。在这种情况下，您的吸收器是精心挑选的边缘集合。如果您发现自己无法将系统的其余部分分类为三角形，则可以使用一些通向吸收器的边缘。然后，当你完成这个操作时，你将吸收器本身分解成三角形。

吸收并不总是有效。但是数学家已经对这个过程进行了修补，找到了绕过障碍的新方法。例如，一种称为迭代吸收的强大变体将边缘划分为嵌套的集合序列，因此每个集合都充当下一个最大的吸收器。

“在过去十年左右的时间里，取得了巨大的进步，”Conlon 说。 “这是一种艺术形式，但在这一点上，他们确实将其提升到了高级艺术的水平。”

即使使用迭代吸收，Erdős 的问题也很棘手。 “很快就很清楚为什么这个问题没有得到解决，”解决这个问题的四名研究人员之一Mehtaab Sawhney和Ashwin Sah说，他和 Sawhney 是麻省理工学院的研究生。 Michael Simkin ，哈佛大学数学科学与应用中心博士后；以及奥地利科学技术学院的数学家Matthew Kwan 。 “有一些非常有趣、非常困难的技术任务。”

例如，在迭代吸收的其他应用中，一旦你完成了一个集合的覆盖——无论是三角形、斯坦纳三重系统，还是其他结构的其他问题——你可以认为它已经处理并忘记它。然而，Erdős 的条件阻止了这四位数学家这样做。有问题的三角形簇很容易涉及来自多个吸收器组的节点。

“一个你在 500 步前选择的三角形，你需要以某种方式记住如何思考它，”Sawhney 说。

这四个人最终发现，如果他们仔细选择三角形，他们就可以避免跟踪每一件小事的需要。 “最好的做法是考虑任何 100 个三角形的小集合，并确保以正确的概率选择这组三角形，”Sawhney 说。

新论文的作者乐观地认为，他们的技术可以扩展到这一问题之外。他们已经将他们的策略应用于一个关于拉丁方格的问题，这就像数独谜题的简化。

关说，除此之外，还有几个问题最终可能会屈服于吸收方法。 “组合学中有很多问题，尤其是在设计理论中，随机过程是一个非常强大的工具。”其中一个问题，Ryser-Brualdi-Stein 猜想，也是关于拉丁方格的，自 1960 年代以来一直在等待解决方案。

智利大学数学建模中心副主任玛雅斯坦说，虽然吸收可能需要进一步发展才能解决这个问题，但自 30 年前成立以来，它已经走过了漫长的道路。 “看到这些方法是如何演变的，真是太棒了。”