pith. sign in

arxiv: 2412.11901 · v2 · pith:DZ4HIVPHnew · submitted 2024-12-16 · 🧮 math.CO

The Frankl-Pach upper bound is not tight for any uniformity

classification 🧮 math.CO
keywords boundupperfrankl-pachtightbinommethodpowerprime
0
0 comments X
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Uniform set systems with small VC-dimension

    math.CO 2025-01 unverdicted novelty 8.0

    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.