A disproof of the uniform witness conjecture
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 $\binom{n-1}{d}$. They proved the conjecture when $s=d$, and when $s=1$ and $n$ is large. Very…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.24776
curl -X POST /api/v1/records/arxiv/2606.24776/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.24776/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'