10/01/1991 09:00 AM
Computer Science
Let V contained in {0,1}^n have Vapnk- Chervonenkis dimension d. Let M(k/n,V) denote the cardinality of the largest W contained in V such that any two distinct vectors in W differ on at least k indices. We show that M(k/n,V) <= (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.
