林格尔猜想(优美分解)
已解决,2020年组合数学与离散数学
问题陈述
对任意正整数 以及任意具有 条边的树 ,完全图 都可以分解为 个边互不相交且均与 同构的子图。
理查德·蒙哥马利、阿列克谢·波克罗夫斯基和本尼·苏达科夫于2020年1月宣布证明(2021年发表于 Geometric and Functional Analysis),对所有充分大的 确立了林格尔猜想。他们的证明结合了高度数顶点的确定性嵌入、保持统计独立性的随机嵌入以及分布式吸收技术,在 的自然距离边染色中找到了任意 边树 的彩虹副本,而该副本的 次循环移位恰好分解 。这一突破在不解决更强的林格尔–科齐格优美树猜想的情况下,渐近地解决了林格尔猜想。
参考文献
- Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov (2021). A proof of Ringel's conjecture · DOI:10.1007/s00039-021-00576-2 · arXiv:2001.02665
- Alexander Rosa (1967). On certain valuations of the vertices of a graph