Clustering of vertices in an $n$-dimensional cube

Question

Consider the vertices of an $n$-dimensional cube. The distance between two vertices is measured as the minimum number of edges between the two vertices. Now consider a subset of these vertices. If we call the total set of vertices as $T$ and the subset as $S$ then our purpose is to partition $S$ into two sets $A$ and $B$ and for both of these sets find vertices $x_A$ and $x_B$ from $T$ such that the sum total of the distance between $x_A$ and the vertices of $A$ and $x_B$ and the vertices of $B$ should be a minimum.

How to approach this question?

Given that we know the distance relation for every pair of vertex, is it possible to know the minimum distance through some simple calculation?

Answer 1

You know that a square has a diagonal of sqrt(2), a cube has a diagonal of sqrt(3), etc. i.e. an nD hypercube has a diagonal of sqrt(n).

If you further align your hypercube along this diagonal, the vertices will fall in exactly n+1 equally spaced layers: the square is vertex atop diagonal (orthogonal to the chosen axis) atop opposite vertex, the cube is vertex atop triangle atop dual triangle atop opposite vertex, etc.

Thus your asked for minimal distance simply is counting the respective layers to where the second vertex is in, when the first vertex is taken to be the top-most.

--- rk

Answer 2

Just an illustration of @RichardKlitzing's construction in 3D:

     

His $n+1 = 4$ layers are: $$ v_1 \;,\; \{v_2,v_4,v_5\} \;,\; \{v_3,v_8,v_6\} \;,\; v_7 $$