The Frankl-Pach upper bound is not tight for any uniformity
read the original abstract
For any positive integers $n\ge d+1\ge 3$, what is the maximum size of a $(d+1)$-uniform set system in $[n]$ with VC-dimension at most $d$? In 1984, Frankl and Pach initiated the study of this fundamental problem and provided an upper bound $\binom{n}{d}$ via an elegant algebraic proof. Surprisingly, in 2007, Mubayi and Zhao showed that when $n$ is sufficiently large and $d$ is a prime power, the Frankl-Pach upper bound is not tight. They also remarked that their method requires $d$ to be a prime power, and asked for new ideas to improve the Frankl-Pach upper bound without extra assumptions on $n$ and $d$. In this paper, we provide an improvement for any $d\ge 2$ and $n\ge 2d+2$, which demonstrates that the long-standing Frankl-Pach upper bound $\binom{n}{d}$ is not tight for any uniformity. Our proof combines a simple yet powerful polynomial method and structural analysis.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Uniform set systems with small VC-dimension
Improves the Frankl–Pach upper bound on maximum size of (d+1)-uniform VC-dimension-d families to binom(n-1,d) + O_d(n^{d-1-1/(4d-2)}), disproves the Erdős–Frankl–Pach conjecture, and proposes a refined version.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.