林格尔猜想(优美分解)
已解决,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