Complexity of VC-classes of sequences with long repetitive runs

The Vapnik-Chervonenkis (VC) dimension (also known as the trace number) and the Sauer-Shelah lemma have found applications in numerous areas including set theory, combinatorial geometry, graph theory and statistical learning theory. Estimation of the complexity of discrete structures associated with the search space of algorithms often amounts to estimating the cardinality of a simpler class which is e#ectively induced by some restrictive property of the search. In this paper we study the complexity of Boolean-function classes of finite VC-dimension which satisfy a local `smoothness' property expressed as having long runs of repeated values. As in Sauer's lemma, a bound is obtained on the cardinality of such classes