Question: Is there a pairing (a fixed point free involution) of the vertices of the $n$-dimensional cube graph, and a $2$-coloring of its edges such that the number of color changes needed to get from a vertex to its pair is on average more than $c \sqrt{n}$ for a constant $c$?

Motivation: If we chose the involution that takes every vertex to its antipodal pair, and ask for the minimal number of color changes, it is open whether it is $o(n)$, so a proof would answer a question of Leader and Long affirmatively.

Examples: You can achieve the order of magnitude of $\sqrt{n}$ by setting the involution to pair a vertex to its antipodal pair, and coloring the edges between the same levels of the cube with the same color, such that neighbouring levels get different colors. This way the minimum is one (or zero according to parity, attained at the middle level), and the average is $c \sqrt{n}$. One can do "worse" by changing the involution to send the middle layers to the top/bottom of the cube, but this will only make the minimum $c'\sqrt{n}$ and the average also $c'' \sqrt{n}$.

  • $\begingroup$ This seems to speak to colorings more than to involutions. If I color edges so that edge gets color c(i) if the vertices differ in the ith bit, then I can find a path between any two vertices with at most one color change. It might be interesting to classify colorings which are small variations on this which admit "similarly boring" paths between any two points. $\endgroup$ – The Masked Avenger Mar 6 '15 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.