On the 1 switch conjecture in the Hypercube and other graphs
Feder and Subi conjectured that for any $2$ coloring of the edges of the $n$ dimensional cube, we can find an antipodal pair of vertices connected by a path that changes color at most once. We discuss the case of random colorings, and we prove the conjecture for a wide class of colorings. Our method can be applied to a more general problem, where $Q_n$ can be replaced by any graph $G$ the notion of antipodality by a fixed automorphism \phi \in Aut(G) Thus for any $2$ coloring of $E(G) we are looking for a pair of vertices $u,v$ such that $u= \phi(v) and there is a path between them with as few color changes as possible. We solve this problem for the toroidal grid $G=C_{2a} \square c_{2b} with the automorphism that takes every vertex to its unique farthest pair. Our results point towards a more general conjecture which turns out to be supported by a previous theorem of Feder and Subi.