{"id":"90e8bbc5-adef-4b71-bb8e-4fda144fd415","arxiv_id":"2505.07756","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every n, the maximum size of a 3-uniform set system on [n] with VC-dimension 2 is C(n,3) for n≤5, 13 for n=6, and C(n-1,2)+1 for n≥7.","lead":"This paper finds the exact largest size of a collection of 3-element subsets of an n-element set that realizes every pattern on up to 2 positions but not on 3 positions. The answer is a simple formula for all n except one surprising exceptional case at n=6, which breaks a 2007 conjecture.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Base case n=7 rests on an unverified external backtracking computation; if the search or its enumeration is flawed, the induction has no valid starting point.","rationale":"The reader's weakest-assumption analysis identified the n=7 computational base case as the fragile point, and my reading agrees. I worked through the structure of the induction: Claim 2.4, Lemma 2.8, Corollary 2.12, and the case splits in Sections 2.4–2.6 are intricate but I did not find a specific internal inconsistency that would disprove the theorem. The apparent typos and compressed arguments in Section 2.6 (for example, the wording around Claim 2.20(4)) may need cleaning, but they do not appear to be load-bearing in the same way as the base case. The 4-uniform example in Section 3.2 is not used in the proof of Theorem 1.2, so it is not a threat to the central claim. The deciding issue is that Lemma 2.1 is essential and is verified only by computation that is not fully reproduced or certified in the manuscript. That justifies the conditional verdict; it does not change it.","tokens_in":21861,"tokens_out":18727,"duration_ms":183877,"concrete_test":"Obtain the implementation from reference [13] and run it independently. In addition, write a second, independent verifier that does not reuse the authors' code or ordering: for example, encode the 35 triples on [7] as Boolean variables with clauses forbidding any 3-set from being shattered, and use a SAT solver or a separate backtracking program to compute the maximum size and to certify that no valid family of size 17 exists. Repeat the same check for n = 6, where the claimed maximum is 13. If both independent searches return 13 and 16 respectively and terminate with a certificate, Lemma 2.1 is settled; if they disagree, or if no certificate can be produced, the base case remains unsupported and the theorem is not proven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1.2) is proved by induction: Theorem 2.2 reduces every n ≥ 8 to Lemma 2.1, the n = 7 base case. Lemma 2.1 is not proved analytically anywhere in the paper; it is delegated to a backtracking computation whose full implementation appears only on the external page [13]. The Appendix gives pseudocode, but not a completeness proof, not the actual code, and not a certificate. The pseudocode fixes the first chosen triple as F1, implicitly relying on an unstated symmetry reduction, and for n = 7 the raw search space over C(7,3) = 35 triples is enormous; no argument shows that the VC-dimension pruning in the pseudocode is sufficient to make the computation feasible or that the implementation matches the pseudocode. Since every n ≥ 7 case — and hence the claimed exact maximum for all n — depends on this computation, a bug in the search, a missed family, or an over-pruning step would invalidate the theorem even if the long induction proof is internally correct. This is the weakest point of the argument, and it is exactly the base case that cannot be checked from the manuscript alone.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":22076,"tokens_out":28556,"duration_ms":267311,"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":[{"comment":"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":"Section 2, Lemma 2.1 and Appendix"},{"comment":"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":"Section 2.3, Claim 2.10"},{"comment":"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":"Section 2.4, Claim 2.13 and Section 2.4.1"},{"comment":"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.","section":"Section 2.6.2, Claim 2.20(4)"}],"minor_comments":[{"comment":"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.","section":"Section 2, Lemma 2.3"},{"comment":"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":"Appendix, Algorithm 1"},{"comment":"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":"Section 2.5, Claim 2.16 and Section 2.6.1"},{"comment":"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.","section":"Section 3.2"}],"recommendation":"major_revision","confidential_remarks":"For the editor: I am not recommending rejection because the overall strategy is plausible and the n=6 and n=7 examples are concrete. However, the manuscript is not currently publishable: the n=7 base case depends on an external computation with no certificate, and several displayed inequalities and inferences in Sections 2.3 and 2.4 are inconsistent as printed. I would like to see a corrected version with consistent notation, a full proof or certificate for Lemma 2.1, and the gaps in Claim 2.10 and Claim 2.20(4) repaired. If the authors cannot supply an independently checkable certificate for the base case, the journal may need to consider whether a computer-assisted proof of this length without such a certificate meets its standards."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a look. The paper closes the d=2 case of the Mubayi–Zhao question: for n≥7 the maximum is C(n−1,2)+1, with n=6 exceptional at 13. That n=6 construction is genuinely new, and the anomaly is the kind of thing that makes the paper useful even if the main theorem weren't there. The proof is long but organized; the witness-set and auxiliary-graph machinery is sensible, and the case split by transversal number is natural. The structural lemmas appear internally consistent, though I did not re-check every line of the case analysis.\n\nThe load-bearing weakness is exactly what the stress-test note flags: Lemma 2.1, the n=7 base case, is delegated to a backtracking search that appears only as pseudocode plus a personal URL. There is no code, no certificate, and no proof of completeness. The pseudocode itself is plausible, but the search space over C(7,3)=35 triples is nontrivial, and the pruning is not analyzed; a bug or over-pruning would invalidate the theorem even if the induction is sound. This is not a fatal flaw—it is fixable by shipping the code and a certificate, or by a short exact argument—but as written the manuscript asks the reader to trust a computation they cannot inspect.\n\nSmaller quibbles: the 4-uniform example in Section 3.2 is asserted without verification. It is not needed for the main result, but if it is meant as evidence for the n=2d phenomenon, it should be checked or given a certificate. The self-citation to [3] is appropriate; Lemma 2.3 is an auxiliary structural result, not the target theorem.\n\nBottom line: I believe the theorem is very likely true, and the paper deserves a serious referee. The main thing to demand in revision is the computational base case: archive the implementation, include a completeness statement or certificate, and ideally an independent verification. I would cite this once the base case is solid.","headline":"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.","tokens_in":22613,"tokens_out":2231,"would_cite":true,"duration_ms":21455,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D05","05C65"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["3-uniform set systems","VC-dimension","extremal set theory","shattering","hypergraphs","transversal number","sunflower lemma","backtracking computation"],"falsifier":"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.","tokens_in":21655,"feed_emoji":"🔺","tokens_out":7270,"duration_ms":63836,"temperature":0.7,"pith_summary":"This paper solves a long-standing extremal question in the special case of triples: how large can a family of 3-element subsets of an n-element set be if no 3-element subset is shattered? The answer is now known exactly for every n: all triples when n≤5, 13 triples when n=6, and C(n−1,2)+1 triples when n≥7. The value for n≥7 matches the lower-bound construction from [1, 9], so the earlier conjecture from [9] is confirmed for d=2 despite failing at the exceptional n=6. The proof is an induction whose n=7 base case rests on a backtracking computation, with the induction step carried out by a structural decomposition of witnesses.","feed_headline":"Maximum size of 3-uniform VC-dimension-2 families found for all n","feed_subtitle":"For n≥7 the exact maximum is C(n−1,2)+1, and n=6 breaks the pattern at 13.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the lower-bound construction for n≥7 that achieves C(n−1,2)+1 and was conjectured to be optimal.","marker":"[1]"},{"why":"States the conjecture that this paper confirms for d=2 when n≥7, and contributes the generalized constructions and the extremal framework.","marker":"[9]"},{"why":"Provides Lemma 2.3, the auxiliary result bounding multiplicities of witnesses, which is the structural foundation of the proof.","marker":"[3]"},{"why":"Reports the exhaustive backtracking computation that verifies the n=7 base case and the n=6 maximum; the induction has no base without it.","marker":"[13]"}],"fun_headline_variants":["Exact maximum size for VC-dim-2 3-set systems found","VC-dimension-2 triple systems: max size settled for all n","For n≥7, max triples is C(n-1,2)+1; n=6 breaks","Largest 3-uniform VC-dim-2 families: exact for every n","Triple systems with VC-dim 2: max size formula plus n=6 oddity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact maximum size for VC-dim-2 3-set systems found","VC-dimension-2 triple systems: max size settled for all n","For n≥7, max triples is C(n-1,2)+1; n=6 breaks","Largest 3-uniform VC-dim-2 families: exact for every n","Triple systems with VC-dim 2: max size formula plus n=6 oddity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000691,"raw_usage":{"total_tokens":3008,"prompt_tokens":707,"completion_tokens":2301,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":323,"completion_tokens_details":{"reasoning_tokens":2192}},"tokens_in":323,"tokens_out":2301,"duration_ms":15187,"temperature":1.0,"reasoning_tokens":2192,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:08:49.755241+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Mubayi and Y","cited_arxiv_id":null,"evidence_quote":"States the conjecture that this paper confirms for d=2 when n≥7, and contributes the generalized constructions and the extremal framework."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Reports the exhaustive backtracking computation that verifies the n=7 base case and the n=6 maximum; the induction has no base without it."}],"review_version":1}