2-colorings of edges of the cube

Q_n denotes the n-dimensional cube. For any x in Q_n, x_bar denotes the antipodal of x in Q_n.

We conjecture the following: Conj1 Let c:E_n --> {0, 1} be a coloring of the edges of Q_n. Then, there exists a pair of antipodal points x, x_bar and a path p from x to x_bar that it is either monochromatic or it changes colors exactly once.

It is easy to see that this conjecture implies an affirmative answer to the "antipodal" coloring open problem. We have verified that Conj1 holds for dimensions n=2, 3, and 4. We have also found that if the coloring is simple, that is, it does not contain squares colored 0101, then Conj1 holds (in fact, we find a monochromatic path joining a pair of antipodals).


Comments are limited to a maximum of 1000 characters.
More information about formatting options