The ACO Seminar (2025–2026)

A subset of the Hamming cube over an 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.