MathLabs

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

第 1/8 步:林格尔1963年的猜想:用树填满完全图
通俗地说

具有 nn 条边的树有 n+1n+1 个顶点且不含圈——是最简单的连通形状。林格尔提出的问题是:完全图 K2n+1K_{2n+1}(其中 2n+12n+1 个点两两相连)是否总能被完美地切分成一棵所选树的 2n+12n+1 个副本,每条边恰好用一次?瓦莱茨基早在1882年就解决了树只是一条长路径的特殊情形;林格尔1963年的猜想断言,无论这棵树如何分叉,同样的结论都成立。

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}
详细分析

蒙哥马利、波克罗夫斯基与苏达科夫(2021年,引言)回顾了林格尔在1963年提出的猜想1.1:K2n+1K_{2n+1} 可以分解成具有 nn 条边的任意树的副本。这是图分解领域最古老、最著名的未解决问题之一,此前只对特殊形状的树(毛虫树、至多 44 片叶子的树、至多 3535 个顶点的树等)得到验证,或者在近似/度数有界的限制下成立(Joos-Kim-Kühn-Osthus 证明了度数有界树的情形;Ferber-Samotij 与 Adamaszek-Allen-Grosu-Hladký 证明了最大度数为 O(n/log⁡n)O(n/\log n) 的近似版本)。这篇论文的主定理去除了对树的形状或度数的一切限制:对于所有充分大的 nn,K2n+1K_{2n+1} 都能分解成具有 nn 条边的任意树 TT 的 2n+12n+1 个副本(定理1.2)。

本步骤中的术语
图分解
把图 GG 的边划分成若干条边不相交的子图,每个子图都与固定图 HH 同构,使得 GG 的每条边恰好属于一个 HH 的副本。
树
不含圈的连通图;具有 nn 条边的树自动拥有 n+1n+1 个顶点。
本步骤用到的知识