SPHERE PACKING NUMBERS FOR SUBSETS OF THE BOOLEAN N-CUBE WITH BOUNDED VAPNIK-CHERVONENKIS DIMENSION

Let V subset of or equal to {0, 1}(n) have Vapnik-Chervonenkis dimension d. Let M(k/n, V) denote the cardinality of the largest W subset of or equal to V such that any two distinct vectors in W differ on at least k indices. We show that M(k/n, V) less than or equal to (cn/(k + d))(d) for some constant c. This improves on the previous best result of ((cn/k)log(n/k))(d). This new result has applications in the theory of empirical processes. (C) 1995 Academic Press, Inc.