Scholarlink

<p>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 <i>H</i>(2,&#xa0;<i>q</i>) 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

VC-dimension of subsets of Hamming graphs

  • 期刊论文

  • 发表日期：

    2026年5月18日

查看全文
  • Christopher Housholder,
  • Layna Mangiapanello,
  • Steven Senger

摘要

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.