Exact VC-Dimension of Boolean Monomials

We show that the Vapnik-Chervonenkis dimension of Boolean monomials over n variables is at most n for all n 2. It follows that the VC-dimension is determined exactly and is, except for n = 1, equal to the VC-dimension of the proper subclass of monotone monomials. Keywords: Combinatorial Problems, Computational Complexity, Learnability Work supported by the ESPRIT Working Group NeuroCOLT No. 8556 1 Introduction The Vapnik-Chervonenkis dimension VC-dim(C) of a collection C of subsets of a set X is defined as the maximum cardinality of any set S ` X that is shattered by C. A set S is shattered by C if for every subset T of S there exists a C 2 C such that T = S " C. The VC-dimension of a class F of functions f : X ! f0; 1g is defined by identifying each element f 2 F with the set fx 2 X : f(x) = 1g. Thus VC-dim(F) is the maximum cardinality of any set S ` X for which F induces all functions g : S ! f0; 1g. The Vapnik-Chervonenkis dimension gives almost tight bounds for the numb..