Minimum average distance subsets in the hamming cube Original Research Article

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 Qk 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 point c∈Rk. We show that these “discrete balls” include all known good constructions and we provide additional evidence supporting the conjecture.