VC-dimension of subsets of Hamming graphs

Christopher Housholder; Layna Mangiapanello; Steven Senger

REVIEW 3 major objections 4 minor 12 references

VC-dimension of subsets of Hamming graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper pins down the exact subset sizes of Hamming graphs that force VC-dimension 2 or 3, and proves each threshold is tight.

desk verdict The H(2,q) threshold theorems look solid and new, but the higher-dimensional sharpness claims are broken (Proposition 1.6 is false, Lemma 4.2 fails for even q), so the advertised complete characterization does not hold as written. read the letter →

arxiv 2505.14641 v1 pith:KESER2LR submitted 2025-05-20 math.CO

Christopher Housholder , Layna Mangiapanello , Steven Senger This is my paper · ORCID

classification math.CO MSC 05C9968Q32

keywords VC-dimensionHamminggraphsneighborhoodsystemsshatteringsetstightboundspointconfigurationspigeonholeprinciplepseudorandom

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks how many vertices of a Hamming graph $H(d,q)$ a set $U$ must contain before the neighborhood system $n(U)$ can shatter a pair or a triple of points. The main answer is a pair of tight thresholds in the two-dimensional case: for $q\ge 4$, every $U\subset H(2,q)$ with $|U|\ge 3q+1$ has VC-dimension exactly 3, and a construction with $3q$ vertices shows that no smaller size guarantees this. For odd $q$, $2q$ vertices guarantee VC-dimension at least 2, with a matching counterexample. The paper also gives pigeonhole corollaries for higher dimensions and a sharp threshold for the distance-two Hamming graph $H(2,q,2)$. These thresholds matter because they are exact, elementary size conditions for a quantity that earlier pseudorandom-graph methods could only bound loosely.

What carries the argument

The load-bearing object is the 'fist': a line $L$ containing four points $x,y,z,u_3$, with $x,y,z$ each having an additional point $u_x,u_y,u_z$ on the perpendicular line through it. A fist plus one extra point $u_0$ gives all eight intersections of neighborhoods with $\{x,y,z\}$, hence a shattered triple. The matching upper bound runs through the contrapositive: Lemma 3.1 shows that a subset of $H(2,q)$ with VC-dimension 3 must have a line with four points, so any set with at most three points on every line has VC-dimension below 3. The same 'four points on a line or a rectangle' dichotomy (Lemma 4.1) is the mechanism for the higher-dimensional constructions.

What would settle it

For $q=6$, inspect the set defined by $x_d \in \{-1,0,2\} + \sum_{j=1}^{d-1} x_j$ and look for four points forming a rectangle; the congruence $\epsilon_w-\epsilon_y = 2(y_1-w_1)$ admits the nonzero solution $y_1-w_1=3$ modulo 6, so if those four points are present, the no-rectangle claim fails and the sharpness construction is invalid for even $q$.

Watch

Extended reading notes

Core claim

The paper's central claim is that in $H(2,q)$ the VC-dimension of a subset against its neighborhood system is controlled by how many points lie on a single row or column. Theorem 1.3 proves that $|U|\ge 3q+1$ forces $\mathrm{VCdim}((U,n(U)))=3$: the size condition puts four points on one line, and the resulting 'fist' configuration shatters a triple. Lemma 3.2 shows the bound is tight by building $3q$ points with exactly three points on every row and column, and Lemma 3.1 shows that no such set can shatter a triple. Theorem 1.2 proves the analogous sharp threshold $2q$ for VC-dimension at least 2 when $q$ is odd. The remaining results extend the same line-counting principle to higher dimensions by pigeonholing and to $H(2,q,2)$.

Load-bearing premise

The sharpness of the higher-dimensional threshold rests on the claim that the constructed set $U''_d(q)$ contains no rectangle; that claim depends on an arithmetic congruence modulo $q$ having only the trivial integer solution, which can fail when $q$ is even.

Editorial extensions

If this is right

