2024/12/16 by Ge, Gennian, Xu, Zixiang, Yip, Chi Hoi +2 · 1 citation
#05D05 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2412.11901
For any positive integers n≥ d+1≥ 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 \binomnd 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≥ 2 and n≥ 2d+2, which demonstrates that the long-standing Frankl-Pach upper bound \binomnd is not tight for any uniformity. Our proof combines a simple yet powerful polynomial method and structural analysis.