VC-dimension of subsets of Hamming graphs

Christopher Housholder, Layna Mangiapanello, Steven Senger · 2025

Read VC-dimension of subsets of Hamming graphs by Christopher Housholder, Layna Mangiapanello, Steven Senger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-14641.txt.

Introduction

Christopher Housholder, Layna Mangiapanello and Steven Senger study the VC-dimension of subsets of Hamming graphs, in work from 2025. VC-dimension measures how rich a pattern family a set can express, and recent work has chased it across pseudorandom graphs. Hamming graphs had resisted the standard tools, so the authors lean on elementary methods instead.

For the smallest case they give tight bounds on how large a vertex set must be to force dimension two or three. A spread of results for other parameters follows, many of them also tight. The paper fills a stubborn gap in the map of VC-dimension over graph families.

Catalog record

CREATORChristopher Housholder, Layna Mangiapanello, Steven Senger
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-14641

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

VC-dimension of subsets of Hamming graphs Christopher Housholder, Layna Mangiapanello, Steven Senger Abstract 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 ) 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. 1 Introduction The notion of Vapnik-Chervonenkis or VC-dimension, from [ 12 ] , has been used for a variety of applications, ranging from machine learning (see [ 5 ] ) to combinatorial applications (see [ 2 ] ). Recently, there has been interest in estimating the VC-dimension of subsets of the vertex sets of various graphs, as in [ 7 , 9 ] . Many of the methods in this pursuit rely on the pseudorandomness of the underlying graph. While the Hamming graph is pseudorandom, it has been less susceptible to these techniques, as shown in [ 11 ] . Building on this work, we use elementary methods to prove estimates (many tight) on the VC-dimension of subsets of Hamming graphs. For natural numbers d and q, one way to describe the Hamming graph H(d,q) is with vertices \mathbb{Z}_{q}^{d}, that is d -tuples of integers in the interval [0,q), where vertices are adjacent if they differ in exactly one coordinate. More generally, for an integer t, the Hamming graph H(d,q,t) has the same vertex set, but vertices are adjacent when they differ in exactly t coordinates. Given a collection of subsets \mathcal{F} of some ambient set X, and some fixed subset W\subseteq X, we say \mathcal{F} shatters W if for every S in the power set of W, there is a subset F_{S}\in\mathcal{F} so that F_{S}\cap W=S. That is, every possible subset of W is in the intersection of W and some member of the family \mathcal{F}. The Vapnik-Chervonenkis-dimension or VC-dimension of the pair (X,\mathcal{F}) is the size of the largest subset W\subset X that can be shattered by \mathcal{F}. We often call such a subset a shattering set . For example, if X is the plane, and \mathcal{F} is the set of lines, the VC-dimension of (X,\mathcal{F}) is 2, because for any pair of points, x,y\in\mathbb{R}^{2}, we can find lines that contain both, neither, or exactly one of x and y. However, we could never find a collection of lines that shatters any set of three points x,y,z\in\mathbb{R}^{2}, because if the three points do not lie on a line, there is no line that contains all three, and if they do lie on a line, there is no line that contains exactly two of them. One type of problem that has been around for a while, but gained more attention in recent years, is the estimation of the VC-dimension of subsets of certain graphs. Recall that the neighborhood of a vertex x , denoted n(x), is the set of vertices adjacent to x. In particular, given a graph G(V,E), where V is the set of vertices, n(V) is the set of neighborhoods of vertices, and E is the set of edges, there is much interest in determining the VC-dimension of the pair (V,n(V)). When context is clear, we refer to this as the VC-dimension of the graph G. See [ 3 , 7 , 9 , 4 ] and the references included therein for more information. In [ 1 ] , the authors show that for most choices of d and q, the VC-dimension of H(d,q) is 3. In [ 11 ] , the authors gave a suite of results about the VC-dimension of induced subgraphs of a family of graphs called pseudorandom graphs (See [ 8 , 10 ] for more on these and the techniques employed in their study.). However, they noted that while the Hamming graph is pseudorandom (see [ 6 ] and the references contained therein), it was resistant to the standard techniques, in that they yielded comparatively weak results. This was demonstrated by proving stronger results with elementary techniques. The main goal of this note is to improve upon and generalize some the initial results on Hamming graphs from [ 11 ] . The general strategy for each proof will be to show that some type of point configuration must (or respectively, must not) be present in some subset of the vertices of the appropriate Hamming graph. The following result first appeared in [ 11 ] , but only for d=2, and the proof was a longer induction argument, based on finding a more intricate point configuration, than the proof we give here. Proposition 1.1 . Given a natural number q\geq 3, and subset U of the vertices of H(2,q) of size |U|\geq 2q^{d-1}+1 , the VC-dimension of (U,n(U)) is at least 2. We now focus on the d=2 case, where we prove that Proposition 1.1 is tight in general, but that the bound can be improved if q is odd. Theorem 1.2 . Given an odd number q\geq 3, and subset U of the vertices of H(2,q) of size |U|\geq 2q , the VC-dimension of (U,n(U)) is at least 2. Moreover, this bound and the bound in Proposition 1.1 for d=2 are tight. Of course, if one has a larger subset of H(2,q), we can guarantee the maximum possible VC-dimension. We also demonstrate that this bound is tight. Theorem 1.3 . Given a natural number q\geq 4, and subset U of the vertices of H(2,q) of size |U|\geq 3q+1 , the VC-dimension of (U,n(U)) is 3. Moreover this bound is tight. We pause to note that by pigeonholing, Theorem 1.3 yields nontrivial results for higher ambient dimensions. We record these in the following corollary. Corollary 1.4 . Given natural numbers d,q\geq 4, and a subset of U of the vertices of H(d,q) of size |U|\geq 3q^{d-1}+1, then the VC-dimension of (U,n(U)) is 3. Proof. The graph H(d,q) has q^{d}-2 isomorphic copies of H(2,q), so by pigeonholing, there must be an isomorphic copy of H(2,q) with at least 3q+1 points on it, and we apply Theorem 1.3 there.∎ While we currently do not know how sharp the results about VC-dimension 2 are in higher ambient dimensions are, we have an explicit construction that shows that we at least have the correct exponent of q. Proposition 1.5 . Given an even natural number q\geq 4, there exists a subset U of the vertices of H(3,q) of size |U|=\frac{5}{4}q^{2} so that the VC-dimension of (U,n(U)) is 1. While Proposition does require q to be even, one can prove a similar result for q odd by embedding the construction above into H(d,q-1) and adding one more point with all coordinates (q-1). However, the constant drops off when d grows large, so we also give the following result, which comes from a simpler construction that has no parity constraint on q when d\geq 4 . Proposition 1.6 . Given natural numbers d,q\geq 2, there exists a subset U of the vertices of H(d,q) of

Read the complete text