解法:用彩虹树证明林格尔猜想(2020年)
通俗地说
具有 条边的树有 个顶点且不含圈——是最简单的连通形状。林格尔提出的问题是:完全图 (其中 个点两两相连)是否总能被完美地切分成一棵所选树的 个副本,每条边恰好用一次?瓦莱茨基早在1882年就解决了树只是一条长路径的特殊情形;林格尔1963年的猜想断言,无论这棵树如何分叉,同样的结论都成立。
详细分析
蒙哥马利、波克罗夫斯基与苏达科夫(2021年,引言)回顾了林格尔在1963年提出的猜想1.1: 可以分解成具有 条边的任意树的副本。这是图分解领域最古老、最著名的未解决问题之一,此前只对特殊形状的树(毛虫树、至多 片叶子的树、至多 个顶点的树等)得到验证,或者在近似/度数有界的限制下成立(Joos-Kim-Kühn-Osthus 证明了度数有界树的情形;Ferber-Samotij 与 Adamaszek-Allen-Grosu-Hladký 证明了最大度数为 的近似版本)。这篇论文的主定理去除了对树的形状或度数的一切限制:对于所有充分大的 , 都能分解成具有 条边的任意树 的 个副本(定理1.2)。
- 图分解
- 把图 的边划分成若干条边不相交的子图,每个子图都与固定图 同构,使得 的每条边恰好属于一个 的副本。
- 树
- 不含圈的连通图;具有 条边的树自动拥有 个顶点。