The duplicate-free contradiction graph detects VC dimension at orders two and three, and at no higher order
Abstract
Campbell, Ibaibarriaga and Reyzin (arXiv:2605.20434) proved that the order-m contradiction graph Gₘ(H) of a concept class H determines whether VC(H) ≥ m: the graph contains a cube-trace clique of size 2ᵐ if and only if H shatters an m-point set. The vertices of Gₘ(H) are labeled samples of length m in which domain points may repeat, and the reverse implication uses the repeated samples ((x,0),…,(x,0)) and ((x,1),…,(x,1)); the closing discussion of that paper notes that the proof "does not automatically apply to a duplicate-free variant in which each sample must use m distinct domain points". We determine exactly when the implication survives in that variant. At m=2 it holds for every domain and every class, by a classification of the four supports and three duplicate-free witness vertices, machine-checked in Lean 4. At m=3 it holds by a computer-assisted argument: two reductions make a counterexample a partition of {0,1}ⁿ into eight subcubes of codimension three with n ≤ 7, and an exhaustive census of the 16,139 such partitions that use every coordinate, with all realizer assignments, finds none. At every order m ≥ 4 it fails: for each m ≥ 4 we exhibit a class of exactly 2ᵐ concepts on exactly m+1 points with VC dimension m-1 whose duplicate-free contradiction graph contains a cube-trace clique of size 2ᵐ — an explicit sixteen-concept class on five points at m=4, carried to every higher order by a padding argument, both machine-checked. The counterexample fails the original trace condition at precisely the repeated vertex the original proof uses, so the theorem for the repeated-sample graph is untouched. An exhaustive search over the five-point domain shows that the 640 counterexamples there are all instances of one construction, and the conjecture of the first version of this paper, that the members of a cube-trace clique share a support, is refuted already at m=2.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 2 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
a2b1e8f14a0c255d5560a58fe432addfeeb36f81a5ea39475f0166f514009cf0
Claim ledger
Stated results
DC1routine2026-09-03
Source Proposition 5.2 transferred: if VC(H) >= m then a cube-trace clique of size 2ᵐ exists in Gₘ(H) AND in the duplicate-free graph Gₘ^(!=)(H) – the clique of the 2ᵐ labelings of a shattered m-set already uses m distinct points
DC2candidate2026-09-03
The duplicate-free implication at order 2, for every domain and every class: a cube-trace clique of size 4 in G₂^(!=)(H) forces VC(H) >= 2
DC3candidate2026-09-03
The combinatorial core of DC2: four pairwise-contradicting duplicate-free 2-samples have either one common support (then it is shattered) or the three-point star pattern p,q,p,q,p,r,p,r; in the star case either p,r is shattered or three duplicate-free vertices give three two-element traces through one clique member, which no point of the square admits
DC4routine2026-09-03
Control (the hypothesis cannot be weakened): the star class 000,010,100,101 on three points has a clique of four duplicate-free vertices in G₂^(!=) while VC = 1, so G₂^(!=)(H*) has no cube-trace 4-clique at all
DC5routine2026-09-03
Control (the vertex the source's proof uses): the repeated sample ((q,0),(q,0)) is H*-realizable, hence a vertex of the source's graph G₂(H*), is not duplicate-free, and its non-neighbour trace on the clique has three elements – never a Boolean subcube
DC6routine2026-09-03
Control (non-vacuity and sharpness): the full class on two points has VC = 2 exactly, so the hypothesis of DC2 is satisfiable and its conclusion cannot be strengthened to VC >= 3
DC7routine2026-09-03
The realizer reduction: a counterexample to 'cube-trace 2ᵐ-clique in Gₘ^(!=) implies VC >= m' can always be taken with at most 2ᵐ concepts, namely the clique's own realizers, because shrinking H shrinks the vertex set and hence preserves the cube-trace condition while VC can only fall
DC8prose2026-09-03
The duplicate-free implication at order 3: for every domain X and every H, a cube-trace clique of size 8 in G₃^(!=)(H) forces VC(H) >= 3 – by the two reductions, the support bound |U| <= 7, and an exhaustive machine census of every configuration on 3 to 7 points
This ledger entry is reported in prose and is not bound to a Lean theorem.DC9measurement2026-09-03
Census (MEASUREMENT): the number of partitions of 0,1ⁿ into 2ᵐ subcubes of codimension m – 1, 9, 30, 70, 135 for m = 2, n = 2..6 (of which 1, 6, 0, 0, 0 use every coordinate) and 1, 272, 4380, 30020, 132685 for m = 3, n = 3..7 (of which 1, 268, 3030, 7800, 5040 use every coordinate) – and: not one of them, under any assignment of realizers, is a counterexample
This ledger entry is reported in prose and is not bound to a Lean theorem.DC10prose2026-09-03
Structure (PROSE): a 2ᵐ-clique of duplicate-free m-samples over an n-point domain is exactly a partition of 0,1ⁿ into 2ᵐ subcubes of codimension m; each coordinate is fixed to 0 by as many pieces as to 1, so with aₓ = |Qₓ⁰| one has sum aₓ = m*2ᵐ⁻¹, aₓ <= 2ᵐ⁻¹ and sum aₓ² >= binom(2ᵐ,2), forcing |U| <= 3 at m = 2 and |U| <= 7 at m = 3; and the repeated-sample graph is the duplicate-free one plus exactly the vertices of support size < m, so the source's condition is 'every trace at supports of size <= m is a subcube' against 'every trace at supports of size exactly m'
This ledger entry is reported in prose and is not bound to a Lean theorem.DC11candidate2026-09-07
The duplicate-free implication FAILS at order 4: the explicit class H4 of 16 concepts on the 5-point domain y₁,y₂,y₃,a,b whose duplicate-free contradiction graph G₄^(!=)(H4) contains a cube-trace clique of size 2⁴ = 16 while VC(H4) = 3 < 4 – so a cube-trace 2ᵐ-clique of duplicate-free m-samples does NOT force VC >= m at m = 4
DC12candidate2026-09-07
The general-m answer: for every m >= 4 there is a class H of exactly 2ᵐ concepts on exactly m + 1 points with VC(H) = m - 1 whose duplicate-free contradiction graph contains a cube-trace clique of size 2ᵐ – hence, with DC2 (m = 2, every domain) and DC8 (m = 3), a cube-trace 2ᵐ-clique in Gₘ^(!=)(H) forces VC(H) >= m EXACTLY for m <= 3
DC13measurement2026-09-07
Census (MEASUREMENT) at (m, n) = (4, 5): 589,185 perfect matchings of Q₅, 3,025 carrying a cube-trace realizer choice, 6,205 cube-trace (matching, realizer) pairs, 640 counterexamples and 438,360 positives; the 640 carry 640 distinct classes on exactly 80 distinct cliques, and are exactly the family K(4, c, gamma)
This ledger entry is reported in prose and is not bound to a Lean theorem.DC14prose2026-09-07
Structure (PROSE): the closed-form counterexample family K(m, c₀, gamma) on m + 1 points for every m >= 4 – colour the nodes of 0,1ᵐ⁻¹ by the two bottom points, give the realizer of an interior node a constant label at the unused bottom point – together with the threshold explanation: the construction needs two nodes of 0,1ᵐ⁻¹ with disjoint closed neighbourhoods, i.e. at Hamming distance >= 3, which exist iff m - 1 >= 3
This ledger entry is reported in prose and is not bound to a Lean theorem.DC15routine2026-09-07
Control (the intermediate conjecture is FALSE): the twin star H = 000, 011, 100, 111 on three points carries a cube-trace 4-clique of G₂^(!=)(H) whose supports are p,q and p,r – not all equal – refuting Conjecture 9.1 of this family's own v1 paper at m = 2, while VC(H) = 2 keeps DC2 intact
DC16routine2026-09-07
Control (extremality; too-large refuted): VC(H4) = 3 exactly and |H4| = 16 = 2ᵐ exactly, so the order-4 counterexample's conclusion cannot be strengthened to VC <= m - 2 and its class is as small as the realizer reduction DC7 allows; the domain has m + 1 = 5 points, the least on which two supports can differ
DC17routine2026-09-07
Control (too-small refuted; the threshold): the same construction one order down – domain y₁,y₂,a,b, colour a on 00,01,10 and b on 11 – still gives a cube-trace clique of size 8, but VC = 3, a POSITIVE instance as DC8 demands; 0,1² has no two nodes with disjoint closed neighbourhoods, so only one node is interior and the VC-lowering argument dies
DC18routine2026-09-07
Control (the source's Theorem 5.4 is untouched): the repeated vertex ((a,0),(a,0),(a,0),(a,0)) is H4-realizable, is not duplicate-free, and its non-neighbour trace on the order-4 clique has exactly 12 members – not a power of two, hence not a Boolean subcube – so the same 16 samples form a cube-trace clique of G₄^(!=)(H4) and of no CubeTraceRep H4 4
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Let X be any set and H ⊆ 0,1^X a concept class. Following Alon–Moran–Schefler–Yehudayoff (arXiv:2304.03996v4) and the founding source (arXiv:2605.20434v1, Definitions 3.2–3.3), a length-m labeled sequence is a tuple
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7