题目：Maximum size of a uniform family with bounded VC-dimension

报告人：杨天驰  博士，佐治亚理工学院

时间：2025年12月8日下午，2:00-3:00

地点：二教 2210

摘要：In the 1980s, Frankl, and Pach conjectured the maximum size of a $(d+1)$-uniform set family $\mathcal{F}$ on an $n$-element set with  VC-dimension at most $d$ is $\binom{n-1}{d}$. While their specific conjecture was later disproven by Ahlswede and Khachatrian, the problem of determining this maximum size remains a central question in extremal set theory. For decades, a significant gap persisted between the best-known lower and upper bounds. The established lower bound was $\binom{n-1}{d}+\binom{n-4}{d-2}$, while the longstanding upper bound $\binom{n}{d}$ was recently improved to $ \binom{n-1}{d}+O( n^{d-1-\frac{1}{4d-2}})$. We narrow this gap by showing a new upper bound of $\binom{n-1}{d} + O(n^{d-2})$. The improvement is substantial, as the error term now matches the order of magnitude of the second term in the lower bound. This is joint work with Xingxing Yu.