The Asymptotic Behavior of Diameters in the Average

In 1975 R. Ahlswede and G. Katona posed the following average distance problem (Discrete Math.17 (1977), 10): For every cardinality a ∈ {1, ..., 2n} determine subsets A of {0, 1}n with # A = a, which have minimal average inner Hamming distance. Recently I. Althöfer and T. Sillke (J. Combin. Theory Ser. B56 (1992), 296-301) gave an exact solution of this problem for the central value a = 2n − 1. Here we present nearly optimal solutions for a = 2λn with 0 < λ < 1: Asymptotically it is not possible to do better than choosing An = {(x1, ..., xn)|∑nt = 1xt = ⌊αn⌋}, where λ = −αlog α − (1 − α) log(1 − α). Next we investigate the following more general problem, which occurs, for instance, in the construction of good write-efficient-memories (WEMs). Given any finite set M with an arbitrary cost function d: M × M → R, the corresponding sum type cost function dn: Mn × Mn → R is defined by dn((x1, ..., xn, (y1, ..., yn) = ∑nt = 1d(xt, yt). The task is to find sets An, of a given cardinality, which minimize the average inner cost (1/(#An)2)∑a∈An∑a′∈Andn(a, a′). We prove that asymptotically optimal sets can be constructed by using "mixed typical sequences" with at most two different local configurations. As a non-trivial example we look at the Hamming distance for M = {1, ..., m} with m ≥ 3.