Maxmum Size of a Uniform Family with Bounded VC-dimension

Tianchi Yang; Xingxing Yu

paper

Maxmum Size of a Uniform Family with Bounded VC-dimension

arXiv:2508.14334

Abstract

In 1984, Frankl and Pach proved that, for positive integers $n$ and $d$ , the maximum size of a $(d + 1)$ -uniform set family $F$ on an $n$ -element set with VC-dimension at most $d$ is at most $(d n)$ ; and they suspected that $(d n)$ could be replaced by $(d n - 1)$ , which would generalize the famous Erdős-Ko-Rado theorem and was mentioned by Erdő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 $(d n - 1) + (d - 2 n - 4)$ , 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 $(d n - 1) + (d - 2 n - 4)$ and the upper bound $(d n)$ . In a recent breakthrough, Chao, Xu, Yip, and Zhang reduced the upper bound $(d n)$ to $(d n - 1) + O (n^{d - 1 - \frac{1}{4 d - 2}})$ . In this paper, we further reduce the upper bound to $(d n - 1) + O (n^{d - 2})$ , asymptotically matching the lower bound $(d n - 1) + (d - 2 n - 4)$ .

16 pages