On hypercube labellings and antipodal monochromatic paths

A labelling of the nn-dimensional hypercube HnHn is a mapping that assigns value 0 or 1 to each edge of HnHn. A labelling is antipodal if antipodal edges of HnHn get assigned different values. It has been conjectured that, if Hn,n≥2Hn,n≥2, is given a labelling that is antipodal, then there exists a pair of antipodal vertices joined by a monochromatic path. This conjecture has been verified by hand for n≤5n≤5. In this paper, we verify the conjecture in the case where the labelling is simple in the sense that no square xyztxyzt in HnHn has value 0 assigned to xy,ztxy,zt and value 1 assigned to yz,txyz,tx, even if the given labelling is not antipodal. The proof is based on a new property of (not necessarily antipodal) simple labellings of HnHn. We also exhibit a large class of simple labellings that thus satisfy the conjecture. Finally, we conjecture that, even if the given labelling is not antipodal, there is always a path joining antipodal vertices that switches labels at most once, which implies the original conjecture. We establish this new conjecture for Hn,n≤5Hn,n≤5 as well.