海岸线文学

手机浏览器扫描二维码访问

第六百零七章 柯克曼女生问题图论（第1页）

1850年，英格兰国教会神父柯克曼在闲暇时间提出一个数学问题：“学校有15名女生，每天3人一组出去散步。

要保证每周的7天内，任何两人都有一次同组的经历，但也只能有一次同组经历。

请问如何办到？”

，这就是柯克曼女生问题。

在现代数学家看来，这类问题最好的办法把他们看成超图——一堆三个节点或更多的节点组成的集合。

15个女生就是节点，三人同组就看成这三个节点用三条线段（图论术语会说三条边）连接成的三角形。

柯克曼女生问题实际上就是问，有没有一种三角形的排列，把这些女生节点连接起来，并且，这些三角形还不能共边。

共边意味着两个女生被同组安排了两次。

题设要求的安排意味着女生们每周都能相聚一次，而每一天都是和新朋友一起散步。

柯克曼提出这个问题之后，近200年来，无数相关问题吸引和困扰着数学家。

1973年，传奇数学家埃尔德什提出了一个类似的问题。

他问能不能构造一个超图，这个超图拥有如下两个看似矛盾的性质。

性质一，任意两个节点都恰好被一个三角形包含，就和之前的女生一样。

性质一要求了三角形要非常的密。

性质二要求三角形要以某种精确的方式铺得足够广（具体的说，就是任意拿出几个三角形，三角形占用的结点数要比三角形本身的数量至少多出三个）。

”

这有点矛盾，这些物体的布局你既要求局部上稀疏，又要求整体上稠密。

“加州理工学院的数学家康隆（DavidConlon）如是说道。

2022年1月，四位数学家通过一份长达50的论文，证明了只要节点足够多，总是可以构造这样的超图。

伯明翰大学的数学家罗（AllanLo）说：“为了得到这个结果，他们用的办法的技术性程度令人惊叹。”

康隆也说：“这是一个非常优秀的成果。”

研究团队建立了一个满足埃尔德什苛刻要求的系统方法，该系统方法从一个随机选择的三角形的开始，极其小心地设计以后续过程以满足他们的要求。

“证明里那些复杂困难的分支情况的数量是非常惊人的。”

康隆说。

他们的证明策略是从一个三角形开始，细致的构造这个超图。

举个例子，你可以试想一下我们提到的15个女生，然后两两相连做线段。

我们需要从这些线段上描出我们需要的、满足条件的一堆三角形：

第一，任意两个三角形不共边。

（满足这样条件的系统叫做施泰纳三元系）

第二，让每个三角形的子集占用足够多的节点。

数学家们对此有个通俗的类比。

现在假设我们不是在描三角形，而是在用乐高积木建造房屋。

你建造的前几个房子非常宏伟、坚固和精致。

你建好这些后，就把它们放在旁边备用。

数学家把它们称为”