Constrained versions of Sauer’s lemma

Let n]={1,…,n}. For a function h:n]→{0,1}, xn] and y{0,1} define by the width ω_h(x,y) of h at x the largest nonnegative integer a such that h(z)=y on x−a≤z≤x+a. We consider finite VC-dimension classes of functions h constrained to have a width ω_h(x_i,y_i) which is larger than N for all points in a sample or a width no larger than N over the whole domain n]. Extending Sauer’s lemma, a tight upper bound with closed-form estimates is obtained on the cardinality of several such classes.