Average pairwise Hamming distance of a subset in a hypercube
math.CO, cs.DM, cs.IT, math.IT
Submitted: 2026-10-29
Updated: 2026-10-29
License: http://creativecommons.org/licenses/by/4.0/
The gist: In this note, we prove that for a subset F of 0,1 n of density 1 over 8, its average pairwise Hamming distance is at least n-3 over 2, with equality attained only by (n-3) -dimensional subcubes.
Terminology
Abstract
In this note, we prove that for a subset F of 0,1 n of density 1 over 8, its average pairwise Hamming distance is at least n-3 over 2, with equality attained only by (n-3) -dimensional subcubes. This answers a question of Lei Yu, and solves an important open case of a more general question posed by Ahlswede and Katona in 1977.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality