A disproof of the uniform witness conjecture

Abstract

The study of $(d+1)$-uniform set systems with VC-dimension at most $d$ links the Erdős--Ko--Rado theorem with VC-dimension. But already in 1997, Ahlswede and Khachatrian showed that this is not the right extension of the Erdős--Ko--Rado theorem. In 2025, Chao, Xu, Yip and Zhang proposed the uniform witness conjecture as a possible right extension: for $0\le s\le d$, if every set of a $(d+1)$-uniform family has a missing trace of the same fixed size $s$, then the family should have size at most $\left(\genfrac{}{}{0ex}{}{n-1}{d}\right)$. They proved the conjecture when $s=d$, and when $s=1$ and $n$ is large. Very recently, Chao, Xu and Zakharov proved the conjecture when $s\le \frac{d}{2}$ and $n$ is large. We fill in the missing half of the picture, although the picture is not the one suggested by the conjecture. More precisely, for $d\ge 4$ and $\lceil \frac{d+2}{2}\rceil \le s\le d-1$, we construct such a family $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{d+1}\right)$ with $|\mathcal{F}|=\left(\genfrac{}{}{0ex}{}{n-1}{d}\right)+\left(\genfrac{}{}{0ex}{}{n-2(d+1-s)-2}{2s-d-2}\right)$ for every $n\ge 2(d+1)$, thereby disproving the uniform witness conjecture.

5 pages