Uniform Set Systems with Small VC-Dimension

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 nd, this question has resisted significant progress. The best-known lower bound is n-1d + n-4d-2, obtained by Ahlswede and Khachatrian, leaving a substantial gap of n-1d-1- n-4d-2. Despite decades of effort, improvements to the Frankl–Pach bound have been incremental at best: Mubayi and Zhao introduced an Ω d(logn) 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 nd - n-1d-1 + Od(nd-1 - 1/4d-2)= n-1d+Od(nd-1 - 1/4d-2). This result completely removes the main term n-1d-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.