Maximal sets of a given diameter in Hamming cubes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911055799648256 |
|---|---|
| author | Bukh, Boris Saatashvili, Aleksandre |
| author_facet | Bukh, Boris Saatashvili, Aleksandre |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_10828 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximal sets of a given diameter in Hamming cubes Bukh, Boris Saatashvili, Aleksandre Combinatorics 05D05, 05B20, 05D99 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. |
| title | Maximal sets of a given diameter in Hamming cubes |
| topic | Combinatorics 05D05, 05B20, 05D99 |
| url | https://arxiv.org/abs/2507.10828 |