Disproves the uniform witness conjecture via explicit construction of larger families than the bound binom(n-1,d) for d≥4 and ceil((d+2)/2)≤s≤d-1.
Largest $3$-uniform set systems with VC-dimension $2$
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
We determine the largest size of $3$-uniform set systems on $[n]$ with VC-dimension $2$ for all $n$.
fields
math.CO 3years
2026 3representative citing papers
New explicit constructions yield (d+1)-uniform VC-d families larger than the Ahlswede-Khachatrian size for d≥3, disproving the Mubayi-Zhao conjecture.
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.
citing papers explorer
-
A disproof of the uniform witness conjecture
Disproves the uniform witness conjecture via explicit construction of larger families than the bound binom(n-1,d) for d≥4 and ceil((d+2)/2)≤s≤d-1.
-
Beating the Ahlswede--Khachatrian bound for the Erd\H{o}s--Frankl--Pach problem
New explicit constructions yield (d+1)-uniform VC-d families larger than the Ahlswede-Khachatrian size for d≥3, disproving the Mubayi-Zhao conjecture.
-
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.