The ACO Seminar (2020–2021)

A family of sets is $d$-saturated, if it has VC-dimension $d$ and adding any new set to the family increases the VC-dimension. We study the minimum cardinality of a $d$-saturated family on a ground set of size $n$. For $d=1$ this minimum is $n+1$, which is the same as the Sauer-Shelah bound for the maximum cardinality of a family of VC-dimension $1$. For $d>1$ we find upper bounds that do not depend on $n$, only on d. Joint work with Sergei Kiselev, Andrey Kupavskii and Balázs Patkós.

Please email Boris Bukh (bbukh ~at~ math) for a password.