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 is-an -element-of {1, ..., 2(n)} determine subsets A of { 0, 1 }n with # A = a, which have minimal average inner Hamming distance. Recently 1. Alt hofer and T. Sillke (J. Combin. Theory Ser. B 56 (1992), 296-301) gave an exact solution of this problem for the central value a=2(n-1). Her e we present nearly optimal solutions for a = 2lambdan with 0 < lambda < 1: Asymptotically it is not possible to do better than choosing A(n ) = {(x1, ..., x(n))/SIGMA(T=1)n x(t) = right perpenducular alphan lef t perpendicular}, where lambda = -alpha log alpha - (1 - alpha) log(1 - alpha). Next we investigate the following more general problem, whic h occurs, for instance, in the construction of good write-efficient-me mories (WEMs). Given any finite set M with an arbitrary cost function d: M x M --> R, the corresponding sum type cost function d(n):M(n) x M (n) --> R is defined by d(n)((x1, ..., x(n), (y1, ..., y(n)) = SIGMA(t =1)n d(x(t), y(t)). The task is to find sets A, of a given cardinality , which minimize the average inner cost (11(# A(n))2) SIGMA(a is-an-el ement-of A(n) d(n)(a, a'). We prove that asymptotically optimal sets c an be constructed by using ''mixed typical sequences'' with at most tw o different local configurations. As a non-trivial example we look at the Hamming distance for M = {1, ..., m} with m greater-than-or-equal- to 3. (C) 1994 Academic Press, Inc.