AFTD Auto-Formalizing Theoretical Domains

月报 · 2026-10 · 2026年10月

最优图划分、量子奇偶界与数表计数问题获解

English

一分钟看本月

本月解决了离散数学中的多个公开问题。研究表明最优图割无法保证联盟稳定性;证明了线立方电路的精确奇偶界;确立了拉丁数表的计数公式;并证明了正方形不存在块面积均为两素数之积的完美分割。

  • 3 证明
  • 1 否定
  • 3 部分结果
  • 1 形式化验证
  • 5 仍未解决

研究级成果

本月故事

最优图割在群体合谋下可能失去稳定性

想象博弈参与者为网络中的顶点着色,希望与邻居顶点的颜色不同。当两端颜色不同的边带来收益时,使割边数量最大化的着色方案能够实现最大的社会福利。虽然已知某些最优着色方案并不稳定,但人们一直想知道,是否每个网络都必然存在某种能够抵御团队合谋的最优着色方案。

答案是否定的。一个包含182个顶点的网络表明,无权图割博弈可能完全不存在任何最优强均衡。

在该网络中,每一种达到最大社会福利的着色方案,都允许某个联盟联合改变颜色,从而严格提高其中每一位成员的收益。

本月全部结果

  1. 否定

    无权最大3-割博弈可能不存在任何最优强均衡

    即便追求最大化切断连接,某些网络也不存在能免受团队合谋影响的最优着色。

  2. 证明

    线立方量子校验子具有大小恰为2n + 1的奇偶表示

    一族量子电路总能使用确定且极小数量的奇偶操作来实现。

  3. 证明

    具有双三尾的拉丁数表数量由闭式公式给出

    具有特定阶梯尾部的填数网格形状数量满足精确的指数公式。

  4. 部分结果

    正方形不存在块面积为两素数乘积的完美分割

    任何整数正方形都无法被分割为互不相同但面积均为相同两素数之积的矩形。

  5. 部分结果

    大阶数完全图的野数等于下界

    在大型边着色完全网络中连接单色分支仅需可能的最少边数。

  6. 证明

    圈图十五次幂的等价覆盖数为六

    覆盖长度不为十六的倍数的大偶圈的十五次幂需要六个等价层。

  7. 部分结果

    模60余数非59的奇数阶负三邮票数已确定

    允许负面额会使几乎所有奇数阈值下的三邮票基范围缩减一个精确差值。

  8. 形式化验证

    互功率散度的次可加性在低于黄金分割共轭值时失效

    只要功率参数低于黄金分割共轭值,简单三变量马尔可夫链间共享的信息便不再满足次可加性。

仍未解决

本文由模型(gemini-3.8-flash)根据本期经 Lean 验证的结果撰写,并从英文版翻译而来。文中提到的每个定理都经过 Lean 检查;本摘要只是阅读辅助,本身未经机器检查。