MathLabs

林格尔猜想(优美分解)

已解决,2020年组合数学与离散数学
问题陈述

对任意正整数 nn 以及任意具有 nn 条边的树 TT,完全图 K2n+1K_{2n+1} 都可以分解为 2n+12n+1 个边互不相交且均与 TT 同构的子图。

理查德·蒙哥马利、阿列克谢·波克罗夫斯基和本尼·苏达科夫于2020年1月宣布证明(2021年发表于 Geometric and Functional Analysis),对所有充分大的 nn 确立了林格尔猜想。他们的证明结合了高度数顶点的确定性嵌入、保持统计独立性的随机嵌入以及分布式吸收技术,在 K2n+1K_{2n+1} 的自然距离边染色中找到了任意 nn 边树 TT 的彩虹副本,而该副本的 2n+12n+1 次循环移位恰好分解 K2n+1K_{2n+1}。这一突破在不解决更强的林格尔–科齐格优美树猜想的情况下,渐近地解决了林格尔猜想。

参考文献

  1. Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov (2021). A proof of Ringel's conjecture · DOI:10.1007/s00039-021-00576-2 · arXiv:2001.02665
  2. Alexander Rosa (1967). On certain valuations of the vertices of a graph