VC-dimension of subsets of Hamming graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913849054068736 |
|---|---|
| author | Housholder, Christopher Mangiapanello, Layna Senger, Steven |
| author_facet | Housholder, Christopher Mangiapanello, Layna Senger, Steven |
| contents | Following recent work on the VC-dimension of subsets of various pseudorandom graphs, we study the VC-dimension of Hamming graphs, which have proved somewhat resistant to the standard techniques in the literature. Our methods are elementary, and agree with or improve upon previously known results. In particular, for $H(2,q)$ we show tight bounds on the size of a subset of vertices to guarantee VC-dimension 2 or 3. We also prove an assortment of results for other parameters, with many of these being tight as well. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_14641 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | VC-dimension of subsets of Hamming graphs Housholder, Christopher Mangiapanello, Layna Senger, Steven Combinatorics 05C99, 68R10, 68T05 Following recent work on the VC-dimension of subsets of various pseudorandom graphs, we study the VC-dimension of Hamming graphs, which have proved somewhat resistant to the standard techniques in the literature. Our methods are elementary, and agree with or improve upon previously known results. In particular, for $H(2,q)$ we show tight bounds on the size of a subset of vertices to guarantee VC-dimension 2 or 3. We also prove an assortment of results for other parameters, with many of these being tight as well. |
| title | VC-dimension of subsets of Hamming graphs |
| topic | Combinatorics 05C99, 68R10, 68T05 |
| url | https://arxiv.org/abs/2505.14641 |