量子杂志：新数学证明显示图的结构何时涌现

大数据文摘授权转载自zzllrr小乐

作者：Leila Sloman

译者：zzllrr小乐

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

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

如果你从 100 个点重新开始并不断添加边，则部分点和边最终将形成正则图。在某个阈值上，它们的存在变得不可避免，就像当你尝试在四个节点之间放置五条边时不可避免地会出现三角形一样。Janzer 和 Sudakov 弄清楚了这个阈值是什么，并回答了Paul Erdős（保罗·厄尔多斯，已故著名匈牙利数学家，zzllrr小乐译注） 和 Norbert Sauer 在 1975 年首次提出的问题。

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

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

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

László Pyber在 1985 年大大缩小了选择范围，当时他表明答案必须小于n log(n)  阶，这大大低于n^{8/5}。（这里值得一提的是，数学家关心的是当一个图有大量点时会发生什么。如果n真的很大——比如说，10¹⁰⁰——那么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 发现，如果你添加更多的边——比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 问题。

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

点「在看」的人都变好看了哦！