解法:用彩虹树证明林格尔猜想(2020年)
通俗地说
具有 条边的树有 个顶点且不含圈——是最简单的连通形状。林格尔提出的问题是:完全图 (其中 个点两两相连)是否总能被完美地切分成一棵所选树的 个副本,每条边恰好用一次?瓦莱茨基早在1882年就解决了树只是一条长路径的特殊情形;林格尔1963年的猜想断言,无论这棵树如何分叉,同样的结论都成立。
详细分析
该猜想要求一个精确的边分解: 条边的树 有 个顶点,而 有 条边,乘积 恰好吻合,因此分解必须使用恰好 个 的拷贝, 的每条边被覆盖一次。Montgomery、Pokrovskiy 与 Sudakov(Geom. Funct. Anal. 2021,定理 1.2)对所有充分大的 证明了这一点,对 的形状与最大度不加任何限制。
这一结果立于论文引言所综述的一长串部分成果之上:Ringel 猜想此前仅对特殊族已知(古典的路与星;caterpillar、至多 片叶子的树,以及 Joos、Kim、Kühn、Osthus 解决的度有界树),而 Ferber–Samotij 与 Adamaszek–Allen–Grosu–Hladký 对最大度 的树证明了覆盖 几乎全部的近似版本。遗留的难点——也是猜想困难之所在——是极端情形的并集:同时稀疏、度序列任意、结构上非均匀的树。
证明并不直接分解 ,而是证明一个更强且表面上无关的命题—— 按循环距离的每种边染色都含有 的彩虹拷贝(下一步)——再对一切充分大的 把分解作为推论导出。
- 图分解
- 把图 的边划分成若干条边不相交的子图,每个子图都与固定图 同构,使得 的每条边恰好属于一个 的副本。
- 树
- 不含圈的连通图;具有 条边的树自动拥有 个顶点。