Let [n]={1,...,n}. For a function h:[n]->{0,1}, x@?[n] and y@?{0,1} define by the width@w"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 @w"h(x"i,y"i) which is larger than N for all points in a sample @z={(x"i,y"i)}"1^@? 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.
['Joel Ratsaby']
Constrained versions of Sauer's lemma