Math Labs

解法:用彩虹树证明林格尔猜想(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}
详细分析

该猜想要求一个精确的边分解:nn 条边的树 TT 有 n+1n+1 个顶点,而 K2n+1K_{2n+1} 有 n(2n+1)n(2n+1) 条边,乘积 n⋅(2n+1)n \cdot (2n+1) 恰好吻合,因此分解必须使用恰好 2n+12n+1 个 TT 的拷贝,K2n+1K_{2n+1} 的每条边被覆盖一次。Montgomery、Pokrovskiy 与 Sudakov(Geom. Funct. Anal. 2021,定理 1.2)对所有充分大的 nn 证明了这一点,对 TT 的形状与最大度不加任何限制。

这一结果立于论文引言所综述的一长串部分成果之上:Ringel 猜想此前仅对特殊族已知(古典的路与星;caterpillar、至多 44 片叶子的树,以及 Joos、Kim、Kühn、Osthus 解决的度有界树),而 Ferber–Samotij 与 Adamaszek–Allen–Grosu–Hladký 对最大度 O(n/log⁡n)O(n/\log n) 的树证明了覆盖 K2n+1K_{2n+1} 几乎全部的近似版本。遗留的难点——也是猜想困难之所在——是极端情形的并集:同时稀疏、度序列任意、结构上非均匀的树。

证明并不直接分解 K2n+1K_{2n+1},而是证明一个更强且表面上无关的命题——K2n+1K_{2n+1} 按循环距离的每种边染色都含有 TT 的彩虹拷贝(下一步)——再对一切充分大的 nn 把分解作为推论导出。

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