For $H(2,q)$, the paper completes the size classification: VC-dimension 3 is guaranteed exactly at $3q+1$ vertices for $q\ge 4$, and VC-dimension at least 2 is guaranteed at $2q$ vertices when $q$ is odd, with tight counterexamples at $3q$ and $2q-1$.
For higher ambient dimensions, any subset of $H(d,q)$ with $q\ge 4$ and size at least $3q^{d-1}+1$ has VC-dimension 3, and the constructions give sets of size on the order of $3q^{d-1}$ with VC-dimension at most 2, showing the exponent is correct.
For the distance-two graph $H(2,q,2)$, $2q$ vertices force VC-dimension at least 2, while $2q-1$ vertices can keep VC-dimension below 2; pigeonholing then gives a nontrivial threshold in $H(d,q,2)$ for $d\ge 3$.
Because the proofs are elementary counts of points on rows and columns, the bounds hold for every subset of the Hamming graph, with no pseudorandomness or spectral assumption on the subset.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the rectangle-free construction in Lemma 4.2 can be repaired for even $q$, the likely consequence is that the $3q^{d-1}+1$ threshold in Corollary 1.4 is sharp for all $q$, fully settling the VC-dimension 3 size threshold in all dimensions.
The dichotomy behind Lemma 4.1 suggests a general heuristic: in Hamming graphs, VC-dimension 3 arises either from four collinear points or from a rectangle; one could test whether this dichotomy extends to other Cartesian product graphs built from grids.
A natural next question the paper leaves open is the exact threshold for VC-dimension 2 in $H(d,q)$ for $d\ge 3$; the constructions here show the exponent is $q^{d-1}$, but the constant may depend on the parity of $q$, mirroring the two-dimensional case.
For $H(d,q,t)$ with $t>2$, the row-pluck and column-pluck configurations used for $t=2$ may give tight thresholds for larger $t$ as well, especially when a parity obstruction like the one in Lemma 4.2 is absent.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version: the paper has two genuinely good results about VC-dimension in H(2,q), and a bunch of higher-dimensional claims that don't hold up. The good part is Theorems 1.2 and 1.3. The proofs are elementary and, as far as I can tell, correct: for odd q, 2q points force a shattered pair, and the 3q+1 threshold for VC-dimension 3 is tight via the diagonal-3-points-per-line construction. Those are real improvements over [11], and worth keeping.

The trouble starts in Section 4. Proposition 1.6 asserts that the hyperplane x_d = Σ_{j=1}^{d-1} x_j has VC-dimension 1. But that set is an independent set in H(d,q), so every neighborhood restricted to U is empty. Under the paper's own range convention, that gives VC-dimension 0, not 1. You can't fix this by reading the neighborhoods in the ambient graph, because the shattered set is inside U and the intersection with U is still empty.

Lemma 4.2 has a modular arithmetic gap. The proof concludes that if ε_w = ε_y then 2(y_1 - w_1) = 0 forces y_1 = w_1. Over Z_q that's only true for odd q. For even q, y_1 - w_1 = q/2 is a nonzero solution. The stress-test gives an explicit rectangle for q=6: (0,0,2), (0,0,5), (3,0,5), (3,0,2) all lie in U''_3(6). So the no-rectangle argument fails exactly when q is even, which is most of the parameter range. Proposition 1.7, the claimed sharpness of Corollary 1.4, depends on that lemma and is therefore unproven. There's also a typo in the statement of Proposition 1.7 – it says H(3,q) but the construction is in H(d,q).

None of this casts doubt on the H(2,q) core. The d=2 results are the main event, and they're probably right. But the abstract's promise of 'many of these being tight as well' oversells the paper, because the advertised complete characterization of VC-dimension 3 in higher dimensions rests on a false lemma.

Who should read this? Anyone interested in VC-dimension of pseudorandom or Hamming graphs. The H(2,q) theorems are a useful benchmark. But the paper needs major revision before it's publishable: fix or drop Proposition 1.6, repair Lemma 4.2 (or restrict it to odd q and state the even-q case as open), and correct the Proposition 1.7 statement. I'd send it to a referee, but with the expectation that the higher-dimensional sections need substantial rework.

Referee Report

3 major / 4 minor

