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}$.
