From the Finite to the Infinite: Sharper Asymptotic Bounds on Norin's Conjecture via SAT
Markus Kirchweger, Tomáš Peitl, Bernardo Subercaseaux, Stefan Szeider
Norin(2008)推测,反足类边缘接受不同颜色的超立方Q_n的任何2边缘着色都必须包含一些反足顶点之间的单色路径。 虽然总体猜想仍然难以实现,但迄今为止在两条战线上取得了进展:有限的情况和无症状的放松。 最好的有限结果是由于Frankston和Scheinerman(2024)使用SAT求解器验证了n≤7的猜想,而最佳渐近结果是由于Dvořák(2020),他表明Q_n的每个2边缘颜色都承认长度为n的antipodal路径,最多为0.375n + o(n)颜色变化。 我们通过SAT在两条战线上都有改进。 首先,我们通过引入更紧凑和高效的SAT编码,将验证扩展到n = 8,增强了对称断裂和立方体和征服并行性。 这种新编码的多功能性使我们能够将Dvořák的渐近方法的部分重铸为SAT问题,从而将渐近上限提高到0.3125n + O(1)颜色变化。 我们的工作展示了基于SAT的方法如何不仅产生有限案例确认,而且还可以在组合猜想上产生渐近进展。
Norin (2008) conjectured that any 2-edge-coloring of the hypercube Q_n in which antipodal edges receive different colors must contain a monochromatic path between some pair of antipodal vertices. While the general conjecture remains elusive, progress thus far has been made on two fronts: finite cases and asymptotic relaxations. The best finite results are due to Frankston and Scheinerman (2024) who verified the conjecture for n ≤ 7 using SAT solvers, and the best asymptotic result is due to Dvoř...