Non-clashing teaching on small domains: a complete five-point census, a planar closed-neighbourhood census, and the class where a withdrawn proof fails
Abstract
For a finite concept class C over a finite domain, Kirkpatrick, Simon and Zilles and Fallat, Kirkpatrick, Simon, Soltani and Zilles ask whether NCTD(C)>VCD(C) is possible; the only search they report is over "those classes for which PBTD>VCD is known from the literature". We report an exhaustive computation over all 4 294 967 295 concept classes on a five-point domain — the joint distributions of (VCD,NCTD) and of (VCD,NCTD⁺) — which finds NCTD ≤ VCD throughout, so on domains of at most five points the question is settled, by enumeration. We then show that Warmuth's class — the class both of the sources above print when they pose the question — has VC dimension 2 and no two-element fragment of frequency 1, so it is a counterexample to Lemma 2 of a preprint that claimed NCTD ≤ VCD in general and was withdrawn by its authors with the comment "The proof of Lemma 2 is wrong"; the remaining step of that argument is correct, so the whole claim rested on that lemma. For the closed neighbourhoods of a planar graph Bhore, Khazaliya and Mc Inerney prove NCTD ≤ 5 and ask whether the bound is tight: we exhibit the smallest graph on which the value 2 is attained and report an exhaustive census showing that 2 is the true maximum up to ten vertices. Around these we give a formal development, in Lean 4 against Mathlib, of the small-domain values NCTD(2^(X))=⌈ n/2⌉ for n ≤ 5 with explicit witnesses, and of the hypercube case of the degree lower bound; both are theorems of Kirkpatrick, Simon and Zilles for every n, and are recorded here as verified, not as new. The census computations are external to the formal development and are labelled as such wherever they are used.
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 1 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
9fc1c4bce721c29ae656b313f968cbb55b61730626a605241600b927be0d69ee
Claim ledger
Stated results
NV1candidate2026-09-03
Warmuth's class has VC dimension 2 and no 2-element fragment of frequency 1, so Lemma 2 of arXiv:2603.23561 (v1/v3, withdrawn) is false and its ordered compression scheme cannot make its first assignment
NV2known data2026-09-03
NCTD(C_W) <= 2 = VCD(C_W) for Warmuth's class, by an explicit order-2 non-clashing map
NV3known2026-09-03
Every concept class on a domain of at most 4 points has NCTD <= 2, by one order-2 non-clashing map for the full power set plus pairwise monotonicity; hence NCTD <= VCD whenever VCD >= 2
NV4known2026-09-03
NCTD(2^[5]) = 3 exactly, so every concept class on a 5-point domain has NCTD <= 3
NV5known2026-09-03
NCTD(2^[4]) = 2 while VCD(2^[4]) = 4
NV6candidate2026-09-03
The unique connected planar graph on 6 vertices attaining the census maximum has NCTD(N[v]) = VCD(N[v]) = 2; arXiv:2602.00657's bound NCTD <= 5 is not tight at n = 6
NV7known2026-09-03
n <= 2*NCTD(2^[n]) for every n: the edges of the hypercube force half the domain into the teaching sets
NV8measurement2026-09-03
The joint (VCD, NCTD) and (VCD, NCTD+) censuses on domains of size 3, 4 and 5; NCTD <= VCD for all 4,294,967,295 concept classes on a 5-point domain
This ledger entry is reported in prose and is not bound to a Lean theorem.NV9measurement2026-09-03
Exactly 960 concept classes on a 5-point domain (4 orbits) have no frequency-1 fragment; none on <= 4 points; the smallest, and the only one of VC dimension 2, is Warmuth's class
This ledger entry is reported in prose and is not bound to a Lean theorem.NV10measurement2026-09-03
Exhaustive planar closed-neighbourhood census to n = 10 vertices: max NCTD(N[v]) = 2 and no instance of NCTD > VCD
This ledger entry is reported in prose and is not bound to a Lean theorem.NV11measurement2026-09-03
Exhaustive all-balls census to n = 8 (the concept class B(G) of Chalopin-Chepoi-Mc Inerney-Ratel): max NCTD(B(G)) = 2 and no instance of NCTD > VCD
This ledger entry is reported in prose and is not bound to a Lean theorem.NV12routine2026-09-03
A teaching map produced by a removal order is non-clashing: arXiv:2603.23561's Theorem 3 is correct given its Lemma 2, so the whole claim rests on that lemma
NV13known2026-09-03
An order-1 non-clashing map is injective on labelled single examples, so a class admitting one has at most 2n+1 concepts
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- For a finite concept class C over a domain X (a concept is a subset of X), a *teacher mapping* sends each C ∈ C to a set of examples consistent with C; since the labels are forced by C, a teaching set is just a subset T(C) ⊆ X. Kirkpatrick–Simon–Zilles (ALT 2019) and Fallat–Kirkpatrick–Simon–Soltani–Zilles (JMLR 24 (2023) 40:1–40:33) call T non-clashing when no two distinct concepts are each consistent with the other's teaching set; unfolded, that is the pairwise condition
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7