REVIEW 4 major objections 4 minor 1 cited by
Largest $3$-uniform set systems with VC-dimension $2$
T0 review · 4 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read This paper determines the largest size of a 3-uniform set system with VC-dimension at most 2 for every n: it is C(n,3) for n≤5, 13 for n=6, and C(n−1,2)+1 for n≥7.
desk verdict Resolves the d=2 Mubayi–Zhao case with a real surprise at n=6, but the base case rests on an unarchived computer search that should be verified before publication. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The proof assigns to each family member F_i a largest proper subset B_i that is never realized as an intersection with another member; these are the witnesses. Under the extremal assumption, the witnesses split into size-2 witnesses forming a simple graph B, singleton witnesses forming a set L, and empty witnesses forming a subfamily C, and Corollary 2.12 gives the accounting identity |F| = |B| + |L| + |C|. A density claim forces every element into at least n−1 triples; the argument then bounds the maximum degree of B when C is empty, and when C is nonempty controls C through its transversal number, using the link graph Z of the star center, which is shown to have matching number at most 2, maximum degree at most 3, and no K2,2 subgraph.
What would settle it
Run an independent exhaustive enumeration of all C(7,3)=35 triples on [7]: if it produces a 3-uniform family of size 17 with VC-dimension at most 2, the theorem is false; if it finds none, the computational base case is corroborated.
Extended reading notes
Core claim
The central result is an exact formula for the extremal number. For n≥7, every 3-uniform set system F ⊆ [n]^3 with VC-dimension at most 2 has at most C(n−1,2)+1 members, and this is tight by the construction from [1, 9]. For n=6 the maximum is 13, exceeding the conjectured 11; for n=3,4,5 the whole family of triples is extremal. The proof proceeds by induction on n; the n=7 base case is checked by an exhaustive backtracking search reported in the Appendix and at [13], and the induction step rules out any family with C(n−1,2)+2 members through a structural case analysis.
Load-bearing premise
The n=7 base case is verified only by a computer search, so the theorem depends on that search having no bug and enumerating all relevant families completely.
Editorial extensions
If this is right
- For n≥7, no 3-uniform set system of VC-dimension at most 2 can exceed C(n−1,2)+1, and the construction from [1, 9] attains it, closing Question 1.1 for d=2.
- At n=6 the extremal value 13 is larger than the conjectured formula, so the earlier conjectured extremal construction is not optimal for the smallest admissible n.
- For n≤5 the full set of all triples is extremal because the family is intersecting, giving the exact value C(n,3).
- Extremal systems are not unique: the paper exhibits a 16-member extremal family on [7] with transversal number 3, distinct from the [1, 9] construction.
Reading between the lines
- The three-regime pattern suggests that for general d, the extremal value at n=2d+2 may be an outlier; the paper's 4-uniform, VC-dimension-3 example on [8] of size 45, beating the previous lower bound of 39, is consistent with this picture.
- A natural testable extension is to run an analogous exhaustive search for d=3 and n=8: if the maximum exceeds the previously conjectured value, it would confirm that the exceptional behavior at the smallest allowed n persists in higher uniformity.
- The witness decomposition into B, L, and C could serve as a template for d≥3, replacing the graph B by a d-uniform witness hypergraph; whether a similar identity |F|=|B|+|L|+|C| holds under the analogous extremal assumption is a concrete open question.
- Turning the n=7 backtracking check into a formally verified proof would eliminate the only non-elementary step and make the full theorem proof-checkable.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper determines the exact maximum size of 3-uniform set systems on [n] with VC-dimension at most 2 for every n. The main result (Theorem 1.2) states that for n ≥ 7 the maximum is C(n-1,2)+1; together with the Ahlswede–Khachatrian/Mubayi–Zhao construction this resolves Question 1.1 for d=2, with small exceptional values C(n,3) for n ≤ 5 and 13 for n=6. The proof is an induction whose base case n=7 is verified by a backtracking computation, and whose inductive step is a structural analysis of witness sets of size two (B), singleton witnesses (L), and empty-witness sets (C). The paper also presents explicit extremal examples and discusses possible extensions to larger uniformity.
Significance. If the proof is completed, this is a substantial result: it fully settles the d=2 case of a well-known open problem of Mubayi and Zhao and reveals an unexpected exceptional regime at n=6. The structural framework—the B,L,C decomposition, the density condition of Claim 2.4, and the singleton-witness lemma (Lemma 2.8)—is nontrivial and potentially reusable for larger d. The authors also provide explicit constructions for n=6 and n=7 and make the computer search available at a public URL, which is good practice. My confidence is nevertheless moderated by several load-bearing gaps and internal inconsistencies in the written proof, detailed below.
major comments (4)
- [Section 2, Lemma 2.1 and Appendix] The base case n=7, on which the entire induction rests, is delegated to a backtracking computation whose implementation appears only on the external page [13]. The pseudocode in the Appendix is not accompanied by a completeness proof, a runtime analysis, a certificate, or the actual executable code; moreover, fixing the first chosen triple as F1 implicitly relies on an unstated symmetry reduction. As printed, a reader cannot verify that the search enumerates all 3-uniform families on [7] with VC-dimension at most 2 without missing a valid family or over-pruning. Since every n ≥ 7 case depends on this base case, the manuscript must supply either fully reproducible code with a machine-checkable certificate, or an independent proof of Lemma 2.1.
- [Section 2.3, Claim 2.10] In the proof of Claim 2.10, the sentence "Since F_j={x,y,w} satisfies B_j={x}, there is no other set F in F such that F∩F_j={x}. Therefore, the only set in F(z) containing x is F_i={x,y,z}" is not valid as written: the set F_l={x,z,w} lies in F(z) and satisfies F_l∩F_j={x,w}, not {x}. The displayed formula for F(z) in the next line also appears corrupted, since it includes sets such as {x,w,y} that do not contain z. This step is essential for the proof of Lemma 2.8 and hence for Corollary 2.12, so it must be corrected and proved carefully.
- [Section 2.4, Claim 2.13 and Section 2.4.1] The notation for the complement graph is inconsistent in a load-bearing way. Equation (2) is only true if N_B denotes the neighborhood in the complement graph, but later sums and inequalities (for example the bound |B|≤2n-3 and the final use in Section 2.4.1) mix the two graphs. Concretely, Claim 2.13 states (3) as |N_B(b)|≤n-3 for b not in L, but Section 2.4.1 invokes (3) to conclude |N_B(y)|≥2, which contradicts the stated inequality. As printed, the proof of |L|≤n-2 and the exclusion of Δ(B)=n-2 cannot be followed. The authors need to introduce separate symbols for the witness graph and its complement and correct the inequalities consistently.
- [Section 2.6.2, Claim 2.20(4)] In the proof that a unique 2-element transversal {a,b} of Z is impossible, the intersection list uses {z,a,b}∩{x,a,b}={a,b}, but the membership {z,a,b}∈F is never established: {a,b} is assumed only to be a transversal set of the graph Z, not necessarily an edge of Z, and {z,a,b} need not belong to C or to F from the stated assumptions. Since the contradiction relies on realizing the 2-subset {a,b} as an intersection, this is a genuine gap. The authors must either prove that {z,a,b}∈F in this situation or replace it by another argument showing that the witness of {x,a,b} cannot be of size 1 or 2.
minor comments (4)
- [Section 2, Lemma 2.3] Lemma 2.3 is quoted from the unpublished preprint [3] by overlapping authors; because it is used to justify that B is a simple graph and to control repeated witnesses, the proof should be included in an appendix or its availability should be clarified.
- [Appendix, Algorithm 1] The pseudocode should be rewritten with explicit stack semantics. In particular, the line that resets ℓ to i_{j-1} and then increments it, and the update j←j-1, are hard to verify as printed; the symmetry reduction that justifies fixing i1=1 should also be stated explicitly.
- [Section 2.5, Claim 2.16 and Section 2.6.1] There are small textual errors: "But it this case" should be "But in this case", and the notation τ(F) appears in Section 2.6.1 where τ(C) is clearly intended.
- [Section 3.2] The 4-uniform example of size 45 on [8] is presented as supporting evidence, but no verification of its VC-dimension or of the claimed lower bound is given; if it is only heuristic, this should be stated explicitly.
Circularity Check
No circularity found: the proof is an induction whose base case is an explicit computation and whose auxiliary cited lemma has assumptions independent of the target bound.
full rationale
The paper's Theorem 1.2 is proved by induction: the base case n=7 is checked by a backtracking computation (Lemma 2.1, Appendix, and external page [13]), and the inductive step Theorem 2.2 assumes the bound only for n-1 and derives it for n. The base-case computation is an external input to the derivation, not a consequence of the theorem, and no parameter is fitted and then renamed as a prediction. The lower bound is taken from Ahlswede-Khachatrian [1] and Mubayi-Zhao [9], which is standard external input. The proof does rely on Lemma 2.3, cited from the authors' own prior work [3], and this lemma is load-bearing: it is used to bound multiplicities of witness sets and, in particular, to treat the graph B of 2-element witnesses as simple. However, Lemma 2.3 is a parameter-free general statement about set systems with VC-dimension at most d and chosen witnesses; its assumptions do not include the target upper bound C(n-1,2)+1, so under the stated rules this citation is independent support rather than circularity. The main caveat in the paper is not circularity but verification completeness: the Appendix's pseudocode initializes i1=1 and claims to return the maximum over all set systems, yet as written it enumerates only families containing the first 3-set unless an unstated symmetry reduction is used, and the full implementation appears only on the external page [13]. This is a correctness or reproducibility risk for Lemma 2.1, not a circular reduction of the theorem to its own assumptions, so it does not raise the circularity score.
Assumptions & free parameters
assumptions (3)
- domain assumption Correctness and exhaustiveness of the backtracking search for n=6 and n=7
- standard math Lemma 2.3 from [3]: multiplicity bound on equal witnesses
- standard math Ahlswede-Khachatrian / Mubayi-Zhao constructions of size C(n-1,2)+1
Cite this review
Pith. "Pith review of Largest $3$-uniform set systems with VC-dimension $2$." pith.science (2026). https://pith.science/paper/AIQG2CIJ
@misc{pith2026250507756,
author = {Pith},
title = {Pith review of: Largest $3$-uniform set systems with VC-dimension $2$},
year = {2026},
howpublished = {\url{https://pith.science/paper/AIQG2CIJ}},
note = {Machine review of arXiv:2505.07756}
}
abstract
We determine the largest size of $3$-uniform set systems on $[n]$ with VC-dimension $2$ for all $n$.
Forward citations
Cited by 1 Pith paper
-
Recursive Lifting Beyond the Ahlswede--Khachatrian Construction
For every d≥3 and n≥d+3, M_d(n) ≥ binom(n-1,d)+binom(n-4,d-2)+M_{d-3}(n-5), beating the Ahlswede–Khachatrian/Mubayi–Zhao lower bound via recursive lifting.
Reference graph
Works this paper leans on
-
[3]
T.-W. Chao, Z. Xu, C. H. Yip, and S. Zhang. Uniform set systems with small VC-dimension. arXiv preprint, arXiv: 2501.13850, 2025. 22
arXiv 2025
-
[13]
J. Wang, Z. Xu, and S. Zhang. 3-uniform set systems on rns with VC- dimension 2, for small n, 2025. https://www.ibs.re.kr/ecopro/zixiangxu/2025/05/05/ 3-uniform-set-systems-on-n-for-small-n/ . Appendix In this appendix, we present the backtracking algorithm used to compute the maximum size of a 3-uniform set system on rns with VC-dimension at most 2, spec...
work page 2025
-
[7]
Frankl and J
P. Frankl and J. Pach. On disjointly representable sets. Combinatorica, 4(1):39–45, 1984
1984
-
[1]
Ahlswede and L
R. Ahlswede and L. H. Khachatrian. Counterexample to the Frankl-Pach conjecture for uniform, dense families. Combinatorica, 17(2):299–301, 1997
1997
- [2]
-
[4]
P. Erd˝ os. On some problems in graph theory, combinatorial analysis and combinatorial number theory. In Graph theory and combinatorics (Cambridge, 1983) , pages 1–17. Academic Press, London, 1984
work page 1983
-
[5]
P. Erd˝ os and R. Rado. Intersection theorems for systems of sets.J. London Math. Soc. , 35:85–90, 1960
work page 1960
-
[6]
J. Fox, J. Pach, and A. Suk. Sunflowers in set systems of bounded dimension. Combinatorica, 43(1):187–202, 2023
work page 2023
Show all 13 references
-
[8]
G. Ge, Z. Xu, C. H. Yip, S. Zhang, and X. Zhao. The Frankl-Pach upper bound is not tight for any uniformity. arXiv preprint, arXiv: 2412.11901, 2024
2024 arXiv
-
[9]
Mubayi and Y
D. Mubayi and Y. Zhao. On the VC-dimension of uniform hypergraphs. J. Algebraic Combin., 25(1):101–110, 2007
2007
-
[10]
N. Sauer. On the density of families of sets. J. Comb. Theory, Ser. A , 13:145–147, 1972
1972
-
[11]
S. Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pac. J. Math. , 41:247–261, 1972
1972
-
[12]
V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity, pages 11–30. Springer, Cham, 2015. Reprint of Theor. Probability Appl. 16 (1971), 264–280
1971
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.