Lower bounds on the minimum average distance of binary codes (Q998361)

\textit{R. Ahlswede} and \textit{G. O. H. Katona} [Discrete Math. 17, 1--22 (1977; Zbl 0368.05001)] posed the following problem: For given \(n\) and \(M\) with \(1 \leq M \leq 2^n\), determine the minimum average Hamming distance \(\beta (n,M)\) of binary codes with length \(n\) and size \(M\). In graph-theoretic terms, this is the minimum average distance between \(M\) vertices of the \(n\)-cube. A linear programming approach is here used to derive new lower bounds on \(\beta (n,M)\), leading among other things to the result that \(\lim_{n \rightarrow \infty} \beta (n,2n) = 5/2\).