AI辅助证明推翻Erdős猜想，图论经典难题被破解

ctjlewis · x · 2026-08-02

AI辅助的数学证明取得了重大突破，成功推翻了著名的Erdős退化猜想（Erdős's degeneracy conjecture）。

该猜想认为对于 $r$-退化的二部图 $H$，其极值函数满足 $ex(n;H) \ll n^{2-1/r}$。但最新的证明显示，该猜想对于所有 $r \ge 2$ 均不成立：对于每一个 $r$，都存在一个 $r$-退化的二部图 $Hr$，使得 $ex(n;Hr) \ge n^{2-1/r+\epsilonr}$（其中 $\epsilonr \sim 1/(16r^2)$）。这一结论通过在Gibbs权重和Hamming半径下，利用二项式方差与熵曲率的精确抵消推导得出。例如在 $r=3$ 时，存在 $ex(n;H) \ge n^{5/3+1/200}$。