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].