Given a set $S\subseteq \{0,1\}^d$ of the Boolean hypercube of dimension $d$, define the average distance of $S$ as $$ \bar{d}(S) = \frac{1}{\lvert S\rvert^2} \sum_{x,y\in S} d_H(x,y)\tag{1} $$ where $d_H$ denotes the Hamming distance. For any $1\leq n \leq 2^d$, define the minimum average distance as $$ \beta(d,n) = \min_{\substack{S\subseteq \{0,1\}^d\\ \lvert S\rvert = n}} \bar{d}(S)\tag{2} $$

In [1], Ahlswede and Katona asked $\beta(d,n)$ for arbitrary $n$. Ahlswede and Althöfer, in [2], provided asymptotically tight (in $d$) lower bounds on $\beta(d,n)$, when $n \geq\binom{d}{\alpha d}$ for constant $\alpha \in(0,1/2)$: $$ \liminf_{d\to\infty} \frac{\beta(d,n)}{d} \geq 2\alpha(1-\alpha)\tag{3} $$

In [3], Althofer and Sillke also showed the general bound $$ \beta(d,n) \geq \frac{1}{4}\left(d+1-\frac{2^d}{n}\right) \tag{4} $$

Besides that, there is some work showing optimal bounds for some cases of the form $n= 2^{d-1}\pm O(1)$ (see e.g. [4]), and it seems most of the more recent work is focused on those, and the structure of optimal large sets achieving these bounds.

So it looks like, for $n= 2^{d-k}$, the cases $k=\Theta(d)$ (via (3)) and $k=O(1)$ are rather well-understood; but for the general case, (4) only gives $$ \beta(d,n) \geq \frac{1}{4}\left(d+1-2^k\right) \tag{5} $$ while the other cases seem to hint at a behavior more like $\beta(d,n) \approx d-k$.

Is there anything better than (4) known for the "intermediary regime" where $n=2^{d-k}$ with $1 \ll k \ll d$ (e.g., $k = \log d$, or $k = \sqrt{d}$)?

[1] R. Ahlswede and G.O.H. Katona, “Contributions to the geometry of hamming spaces”, Discrete Mathematics, vol. 17, 1977, pp. 1-22.

[2] R. Ahlswede and I. Althöfer, “The asymptotic behavior of diameters in the average”, Journal of Combinatorial Theory, Series B, vol. 61, 1994, pp. 167-177.

[3] Ingo Althöfer, Torsten Sillke, 1992, 'An “average distance” inequality for large subsets of the cube', Journal of Combinatorial Theory, Series B, vol. 56, no. 2, pp. 296-301

[4] André Kündgen, 2002, 'Minimum average distance subsets in the hamming cube', Discrete Mathematics, vol. 249, no. 1-3, pp. 149-165


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.