PreprintCC BY 4.0arXiv
Average pairwise Hamming distance of a subset in a hypercube
Abstract
In this note, we prove that for a subset ℱ of {0,1}n of density 1/8, its average pairwise Hamming distance is at least (n−3)/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
- Combinatorial Algorithms for Partial Inverse Min-Max Spanning Tree Problem under the Weighted Sum Hamming Distance
- The crossing number and the unit-distance crossing number of the Hamming graphs H(d,3)=K_3^{box d}, and their realizations over many coordinate fields
- Triangle-Free Sets in Exact-Distance Hamming Graphs
- Pairwise Distance-Diffusion Analysis (PDDA): A Geometric Framework for Estimating Hurst Exponents in Multivariate Long-Memory Processes
- Hypercube eigenfunctions with two strong nodal domains
BibTeX
@misc{fang2026average,
title = {{Average pairwise Hamming distance of a subset in a hypercube}},
author = {Yijia Fang and Hao Huang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40486},
eprint = {2610.40486},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40486},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Average pairwise Hamming distance of a subset in a hypercube
AU - Yijia Fang
AU - Hao Huang
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40486
UR - https://arxiv.org/abs/2610.40486
AB - In this note, we prove that for a subset ℱ of {0,1}^n of density 1/8, its average pairwise Hamming distance is at least (n−3)/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.
ER -