Maximal sets of a given diameter in Hamming cubes

2025/07/14 by Bukh, Boris, Aleksandre Saatashvili, Saatashvili, Aleksandre
Computer Science · Engineering · Mathematics · #05B20 #05D05 #05D99 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Approximation and Integration #Optimization and Packing Problems

paper · pdf · doi:10.48550/arxiv.2507.10828

openalex publication_date 2025/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A subset of the Hamming cube over n-letter alphabet is said to be d-maximal if its diameter is d, and adding any point increases the diameter. Our main result shows that each d-maximal set is either of size at most (n+o(n))^d or contains a non-trivial Hamming ball. The bound of (n+o(n))^d is asymptotically tight. Additionally, we give a non-trivial lower bound on the size of any d-maximal set and show that the number of essentially different d-maximal sets is finite.

Citations

• Facets in the Vietoris--Rips complexes of hypercubes
• Improved bounds for the sunflower lemma
• Constructive Algorithms for Discrepancy Minimization

Related

• The number of maximal independent sets in the Hamming cube
• The Helly number of Hamming balls and related problems
• On subsets of the hypercube with prescribed Hamming distances
• Size sensitive packing number for Hamming cube and its consequences
• Set families: restricted distances via restricted intersections