The thin problem for uniform witnesses: W_(3,2)(8)=C(7, 3) and W_(5,3)(12)>C(11, 5)
Abstract
A family F of (d+1)-element subsets of [n] is an s-witness family if every member F carries a set B_F ⊆ F with |B_F|=s that no member of the family cuts out of F, i.e. F ∩ F' ≠ B_F for all F' ∈ F; W_(d,s)(n) denotes the largest size of such a family. Chao, Xu, Yip and Zhang conjectured W_(d,s)(n) ≤ C(n-1, d) for n ≥ 2(d+1) and 0 ≤ s ≤ d, and in June 2026 Xu disproved it for d ≥ 4 and ⌈ (d+2)/2⌉ ≤ s ≤ d-1, leaving open exactly one shape: whether W_(2s-1,s)(n)>C(n-1, 2s-1) can hold for a fixed s ≥ 2 and infinitely many n. We settle the first in-range cell of each of the first two branches of that question, and they disagree. At s=2 the inequality fails at its first in-range n: W_(3,2)(8)=35=bin73, the star being optimal. At s=3 it holds: W_(5,3)(12) ≥ 471>462=C(11, 5), exhibited by a family with no point common to all its members. The latter is in particular a counterexample to the conjecture at a parameter set the published disproof does not reach. Around these we give the first table of W_(d,s)(n) — all 48 cells with n ≤ 7, all 27 with n=8, and 36 of the 44 with n=9 — prove that the whole space C([n], d+1) is an s-witness family exactly when n+s<2(d+1), close the two edges s=0 and s=d of the table by argument at every n, bound the column s=d-1 through the fibres of the trace map, and show that the colouring certificate an exact maximum-clique solver emits can never close the next open cell W_(3,2)(9). Every statement below is machine-checked in Lean 4 except the exhaustive computations, which are named as such.
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-08-30 15:34 UTC
File fingerprint
cbdaf66148d732359e1029695413c3cf98bbd4e66ce35b0e60c1bd91682ba765
Claim ledger
Stated results
WF1known data2026-08-22
Headline: the uniform witness conjecture is false, at five parameter sets
WF2routine2026-08-22
The two soundness bridges: bitmask computation to the Finset statement, both directions
WF3known2026-08-22
The star bound binom(n-1,d) <= W_(d,s)(n) at every (n, d, s) with s <= d, by argument
WF4routine2026-08-22
Exact values of W_(d,s)(n) for every n <= 7 (48 cells), and the two patterns they show
WF5candidate2026-08-23
CANDIDATE: W_(3,2)(8) = 35, the first cell of the source's surviving problem
WF6routine2026-08-22
Negative controls, five kinds
WF7candidate2026-08-23
W_(5,3)(12) >= 471 > 462 = C(11,5): Xu's thin-problem inequality HOLDS at s = 3, its first in-range n
WF8routine2026-08-22
General thin-problem arguments: blocker-list encoding soundness, flag transitivity, the deletion recursion and its degeneracy at n = 2(d+1)
WF9routine2026-08-22
W_(5,3)(9) = 77 and W_(5,3)(10) >= 155
WF10routine2026-08-23
W_(d,s)(n) is a maximum-clique number: the flag recast
WF11routine2026-08-23
Pattern 2 as a theorem: the whole space fails once n ≥ 2(d+1)-s, hence W_(d,s)(n) < binom(n,d+1) there
WF12routine2026-08-23
Four new n = 9 cells beating the star, and the measured W_(3,2)(9) frontier
WF13routine2026-08-23
Pattern 2 as an iff: W_(d,s)(n) = binom(n,d+1) exactly when n + s < 2(d+1), by argument
WF14routine2026-08-23
W_(6,5)(9) = 33 and W_(7,7)(9) = 8: the first exact n = 9 cells below the whole space
WF15routine2026-08-23
The colouring certificate for the max-clique recast is sound, and provably too weak at W_(3,2)(9) — and at the n = 8 gate
WF16known2026-08-23
The s = d diagonal, W_(d,d)(n) = binom(n-1,d), proved at every n — including below the conjecture's range — and cashed in as 28 exact cells, 26 of them new
WF17known2026-08-23
The s = 0 row is Erdős–Ko–Rado: IsSWitnessFamily d 0 is "uniform and intersecting", so W_(d,0)(n) = binom(n-1,d) for n ≥ 2(d+1) — and the two edges of the table do not squeeze its interior
WF18routine2026-08-23
The s = d-1 fibres, exactly: a fibre of the trace map is an intersecting family of 2-sets, so at most max(n-d,3) members and n-d is attained — giving W_(d,d-1)(n) ≤ max(n-d,3)·binom(n,d-1) at every n, which first beats the trivial bound at n = d²+2d and brackets W_(2,1)(9) in [28,63]
WF19known data2026-08-23
The s = d-1 column has no binom(n-1,d) bound, the fibre route's ceiling is exactly d·binom(n-1,d), and the extremal family at (8,3,2) is not a star — arXiv:2602.17459's non-star construction, kernel-verified
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- A family F of (d+1)-element subsets of [n] is an s-witness family if every member carries a "missing trace" of size exactly s:
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7