MathLabs

解法:用彩虹树证明林格尔猜想(2020年)

第 8/8 步:闭合逻辑:林格尔猜想对大 nn 成立
通俗地说

定理2.1确立之后,第2步中最初的想法——科齐格的循环旋转技巧——只需一步就完成了整个证明:取那个有保证存在的 TT 的彩虹副本,把它绕圆周上的 2n+12n+1 个位置旋转,得到的 2n+12n+1 个旋转副本会自动恰好用尽 K2n+1K_{2n+1} 的每条边一次。这个关于树与完全图的古老而优雅的猜想,最终通过把纯组合的染色技巧与为保证那一个关键彩虹副本必然存在而构建的沉重现代机器(随机嵌入与吸收)结合起来而得以解决。

K2n+1 decomposes into 2n+1 edge-disjoint copies of any tree T with n edgesK_{2n+1} \text{ decomposes into } 2n+1 \text{ edge-disjoint copies of any tree } T \text{ with } n \text{ edges}
详细分析

把定理2.1(第7步)与科齐格的循环旋转观察(第2步)结合起来:对足够大的 nn,ND染色的 K2n+1K_{2n+1} 含有任意给定的 nn 条边树 TT 的彩虹副本 T^\hat{T},其 2n+12n+1 个循环旋转副本 T^0,…,T^2n\hat{T}_0,\ldots,\hat{T}_{2n} 两两边不相交(因为旋转只会把边映射到同色的其他边,而 T^\hat{T} 每种颜色只用一次),并共同覆盖了 K2n+1K_{2n+1} 的全部 n(2n+1)n(2n+1) 条边。这就证明了定理1.2:对每个足够大的 nn,K2n+1K_{2n+1} 都能分解成 TT 的 2n+12n+1 个副本,从而证实了林格尔1963年的猜想;同一论证也同时证明了科齐格关于ND染色中彩虹副本的相关猜想,并给出了完全图分解为任意度数、跨越全图规模子图的第一个结果,摆脱了此前所有方法都受限的度数有界限制。

本步骤用到的知识