Originator: Serguei Norine (presented by Adam Jobson - REGS 2010)
Definitions: Let Qd denote the d-dimensional hypercube, the graph whose vertices are the binary d-tuples, with vertices adjacent when they differ in exactly one position. Vertices in Qd are antipodal if they differ in all d positions. Edges uv and xy are antipodal if {u,x} and {v,y} both are pairs of antipodal vertices. A 2-edge-coloring of Qd is edge-antipodal if the color of every edge differs from the color on the edge antipodal to it.
Conjecture [DN]: For d≥2, in every edge-antipodal 2-edge-coloring of Qd there is a pair of antipodal vertices connected by a monochromatic path.
Comments: The conjecture has been checked for d≤5. Feder and Subi [FS] proved that the conclusion holds for any 2-edge-coloring (not necessarily edge-antipodal) that contains no properly edge-colored 4-cycle.
In an edge-antipodal coloring, the graphs formed by the two colors are isomorphic (complement the vertices), so we only need to consider one color class. Feder and Subi [FS] noted that a counterexample for d can be extended to a counterexample for d+1 and that a counterexample for d=6 must have at least four components each containing a single edge.
References:
[DN] Matt DeVos and Serguei Norine,
Edge-antipodal colorings of cubes,
The Open Problem Garden,
http://garden.irmacs.sfu.ca/?q=op/edge_antipodal_colorings_of_cubes.
[FS] Tomas Feder and Carlos Subi,
On Simple Labellings of Hypercubes and Antipodal Monochromatic Paths,
(2009),
http://theory.stanford.edu/~tomas/antipod.ps.