Vapnik-Chervonenkis Dimension (VC-dimension) is a combinatorial
measure of a set system of subsets of a universe, developed by Vapnik and Chervonenkis in the 1960s and has found several applications in the area of statistical learning theory, discrete and computational geometry. Let U be the universe and H be a set of subsets of U. The family H is said
to shatter an S subset of U if, for all subset S’ subset of S, there is an F in H such that S intersection F = S’. VC-dimension bounds give a general lower and upper bound on sample complexity to learn the concepts from the hypothesis class in the Probability Approximately Correct (PAC) model. The universe is U = {0,1}^n and the hypothesis class is a family of Boolean functions in our context.

VC-dimension of the family of monotone functions is already known to be {n choose n/2}. (Procaccia and Rosenschein (2006)). Alternation of a Boolean function is a measure of non-monotonicity which parameterizes the number of changes in the function value along any chain in the Boolean hypercube. We prove asymptotically matching lower and upper bound of VC-dimension in terms of alternation. For a special case of k = 1, the family contains Monotone functions and its negation for which we give exact bounds of VC-dimension for this family. As an application, we use it derive the 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, k-F = {union{i=1 to k} F_i | F_i in F } must have VC-dimension at least Omega(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. In addition, we also show shattering-extremal properties of the family of monotone functions.

VC dimension can also be defined on a single function with a natural interpretation of the family to be the positive inputs of the function.
We prove bounds for several important Boolean functions - including monotone and symmetric Boolean functions. We also prove a characterization and use it to prove complexity-theoretic bounds for the VC-dimension testing problem.