D. Haussler and P. M. Long. A
generalization of Sauer's Lemma. Journal
of Combinatorial Theory, Series A, 71(2):219-240, 1995.
Abstract
We generalize the Sauer-Shelah lemma
to multivalued functions,
proving tight bounds on the cardinality of sets of functions
from {1,...,m} to {0,...,N} that avoid certain patterns.
In addition, we give an application of this result, bounding
the uniform rate of convergence of empirical estimates of the
expectations of a set of random variables to
their true expectations.