On Alternation, VC-dimension and k-fold Union of Sets

Alternation of Boolean functions is a measure of non-monotonicity of the function. In this paper, we asymptotically characterize the VC-dimension of family of Boolean functions parameterized by the maximum alternation of the Boolean functions in the family. Enroute to our main result, we show exact bounds for VC-dimension of functions which has alternation 1, which strictly contains monotone functions and hence generalizes the bounds in [3]. As an application, we show tightness of VC-dimension bounds for k-fold union, by explicitly constructing a family F of subsets of { 0, 1 }n such that k-fold union of the family, Fk={⋃i=1kFi∣Fi∈F} must have VC-dimension at least Ω(dk) and that this bound holds even when the union is over disjoint sets from F. This provides a non-geometric set system achieving this bound.