图论相关 AI 资讯 · AI 热点

8月18日

10:32

10:32

官方账号arXiv cs.LG@Bjoern Andres, Silvia Di Gregorio, Jannik Irmai, Lucas Fabian Naumann, Shengxian Zhao

这篇论文对Irmai等人（2024）提出的图多分隔符问题展开多面体研究，该问题用于图像分割，是提升多割问题的替代方案。作者从整数线性规划（ILP）公式出发，用可高效判定的图论条件刻画了ILP不等式诱导的所有面。他们进一步强化不等式，描述了若干多分隔符多面体的额外面。对于路径图且考虑所有顶点对分离的情况，得到了全对偶整数（TDI）描述。论文还证明奇数环不等式诱导的面不会从多分隔符多面体迁移到布尔二次多面体，并揭示了多分隔符多面体与提升多割多面体互为某面的投影关系。

论文多分隔符问题多面体整数规划

推荐理由：搞图分割优化的话，这篇把多分隔符问题的多面体结构讲清楚了，还给了路径情况的完整刻画，值得翻翻。

8月11日

11:13

11:13

官方一手arXiv: OpenAI@Jędrzej Hodor, Piotr Micek

一项新研究证明，若高度为h的完全二叉树同构于某图H与一条路径的强乘积的子图，则H的路径宽度pw(H)至少为Ω(h)。该结果解决了Bose、Dujmović、Javarsineh、Morin和Wood在2022年提出的开放问题。证明由OpenAI的GPT-5.6 Sol Pro模型发现，展示了AI在数学推理中的潜力。论文已发布于arXiv，编号2608.09495v1。

论文 GPT-5.6 OpenAI 图论

推荐理由：OpenAI的GPT-5.6 Sol Pro帮人解决了一个2022年的数学难题，想知道AI怎么证明图论下界？看这篇。

7月28日

10:13

10:13

官方一手arXiv: OpenAI@Radek Hušek, Robert Šámal

Szekeres-Seymour的圈双覆盖猜想近期被OpenAI宣布证明。本文研究立方图的计数版本，证明每个2-边连通3-边可着色的n顶点立方图至少有2^(n/2-1)个电路双覆盖，与猜想的下界一致。对于围长至少16的3-边连通立方图，本文给出一个更弱的指数下界。此外，该研究通过OpenAI使用的线性方程组提供了新的组合解释，并刻画了平面性。

论文 OpenAI 电路双覆盖立方图

推荐理由：这篇论文给出了一个漂亮的下界：符合条件的立方图至少有2^(n/2-1)个电路双覆盖，和图论猜想完美匹配，图论爱好者可以看看。

5月28日

11:35

11:35

官方一手arXiv: OpenAI@Matthew Fickus, John Jasper, Dustin G. Mixon

该论文证明了在复数域中，当维度d满足d²-d+1 < n < d²时，不存在d×n的等角紧框架。这一结果填补了等角紧框架理论中的一个重要间隙，称为Singer-Zauner间隙。证明方法源自OpenAI的内部模型，通过类比实数域中等角紧框架与强正则图的关系，将复数域问题转化为图论问题。该发现对信号处理、量子信息理论和编码理论有潜在影响。

论文等角紧框架 Singer-Zauner间隙图论

推荐理由：等角紧框架是信号处理和量子信息中的核心工具，这篇论文解决了长期悬而未决的间隙问题，做相关理论研究的数学家和工程师值得关注。

5月14日

01:10

01:10

官方账号arXiv cs.LG@Oleksandr Slyvka, Jan Rubeš, Rodrigo Alves, Jan Legerský

该研究提出了一种强化学习方法，用于寻找具有异常多实现数的最小刚性图。在刚性理论中，相同边长数据可对应多种几何实现，但传统穷举搜索因候选图数量爆炸和计算成本高昂而不可行。研究者利用Henneberg移动（0-和1-扩展）逐步构建图，并通过深度交叉熵方法优化实现数不变量，策略网络采用图同构网络编码器和置换等变动作头。实验表明，该方法在平面实现数上匹配已知最优解，并在球面实现数上改进了最佳已知边界，发现了新的记录图。

论文强化学习图论刚性理论

推荐理由：这项研究用强化学习解决了刚性理论中的极值搜索难题，做图论或机器人运动规划的开发者可以直接借鉴其方法。