Summary. The paper studies the VC-dimension of the set system induced by open neighborhood ranges on subsets of Hamming graphs H(d,q). Its main results are: (i) for H(2,q), any U with |U| ≥ 2q for odd q has VC-dimension at least 2, and any U with |U| ≥ 3q+1 for q ≥ 4 has VC-dimension 3, with matching constructions; (ii) a pigeonhole corollary transferring the H(2,q) bound to H(d,q) and giving VC-dimension 3 for |U| ≥ 3q^{d-1}; (iii) constructions intended to show sharpness of this corollary and to bound VC-dimension from above (Propositions 1.5, 1.6, 1.7); and (iv) analogous results for H(2,q,2). The H(2,q) portion is elementary and mostly sound, but the higher-dimensional sharpness construction in Proposition 1.7 has a genuine modular-arithmetic gap, and Proposition 1.6 is false under the paper's stated convention.

Significance. If corrected, the paper would provide clean, tight size thresholds for VC-dimension 2 and 3 in H(2,q), a useful pigeonhole transfer to higher dimensions, and several explicit constructions with no parameter fitting. The H(2,q) arguments and the 'fist' and 'row-pluck' lemmas are genuine contributions. However, the advertised complete characterization of VC-dimension 3 in H(d,q) depends on Proposition 1.7, whose proof is invalid for even q, and Proposition 1.6 is false as stated. These are load-bearing gaps, so the manuscript cannot be accepted in its current form, but the H(2,q) core appears salvageable in a major revision.

major comments (3)

[§4.3.2, Lemma 4.2 and Proposition 1.7] The no-rectangle proof fails for even q. From the congruence εw − εy = 2(y1 − w1) in Z_q, the proof concludes that εw = εy forces y1 = w1. For even q this is false: 2(y1 − w1) ≡ 0 mod q has the nonzero solution y1 − w1 = q/2. Concretely, for q = 6 and d = 3, the four points (0,0,2), (0,0,5), (3,0,5), (3,0,2) all lie in U''_3(6) and form an axis-parallel rectangle in the plane x2 = 0. Thus the asserted rectangle-free property is false, and Lemma 4.1 cannot be applied. This leaves Proposition 1.7, the claimed sharpness of Corollary 1.4, unproved, so the paper's advertised complete characterization of VC-dimension 3 in H(d,q) is not established.
[§4.2, Proposition 1.6] Under the convention used throughout the paper, where ranges are the intersections n(u) ∩ U for u ∈ U (see Lemma 2.2 and Lemma 5.3), the set U'_d(q) is an independent set. Every range in (U'_d(q), n(U'_d(q))) is therefore empty, so the VC-dimension is 0, not 1: no neighborhood in U contains a given vertex. Proposition 1.6 is false as stated; at most it shows the existence of a set of size q^{d-1} with VC-dimension at most 1.
[§4, Proposition 1.7 statement] Proposition 1.7 is internally inconsistent as printed: it refers to H(3,q) but uses the dimension parameter d and the size 3q^{d-1}. Moreover, the proof via Lemma 4.2 requires d ≥ 3 and q ≥ 6, whereas Proposition 1.7 claims d,q ≥ 2. These parameter ranges and the notational mismatch must be fixed, and any revised version must address the even-q counterexample described in the first major comment.

minor comments (4)

[§2.2.1, Lemma 2.2] The displayed union for U1(q) runs i = 0 to q/2, which gives q/2 + 1 translates modulo q with the term i = q/2 coinciding with i = 0; the intended construction should run i = 0 to q/2 − 1.
[§4.2, definitions] The definition of U'_d(q) says 'U'_d(q) ⊂ H(q,d)' but should say H(d,q), and the phrase 'H(q,d)' appears again in the proof of Lemma 4.2.
[§4.3.2, Lemma 4.2 final case check] The displayed checks after equation (3) contain transcription errors, such as '2 + 2 ≠ −1 = (−1) + 0εy + εw' and the expression '2εy + εw'; the intended sums are εy + εw throughout.
[§4.3.2, rectangle definition] The description of a rectangle as points 'each point adjacent to the points it was listed next to' is slightly ambiguous because adjacency in Hamming graphs means differing in exactly one coordinate; a figure or a coordinate-based definition would improve clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the main theorems are derived by explicit elementary arguments, and the only self-citation is incidental rather than load-bearing.

full rationale

The paper's derivation chain is self-contained. Proposition 1.1, Theorem 1.2, and Theorem 1.3 are proved directly via pigeonhole arguments, explicit shattering constructions, and induction on q, with all required configurations verified inside the paper. The tightness constructions in Section 3 are explicit sets whose VC-dimension is bounded by the paper's own Lemmas 3.1 and 4.1. The only overlap with prior work is the citation to [11], which shares an author with this paper; however, [11] is used for context, for the origin of Proposition 1.1, and for the style of the induction in Proposition 5.1, while the actual proofs here are written out in full and do not import any theorem as a black box. There are no fitted parameters, no quantity is predicted from data, and no uniqueness theorem is invoked. Some statements in Section 4, notably Lemma 4.2's parity-sensitive algebra and Proposition 1.6's convention for independent sets, may be mathematically questionable, but those are correctness concerns, not cases where a conclusion is equivalent to an input by construction or by self-citation.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted to data and no new physical or combinatorial entities are postulated. The proofs rely only on standard Hamming graph geometry, pigeonhole counting, and the cited upper bound on VC-dimension of H(2,q).

assumptions (5)

standard math VC-dimension and shattering are defined via intersections of ranges with the subset U.
Used throughout; the paper's own ambiguity about whether ranges come only from U or from the ambient graph affects Proposition 1.6.
standard math Pigeonhole principle for lines and rows.
Used in Propositions 1.1, 1.3, Lemma 3.3, and Section 5.
standard math In H(d,q), adjacency is Hamming distance 1, and lines parallel to basis vectors contain exactly q vertices.
This is the basic geometry of Hamming graphs, used in every proof.
domain assumption The maximum VC-dimension of H(2,q) is 3.
The paper relies on this from [1] to say Theorem 1.3 reaches the maximum possible value.
standard math Modular arithmetic in Z_q, including the non-invertibility of 2 when q is even.
Lemma 4.2 ignores this, leading to a false no-rectangle conclusion for q=6.

how reviews work

0 comments

Cite this review

Pith. "Pith review of VC-dimension of subsets of Hamming graphs." pith.science (2026). https://pith.science/paper/KESER2LR

@misc{pith2026250514641,
  author       = {Pith},
  title        = {Pith review of: VC-dimension of subsets of Hamming graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KESER2LR}},
  note         = {Machine review of arXiv:2505.14641}
}

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)$ 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.

