TAOCP 7.1.1 Exercise 94
Let the hypercube be $Q_n = \{0,1\}^n$ with graph metric $d(\cdot,\cdot)$ equal to Hamming distance.
Exercise 94. [M21] [M21] Prove that every retract $X$ of a hypercube is a set of median labels, if we suppress coordinates that are constant for all $x \in X$.
Verified: yes
Solve time: 2m42s
Let the hypercube be $Q_n = {0,1}^n$ with graph metric $d(\cdot,\cdot)$ equal to Hamming distance. Let $X \subseteq Q_n$ be a retract, with retraction $r: Q_n \to X$, so $r(x)=x$ for $x \in X$ and $r$ is a graph homomorphism.
Step 1: Metric monotonicity of the retraction
Since $r$ is a graph homomorphism on a hypercube, it is nonexpansive in the Hamming metric:
$$ d(r(u),r(v)) \le d(u,v) \quad \text{for all } u,v \in Q_n. $$
Indeed, adjacency is preserved, so each edge is mapped to either an edge or a vertex, and shortest-path lengths cannot increase under such a map.
In particular, for $a \in X$, since $r(a)=a$,
$$ d(r(u),a) = d(r(u),r(a)) \le d(u,a). $$
Step 2: Characterization of the hypercube median by an optimization principle
For $x,y,z \in Q_n$, define
$$ S(u) = d(u,x) + d(u,y) + d(u,z). $$
We claim that the coordinatewise majority vertex
$$ m = m(x,y,z) $$
is the unique minimizer of $S(u)$ over all $u \in Q_n$.
This holds coordinatewise. For each coordinate $i$, the contribution of that coordinate to $S(u)$ depends only on $u_i$, and is minimized precisely when $u_i$ equals the majority value of $(x_i,y_i,z_i)$. Hence $m$ minimizes $S$.
Uniqueness follows because in each coordinate the minimizing choice is unique unless all three bits agree, in which case the value is forced anyway. Therefore the global minimizer is unique:
$$ S(u) \ge S(m), \quad \text{with equality only if } u=m. $$
Step 3: Apply the retraction to the median
Let $m = m(x,y,z)$, where $x,y,z \in X$. Since $m \in Q_n$, we may apply $r$ and obtain $r(m) \in X$.
Using nonexpansiveness and $r(x)=x$, $r(y)=y$, $r(z)=z$,
$$ S(r(m)) = d(r(m),x) + d(r(m),y) + d(r(m),z) \le d(m,x) + d(m,y) + d(m,z) = S(m). $$
Thus,
$$ S(r(m)) \le S(m). $$
On the other hand, since $m$ is the global minimizer of $S$ over all of $Q_n$ and $r(m) \in Q_n$,
$$ S(m) \le S(r(m)). $$
Hence
$$ S(r(m)) = S(m). $$
By uniqueness of the minimizer of $S$, it follows that
$$ r(m) = m. $$
Since $r(m) \in X$, we conclude
$$ m \in X. $$
Thus $X$ is closed under coordinatewise majority, i.e. under the median operation of the hypercube.
Step 4: Suppressing constant coordinates
Let $J \subseteq {1,\dots,n}$ be the set of coordinates that are not constant on $X$, and let $\pi: Q_n \to Q_J$ be the projection.
If a coordinate $i \notin J$, then $x_i$ is constant for all $x \in X$, so deleting it does not change any median computation on $X$. Hence for all $x,y,z \in X$,
$$ \pi(m(x,y,z)) = m(\pi(x),\pi(y),\pi(z)). $$
Therefore $\pi(X)$ is closed under coordinatewise median in ${0,1}^J$, and $\pi$ is injective on $X$. So $X$, after suppression of constant coordinates, is isomorphic to a median-closed subset of a hypercube with no fixed coordinates.
Conclusion
After deleting coordinates that are constant on $X$, the set $X$ is closed under coordinatewise majority and hence is a set of median labels in the hypercube ${0,1}^J$.