VC-dimension of subsets of Hamming graphs

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.

• Publication year

  2025

• Venue

  Unknown venue

• Publication date

  2025-05-20

• Fields of study

  Mathematics

• Identifiers
  arXiv 2505.14641
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• VC-dimension and pseudo-random graphs

  2023influential reference
• Dot products in Fq3 and the Vapnik-Chervonenkis dimension

  2023cited by this paper
• Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs

  2020cited by this paper
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters

  2017cited by this paper
• Understanding Machine Learning - From Theory to Algorithms

  2014cited by this paper
• Pseudo-random Graphs

  2005cited by this paper
• The Probabilistic Method

  1998cited by this paper
• The vapnik-chervonenkis dimension of a random graph

  1995cited by this paper
• Eigenvalue techniques in design and graph theory

  1979cited by this paper
• Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities

  1971cited by this paper

• No citing papers are available for this paper.