Uniform Set Systems with Small VC-Dimension
Ting-Wei Chao, Zixiang Xu, Chi Hoi Yip, Shengtong Zhang · International Mathematics Research Notices · 2025
Abstract We investigate the longstanding problem of determining the maximum size of a $(d+1)$-uniform set system with Vapnik–Chervonenkis (VC)-dimension at most $d$. Since the seminal 1984 work of Frankl and Pach, which established the elegant upper bound $\binom{n}{d}$, this question has resisted significant progress. The best-known lower bound is $ {{n-1}\choose{d}} + {{n-4}\choose{d-2}}$, obtained by Ahlswede and Khachatrian, leaving a substantial gap of $ {{n-1}\choose{d-1}}- {{n-4}\choose{d-2}}$. Despite decades of effort, improvements to the Frankl–Pach bound have been incremental at best: Mubayi and Zhao introduced an $\Omega _{d}(\log{n})$ improvement for prime powers $d$, while Ge, Xu, Yip, Zhang, and Zhao achieved a gain of 1 for general $d$. In this work, we provide a purely combinatorial approach that significantly sharpens the Frankl–Pach upper bound. Specifically, for large $n$, we demonstrate that the Frankl–Pach bound can be improved to $ {{n}\choose{d}} - {{n-1}\choose{d-1}} + O_{d}(n^{d-1 - \frac{1}{4d-2}})= {{n-1}\choose{d}}+O_{d}(n^{d-1 - \frac{1}{4d-2}})$. This result completely removes the main term $ {{n-1}\choose{d-1}}$ from the previous gap between the known lower and upper bounds. It also offers fresh insights into the combinatorial structure of uniform set systems with small VC-dimension. In addition, the original Erdős–Frankl–Pach conjecture, which sought to generalize the Erdős–Ko–Rado (EKR) theorem in the 1980s, has been disproven. We propose a new refined conjecture that might establish a sturdier bridge between VC-dimension and the EKR theorem, and we verify several specific cases of this conjecture, which is of independent interest.