Abstract

The Vapnik-Chervonenkis (VC) dimension is a fundamental concept in learning theory that has found increasing applications in extremal combinatorics. Over the years, significant progress has been made in understanding the interplay between VC-dimension theory and extremal combinatorics. A cornerstone result from the 1970s, known as the Sauer-Shelah Lemma, precisely characterizes the maximum size of a non-uniform set system with bounded VC-dimension. However, the analogous problem for uniform set systems remains a major open question.  In this talk, I will present recent advances on this problem, including improved bounds and new structural insights. This is based on joint work with Ting-Wei Chao, Gennian Ge, Chi Hoi Yip, Shengtong Zhang, and Xiaochen Zhao.