A General Framework for Proving Sauer-Shelah Type Lemmas

Abstract

We present two versions of "shatter functions" and show that they are upper-bounded by the same polynomial, known as the Sauer-Shelah dichotomy. Then, we analyze a third setting due to Chase and Freitag [3], the $(n, k)$-banned binary sequence problems (BBSPs). Our purpose is to give an accessible exposition of their result and show that this is not only a generalization of both theorems, but also of both proofs. In particular, a new proof is obtained for the thicket case following this generalization.