Figures

Figures reproduced from arXiv: 2505.14641 by the authors.

**Figure 1.** The shattering set is W = {x, y}. When two vertices are adjacent, an edge is indicated with a solid line. When two vertices may not be adjacent, this is indicated with a dotted curve. In the proof of Lemma 2.1, z served as uxy. 2.2 Proof of Theorem 1.2 We now focus our attention on results where the ambient dimension is d = 2. Theorem 1.2 will follow by combining the following lemmas. 2.2.1 Tightness We prove the sh… view at source ↗

**Figure 2.** The four cases, with the shattering points filled in, and other points [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** The vertices from the shattering set W = {x, y, z} are circled. When two vertices are adjacent, an edge is indicated with a solid line. When two vertices may not be adjacent, this is indicated with a dotted curve. Note that as long as the edge relations are allowed, some vertices in the figure may be identified with one another. So, for example, x cannot be y, but it could be uyz. In the second case, call one of the… view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Each 2 × 2 × 2 subcube will either have five points (shaded) or zero (unshaded). Every layer will be a pair of copies of H(2, q) will have q/2 of these subcubes, arranged diagonally. This pattern will shift with subsequent layer, so that shaded cubes are never in line …

**Figure 5.** Figure 5: This is a two-dimensional slice of U ′′ d (12). no line with four points. To see this, we split into two cases. Assume that either the line consists of points that are constant except in the final coordinate, or one of the first d − 1 coordinates. We start with the cas…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[11]

Thang Pham, Steven Senger, Michael Tait, and Nguyen Thu-Huyen, VC- dimension and pseudo-random graphs , Discrete Applied Mathematics 365 (2025), Pages 231–246

work page 2025
[1]

Isolde Adler, Bjarke Geir Benediktsson, and Dugald Macpherson, Vap- nik–Chervonenkis dimension and density on Johnson and Hamming graphs, Discrete Applied Mathematics 312 (2022), 29–44

work page 2022
[2]

Noga Alon and Joel Spencer, The Probabilistic Method, Wiley, New York, Second edition, (2004)

work page 2004
[3]

1-3, 43–56

Martin Anthony, Graham Brightwell, and Colin Cooper, The Vapnik- Chervonenkis dimension of a random graph , Discrete Mathematics 138 (1995), no. 1-3, 43–56

work page 1995
[4]

VC-Dimension of Hyperplanes over Finite Fields

Ruben Ascoli, Livia Betti, Justin Cheigh, Alex Iosevich, Ryan Jeong, Xuyan Liu, Brian McDonald, Wyatt Milgrim, Steven J. Miller, Francisco Romero Acosta, Santiago Velazquez Iannuzzelli, VC-Dimension of Hyper- planes over Finite Fields, arXiv2307.10425

work page Pith review arXiv
[5]

Ben-David and S

S. Ben-David and S. Shalev-Shwartz, Understanding Machine Learning: From Theory to Algorithms , Cambridge University Press, (2014)

work page 2014
[6]

Brouwer, S

A. Brouwer, S. Cioab˘ a, F. Ihringer, and M.McGinnis, The smallest eigen- values of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters , Journal of Combinatorial Theory, Series B, 133, 88–121, (2018)

work page 2018
[7]

Discrete and Computational Geometry 71 (2024), no

Davey Fitzpatrick, Alex Iosevich, Brian McDonald, and Emmett Wyman, The VC-dimension and point configurations in the discrete planed. Discrete and Computational Geometry 71 (2024), no. 4, pages 1167–1177

work page 2024

Show all 12 references

[8]

Wilhelmus Hubertus Haemers, Eigenvalue techniques in design and graph theory, (1980). 21

1980
[9]

1, 113096

Alex Iosevich, Brian McDonald, and Maxwell Sun, Dot products in F3 q and the Vapnik-Chervonenkis dimension, Discrete Mathematics 346 (2023), no. 1, 113096

2023
[10]

Michael Krivelevich and Benny Sudakov, Pseudo-random graphs, More sets, graphs and numbers, Springer, 2006, pp. 199–262

2006
[12]

Chervonenkis and V

A.Ya. Chervonenkis and V. N. Vapnik, On the uniform convergence of relative frequencies of events to their probabilities , Theory of Probability and Its Applications 16 (1971). 22

1971

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [11]

Thang Pham, Steven Senger, Michael Tait, and Nguyen Thu-Huyen, VC- dimension and pseudo-random graphs , Discrete Applied Mathematics 365 (2025), Pages 231–246

work page 2025

[2] [1]

Isolde Adler, Bjarke Geir Benediktsson, and Dugald Macpherson, Vap- nik–Chervonenkis dimension and density on Johnson and Hamming graphs, Discrete Applied Mathematics 312 (2022), 29–44

work page 2022

[3] [2]

Noga Alon and Joel Spencer, The Probabilistic Method, Wiley, New York, Second edition, (2004)

work page 2004

[4] [3]

1-3, 43–56

Martin Anthony, Graham Brightwell, and Colin Cooper, The Vapnik- Chervonenkis dimension of a random graph , Discrete Mathematics 138 (1995), no. 1-3, 43–56

work page 1995

[5] [4]

VC-Dimension of Hyperplanes over Finite Fields

Ruben Ascoli, Livia Betti, Justin Cheigh, Alex Iosevich, Ryan Jeong, Xuyan Liu, Brian McDonald, Wyatt Milgrim, Steven J. Miller, Francisco Romero Acosta, Santiago Velazquez Iannuzzelli, VC-Dimension of Hyper- planes over Finite Fields, arXiv2307.10425

work page Pith review arXiv

[6] [5]

Ben-David and S

S. Ben-David and S. Shalev-Shwartz, Understanding Machine Learning: From Theory to Algorithms , Cambridge University Press, (2014)

work page 2014

[7] [6]

Brouwer, S

A. Brouwer, S. Cioab˘ a, F. Ihringer, and M.McGinnis, The smallest eigen- values of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters , Journal of Combinatorial Theory, Series B, 133, 88–121, (2018)

work page 2018

[8] [7]

Discrete and Computational Geometry 71 (2024), no

Davey Fitzpatrick, Alex Iosevich, Brian McDonald, and Emmett Wyman, The VC-dimension and point configurations in the discrete planed. Discrete and Computational Geometry 71 (2024), no. 4, pages 1167–1177

work page 2024