In 1984, Frankl and Pach proved that, for positive integers $n$ and $d$, the maximum size of a $(d+1)$-uniform set family $\mathcal{ F}$ on an $n$-element set with VC-dimension at most $d$ is at most ${ n\choose d}$; and they suspected that ${ n\choose d}$ could be replaced by ${ n-1\choose d}$, which would generalize the famous Erd\H{ o}s-Ko-Rado theorem and was mentioned by Erd\H{ o}s as Frankl--Pach conjecture. However, Ahlswede and Khachatrian in 1997 constructed $(d+1)$-uniform families on an $n$-element set with VC-dimension at most $d$ and size exactly $\binom{ n-1}{ d}+\binom{ n-4}{ d-2}$, and Mubayi and Zhao in 2007 constructed more such families. It has since been an open question to narrow the gap between the lower bound $\binom{ n-1}{ d}+\binom{ n-4}{ d-2}$ and the upper bound ${ n\choose d}$. In a recent breakthrough, Chao, Xu, Yip, and Zhang reduced the upper bound $\binom{ n }{ d}$ to $ \binom{ n-1}{ d}+O( n^{ d-1-\frac{ 1}{ 4d-2}})$. In this paper, we further reduce the upper bound to $\binom{ n-1}{ d} + O(n^{ d-2})$, asymptotically matching the lower bound $\binom{ n-1}{ d}+\binom{ n-4}{ d-2}$.
Categories: math.CO