On the complexity of constrained VC-classes

Sauer's lemma is extended to classes H_N of binary-valued functions h on [n]={1,…,n} which have a margin less than or equal to N on all x∈[n] with h(x)=1, where the margin μ_h(x) of h at x∈[n] is defined as the largest non-negative integer a such that h is constant on the interval I_a(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].