Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.11901 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916779964497920 |
|---|---|
| author | Ge, Gennian Xu, Zixiang Yip, Chi Hoi Zhang, Shengtong Zhao, Xiaochen |
| author_facet | Ge, Gennian Xu, Zixiang Yip, Chi Hoi Zhang, Shengtong Zhao, Xiaochen |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_11901 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Frankl-Pach upper bound is not tight for any uniformity Ge, Gennian Xu, Zixiang Yip, Chi Hoi Zhang, Shengtong Zhao, Xiaochen Combinatorics 05D05 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. |
| title | The Frankl-Pach upper bound is not tight for any uniformity |
| topic | Combinatorics 05D05 |
| url | https://arxiv.org/abs/2412.11901 |