Proving Norine's Conjecture holds for n=7 via SAT solvers

2024/08/05 by Frankston, Keith, Scheinerman, Danny · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2408.02474

Abstract

We say a red/blue edge-coloring of the n-dimensional cube graph, Q_n, is antipodal if all pairs of antipodal edges have different colors. Norine conjectured that in such a coloring there must exist a pair of antipodal vertices connected by a monochromatic path. Previous work has proven this conjecture for n≤ 6. Using SAT solvers we verify that the conjecture holds for n = 7.

Cited by

• From the Finite to the Infinite: Sharper Asymptotic Bounds on Norin's Conjecture via SAT

Related

• From the Finite to the Infinite: Sharper Asymptotic Bounds on Norin's Conjecture via SAT
• A Chain-Level Borsuk--Ulam Obstruction Proof of Norine's Antipodal-Coloring Conjecture
• On the 1-switch conjecture in the Hypercube and other graphs
• Counterexamples to Thomassen's conjecture on decomposition of cubic\n graphs
• Properly colored C₄'s in edge-colored graphs