Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension

Let V ⊆ {0, 1}n have Vapnik-Chervonenkis dimension d. Let M(k/n, V) denote the cardinality of the largest W ⊆ 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 ((cnk)log(nk))d. This new result has applications in the theory of empirical processes.