Minimum Average Distance Subsets in the Hamming cube

In 1977, Ahlswede and Katona proposed the following isoperimetric problem: find a set S of n points in {0,1}^k whose average Hamming distance is minimal -- or equivalently find an n-vertex subgraph of the hypercube Q_k whose average distance is minimal.

We report on some recent results and conjecture that S can be chosen to be the set of all points in {0,1}^k that are distance at most r from some real-valued vector c. We show that these ``discrete balls'' include all known good constructions and we provide additional evidence supporting the conjecture.