Norine's conjecture on monochromatic antipodal paths in cube graphs
Statement
Let be the -dimensional cube graph, whose vertices are binary strings of length . For a vertex , write for the vertex obtained by complementing every bit, and call and antipodal. An antipodal edge-coloring of is a red/blue edge-coloring in which every pair of antipodal edges has different colors.
Norine's conjecture. For , any antipodal edge-coloring of contains antipodal vertices and such that and are joined by a monochromatic path.
Previous work had proved the conjecture for , and this paper verifies it for using SAT solvers. The conjecture concerns the existence of a monochromatic connection between antipodal vertices, although the path need not be geodesic.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.