A disproof of the uniform witness conjecture

Zixiang Xu · 2026

Read A disproof of the uniform witness conjecture by Zixiang Xu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24776.txt.

Introduction

Zixiang Xu disproves the uniform witness conjecture, a recent proposal in extremal combinatorics. The background is the study of uniform set families whose VC dimension stays small. In 2025, Chao, Xu, Yip, and Zhang suggested the conjecture as the right extension of the Erdős Ko Rado theorem. It says that if every set in a uniform family misses a trace of one fixed size, the family cannot exceed a stated bound.

Xu fills in the missing half of the picture, and the picture contradicts the conjecture. For dimension at least four and mid range trace sizes, he constructs families larger than the proposed bound. The construction works for every ground set size from twice the set size upward. The counterexample sizes are given by an exact formula. So the uniform witness conjecture fails exactly where it had remained open. Earlier partial results for the smallest cases still stand.

Catalog record

CREATORZixiang Xu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE13 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24776

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A disproof of the uniform witness conjecture Zixiang Xu Abstract The study of ( d + 1 ) (d+1) -uniform set systems with VC-dimension at most d 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 ≤ s ≤ d 0\leq s\leq d , if every set of a ( d + 1 ) (d+1) -uniform family has a missing trace of the same fixed size s s , then the family should have size at most ( n − 1 d ) \binom{n-1}{d} . They proved the conjecture when s = d s=d , and when s = 1 s=1 and n n is large. Very recently, Chao, Xu and Zakharov proved the conjecture when s ≤ d 2 s\leq\frac{d}{2} and n 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 ≥ 4 d\geq 4 and ⌈ d + 2 2 ⌉ ≤ s ≤ d − 1 \left\lceil\frac{d+2}{2}\right\rceil\leq s\leq d-1 , we construct such a family ℱ ⊆ ( [ n ] d + 1 ) \mathcal{F}\subseteq\binom{[n]}{d+1} with | ℱ | = ( n − 1 d ) + ( n − 2 ​ ( d + 1 − s ) − 2 2 ​ s − d − 2 ) |\mathcal{F}|=\binom{n-1}{d}+\binom{n-2(d+1-s)-2}{2s-d-2} for every n ≥ 2 ​ ( d + 1 ) n\geq 2(d+1) , thereby disproving the uniform witness conjecture. 1 Introduction A basic goal in extremal set theory is to find how large or how small a set system can be under a given combinatorial condition. One starting point is the theorem of Erdős, Ko and Rado [ 5 ] , which says that for n\geq 2k , every intersecting k -uniform family on [n] has size at most \binom{n-1}{k-1} . Moreover, when n>2k , equality holds only for a star. This theorem led to many later results on intersection conditions and their variants [ 6 , 9 , 10 , 11 , 12 , 14 ] . Here we focus on a related direction, VC-dimension. Let \mathcal{F}\subseteq 2^{X} be a set system. A set S\subseteq X is shattered by \mathcal{F} if \operatorname{Tr}_{\mathcal{F}}(S)=2^{S} , where \operatorname{Tr}_{\mathcal{F}}(S)=\{F\cap S:F\in\mathcal{F}\} . The VC-dimension of \mathcal{F} , denoted by \operatorname{VC}(\mathcal{F}) , is the largest size of a shattered set. The Sauer–Shelah theorem [ 15 , 16 , 18 ] gives exactly the maximum size of a not necessarily uniform set system with VC-dimension at most d , namely \sum_{i=0}^{d}\binom{n}{i} . The Hamming ball of radius d shows that this bound is sharp. The uniform version is much less understood. For a (d+1) -uniform family \mathcal{F}\subseteq\binom{[n]}{d+1} , the condition \operatorname{VC}(\mathcal{F})\leq d has a simple form: for every F\in\mathcal{F} , there is a proper subset B_{F}\subsetneq F such that F\cap F^{\prime}\neq B_{F} for every F^{\prime}\in\mathcal{F} . Thus every edge misses at least one trace on itself. If \mathcal{F} is intersecting, then one may take B_{F}=\emptyset for every F , so the Erdős–Ko–Rado theorem gives examples of size \binom{n-1}{d} . Because of this link, Erdős [ 4 ] and Frankl and Pach [ 7 ] conjectured in the 1980s that \binom{n-1}{d} should be the maximum size of a (d+1) -uniform family with VC-dimension at most d , when n is sufficiently large compared to d . Frankl and Pach [ 7 ] proved the general upper bound \binom{n}{d} . However, Ahlswede and Khachatrian [ 1 ] disproved the conjecture by constructing a family of size \binom{n-1}{d}+\binom{n-4}{d-2} . Mubayi and Zhao [ 13 ] later gave infinitely many non-isomorphic constructions with the same size, and conjectured that this Ahlswede–Khachatrian value is the correct answer for large n . More recently, Tran and Xu [ 17 ] , and Zhao and Ge [ 21 ] independently further improved the lower bound for d\geq 3 , thereby disproving the above conjecture of Mubayi and Zhao. The upper bound side has also seen several developments. Mubayi and Zhao [ 13 ] improved the Frankl–Pach bound by an \Omega_{d}(\log n) term when d is a prime power and n is large. Ge, Xu, Yip, Zhang and Zhao [ 8 ] proved that the Frankl–Pach bound is not tight for any d\geq 2 and n\geq 2d+2 , giving an unconditional improvement. Chao, Xu, Yip and Zhang [ 2 ] later gave a purely combinatorial proof of the stronger estimate \binom{n-1}{d}+O_{d}(n^{d-1-\frac{1}{4d-2}}) . Later, Yang and Yu [ 20 ] improved this further to \binom{n-1}{d}+O_{d}(n^{d-2}) for fixed d and large n . For d=2 , Wang, Xu and Zhang [ 19 ] determined the exact value for n\geq 7 , confirming the Ahlswede–Khachatrian value in the 3-uniform case. These results show both the strength and the difficulty of the original Erdős–Frankl–Pach problem [ 4 , 7 ] . They also show that bounded VC-dimension alone is not the right way to recover the Erdős–Ko–Rado theorem. Chao, Xu, Yip and Zhang [ 2 ] proposed a more rigid way to recover the Erdős–Ko–Rado theorem. Instead of only asking that every edge has some missing trace, they require all missing traces to have the same fixed size. Let 0\leq s\leq d . A family \mathcal{F}\subseteq\binom{[n]}{d+1} is called an s -witness family if for every F\in\mathcal{F} , there exists B_{F}\in\binom{F}{s} such that F\cap F^{\prime}\neq B_{F} for every F^{\prime}\in\mathcal{F} . We write \operatorname{W}_{d,s}(n) for the maximum size of an s -witness family in \binom{[n]}{d+1} . The case s=0 is exactly the Erdős-Ko-Rado Theorem. The star is an s -witness family for every s\leq d , since for an edge F containing the center 1 , any s -subset of F\setminus\{1\} is missing from the trace on F . This led to the following conjecture. Conjecture 1.1 (Uniform witness conjecture [ 2 ] ) . Let n\geq 2(d+1) and 0\leq s\leq d . If \mathcal{F}\subseteq\binom{[n]}{d+1} is an s -witness family, then |\mathcal{F}|\leq\binom{n-1}{d} . Chao, Xu, Yip and Zhang [ 2 ] verified Conjecture 1.1 when s=d , and also when s=1 and n is sufficiently large. In particular, their result implies the case d=2 for large n . Very recently, Chao, Xu and Zakharov [ 3 ] proved the conjecture when s\leq\frac{d}{2} and n is sufficiently large. They also constructed various non-star s -witness families of size exactly \binom{n-1}{d} for \frac{d}{2}<s\leq d-1 , showing that equality already looks quite different beyond the threshold \frac{d}{2} . Our main result shows that Conjecture 1.1 is false in general. Theorem 1.2 . Let d\geq 4 and let s be an integer with \left\lceil\frac{d+2}{2}\right\rceil\leq s\leq d-1. If n\geq 2(d+1) , then \operatorname{W}_{d,s}(n)\geq\binom{n-1}{d}+\binom{n-2(d+1-s)-2}{2s-d-2}. This covers every possible s when d is even, and every possible s except the lower boundary s=\frac{d+1}{2} when d is odd. Moreover, combining Theorem 1.2 and the results in [ 2 , 3 , 5 ] gives a rather strange picture: the conjecture is true for 0\leq s\leq\frac{d}{2} and large n , and it is also true for s=d , but the middle parameters violate the conjectured bound. 2 Proof of Theorem

Read the complete text