On the complexity of constrained VC-classes

Sauer's lemma is extended to classes HNHN of binary-valued functions h   on [n]={1,…,n}[n]={1,…,n} which have a margin less than or equal to N   on all x∈[n]x∈[n] with h(x)=1h(x)=1, where the margin μh(x)μh(x) of h   at x∈[n]x∈[n] is defined as the largest non-negative integer a such that h   is constant on the interval Ia(x)=[x-a,x+a]⊆[n]Ia(x)=[x-a,x+a]⊆[n]. Estimates are obtained for the cardinality of classes of binary-valued functions with a margin of at least N   on a positive sample S⊆[n]S⊆[n].