数学连接点揭示了结构是如何出现的

想象一下散布在你面前的 100 个点。在连接点的随意变化中，开始在点之间画线。你可以画多少条线而不产生三角形？一个正方形？ 11角星？

这些类型的问题在数学中有着悠久的历史。在 4 月 26 日发表的一篇论文中，瑞士苏黎世联邦理工学院的Oliver Janzer和Benny Sudakov回答了这个问题的 47 年历史版本。他们考虑点和线的排列，被数学家称为图形。他们正在寻找的结构是一种特殊类型的图，称为常规图。在常规图中，每个点（或“节点”）都有相同数量的线（或“边”）与之相连。在 2 正则图中，每个节点恰好位于两条边上；它有“2 级”。在 600 正则图中，每个节点的度数为 600。

如果您从 100 个点重新开始并不断添加边，则部分点和边最终将形成规则图。在某个阈值上，它们的存在变得不可避免，就像当您尝试在四个节点之间放置五条边时不可避免地会出现三角形一样。 Janzer 和 Sudakov 弄清楚了这个阈值是什么，并回答了 Paul Erdős 和 Norbert Sauer 在 1975 年首次提出的问题。

“这个问题真正吸引我的是这个属性，它说起来非常简单，它有着非常古老的历史，并且会产生大量直接后果，”Janzer 说。

对于 1 或 2 正则图，早在 1975 年之前就已经确定了 Erdős 和 Sauer 问题的答案。那是因为这些对象非常简单。 1-正则图可以由两个节点和一条边组成，因此任何非空图都符合条件。一个 2 正则图只需要一个闭环——想想多边形的轮廓。但是 3 正则图和更高的正则图在结构上更加复杂和多样。 “感觉是，一旦你解决了 [3-regular] 案件，你将能够解决更一般的案件，”赖希曼大学和耶路撒冷希伯来大学的教授Gil Kalai说。

Erdős 和 Sauer 在他们第一次发布他们的问题时已经对 3-regular 情况有了一些想法。他们知道具有n 个节点和大约 3 n条边的图没有任何 3 正则子结构。而且他们还知道，具有超过n ^8/5条边的图内部必须具有 3 正则结构。因此，正确的阈值必须介于n阶和n ^8/5阶之间，其中“阶n ”仅表示n乘以某个常数。但这仍然留下了很多可能性。

László Pyber 在 1985 年显着缩小了选择范围，当时他表明答案必须小于n log( n ) 阶，这大大低于n ^8/5 。 （这里值得一提的是，数学家关心的是当一个图有大量点时会发生什么。如果n真的很大——比如 10 ^100——那么n ^8/5大约是n log( n ) 的 10 ⁵⁸倍。 )

不久之后，Pyber、Vojtěch Rödl 和 Endre Szemerédi构建了一个n阶 log(log( n )) 边的图，其中不包含 3 次或更高阶的常规图。因此，Erdős 和 Sauer 问题的可能答案范围从低端的n log(log( n )) 阶到高端的n log( n ) 阶。

然后这个问题停滞了将近四年，直到今年 3 月 Janzer 和 Sudakov 决定尝试这个问题。 “这是高风险、高回报的问题之一，”Janzer 说。 “如果你不解决它，你不会难过，但有时你需要尝试。”

两人首先深入研究了 Pyber、Rödl 和 Szemerédi 的论文，希望弄清楚这三个人是如何设法避免生成正则图的。在他们的图表上，一些节点连接到大量边，而其他节点只连接到少数。这些不同类型的节点紧密相连，无法提取更规则的子结构。

与 Sudakov 合作的加州大学圣地亚哥分校的数学家Jacques Verstraete说：“这种结构是一种灵感，因为它告诉你，好吧，这就是障碍所在。”

Janzer 和 Sudakov 发现，如果你添加更多的边——order n log(log( n )) 更多——以创建 Pyber、Rödl 和 Szemerédi 的图的更密集版本，整个情况都会发生变化。突然，常规图表开始弹出。该功能使两位作者能够从所有类型的图中挖掘出规则图：任何具有足够边的图都包含一个模仿这些超密集 Pyber-Rödl-Szemerédi 结构之一的图，而后者又包含一个规则图。

该结果使他们能够证明，在一个n节点图上，阶n log(log( n )) 边肯定会包含一个度数为 3 或更多的正则图。无论您要寻找 3 正则图还是 1,000,000 正则图，解决方案的顺序都是相同的，尽管后者可能需要多倍的边。 Pyber、Rödl 和 Szemerédi 很久以前的结果意味着订单不能再小了 — 最终解决了 Erdős 和 Sauer 的问题。 “值得注意的是，这不仅仅是他们所做的渐进式改进，他们还解决了这个持续了 30 多年的问题，”Verstraete 说。

Janzer 和 Sudakov 已经找到了将他们的见解应用于其他问题的方法。例如，1983 年，数学家 Carsten Thomassen发表了他自己关于图的问题。 Thomassen 想要绘制一个图并提取一个子结构，除其他要求外，该子结构在确保每个节点连接到一定数量的边的同时避免边的短循环。如果原始图有足够的边开始，则已知该练习是可能的； Janzer 和 Sudakov 已经降低了这个上限。他们还利用他们的工作为1970 年的一个问题做出了贡献，该问题早于 Erdős-Sauer 问题。

对于苏达科夫来说，这篇论文为很久以前开始的数学交响乐提供了一个尾声。 “它利用了以前从事这项工作的人的所有这些作品，”他说。 “令人惊讶的是，每个思考过这个问题的人都朝着正确的方向思考。”