A Caltech Library Service

On subsets of the hypercube with prescribed Hamming distances

Huang, Hao and Klurman, Oleksiy and Pohoata, Cosmin (2020) On subsets of the hypercube with prescribed Hamming distances. Journal of Combinatorial Theory. Series A, 171 . Art. No. 105156. ISSN 0097-3165.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


A celebrated theorem of Kleitman in extremal combinatorics states that a collection of binary vectors in {0,1}^n with diameter d has cardinality at most that of a Hamming ball of radius d/2. In this paper, we give an algebraic proof of Kleitman's Theorem, by carefully choosing a pseudo-adjacency matrix for certain Hamming graphs, and applying the Cvetković bound on independence numbers. This method also allows us to prove several extensions and generalizations of Kleitman's Theorem to other allowed distance sets, in particular blocks of consecutive integers of width much smaller than n. We also improve on a theorem of Alon about subsets of F^n_p whose difference set does not intersect {0,1}^n nontrivially.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2019 Elsevier Inc. Received 12 January 2019, Revised 9 July 2019, Accepted 29 September 2019, Available online 11 October 2019. Research supported in part by the Collaboration Grants from the Simons Foundation, grant no. 417222.
Funding AgencyGrant Number
Simons Foundation417222
Subject Keywords:Kleitman; Pseudo-adjacency matrices; Croot-Lev-Pach Lemma; Intersective sets
Record Number:CaltechAUTHORS:20191011-120012411
Persistent URL:
Official Citation:Hao Huang, Oleksiy Klurman, Cosmin Pohoata, On subsets of the hypercube with prescribed Hamming distances, Journal of Combinatorial Theory, Series A, Volume 171, 2020, 105156, ISSN 0097-3165, (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99242
Deposited By: Tony Diaz
Deposited On:11 Oct 2019 19:28
Last Modified:11 Oct 2019 19:28

Repository Staff Only: item control page