Constrained versions of Sauer’s lemma

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