{"id":"arxiv/2602.17459","url":"https://arxiv.org/abs/2602.17459","tags":["math.CO"],"score":0,"title":"Uniform Set Systems with Uniform Witnesses","domain":"math.CO","source":"arxiv","authors":["Ting-Wei Chao","Zixuan Xu","Dmitrii Zakharov"],"reviews":0,"subject":"math.CO","summary":"Frankl--Pach and Erdős conjectured that any $(d+1)$-uniform set family $\\mathcal{F}\\subseteq \\binom{[n]}{d+1}$ with VC-dimension at most $d$ has size at most $\\binom{n-1}{d}$ when $n$ is sufficiently large. Ahlswede and Khachatrian showed that the conjecture is false by giving a counterexample of size $\\binom{n-1}{d}+\\binom{n-4}{d-2}$. For a set family $\\mathcal{F}\\subseteq \\binom{[n]}{d+1}$, the condition that its VC-dimension is at most $d$ can be reformulated as follows: for any $F\\in\\mathcal{F}$, there exists a set $B_F\\subseteq F$ such that $F\\cap F'\\neq B_F$ for all $F'\\in\\mathcal{F}$.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-19","reactions":{}}