AI在线 AI在线

移除引理

陶哲轩亲测点赞o3-mini：专家级证明，我收到了一个完美的答案

陶哲轩亲测点赞o3-mini：专家级证明，我收到了一个完美的答案
刚刚，陶哲轩亲测了一下o3-mini，然后他给出了这样的结论：重建图论中一个标准（专家级）结果的证明，o3-mini是完全可以hold住的。 图片陶哲轩要重建的这个证明，叫做三角形移除引理（triangle removal lemma），由Ruzsa和Szemeredi于1978年提出，是极值图论中的重要结果:对于任意的η＞0，都存在c0，使得对于任意一个足够大的有n个顶点的图，如果该图中最多包含cn3个三角形，那么可以通过移除最多ηn2条边，使这个图变为无三角形的图。 用另一种表述方式就是，如果一个有n个顶点的图包含o(n3)个三角形，那么可以通过移除o(n2)条边来删除所有的三角形。
3/11/2025 12:07:10 PM
  • 1