A note on Norine's antipodal-colouring conjecture (Q2185216)

A hypercube \(Q_n\) has all binary strings of length \(n\) as vertices. Two vertices are adjacent if they differ in exactly one place, that is in one bit. If two vertices differ in all \(n\) bits, then they are called antipodal vertices. Clearly every vertex of \(Q_n\) has exactly one antipodal vertex. This short note brings a result that in every 2-edge (usually not proper) coloring of \(Q_n\), there exists a pair of antipodal vertices and a shortest path \(P\) between them, such that colors on \(P\) exchange at most \((\frac{3}{8}+o(1))n\) times. This improves \(\frac{n}{2}\) that is the best known result until now. The idea of the proof is to divide \(Q_n\) into smaller cubes \(Q_3\), to analyze the situation in smaller cubes and then joining shortest paths from \(Q_3\)'s into a shortest path between antipodal vertices by limiting the number of color changes.