Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension (Q1345876): Difference between revisions

Let \(V\) be a subset of the Boolean \(n\)-cube \(\{0,1\}^ n\) with Vapnik-Chervonenkis dimension \(d\). Let \(M(k/n, V)\) denote the cardinality of the largest subset \(W\) of \(V\) such that any two distinct vectors in \(W\) differ on at least \(k\) indices. It is shown that \[ M (k/n, V) \leq e(d + 1) \bigl( 2e (n + 1)/(k + 2d + 2) \bigr)^ d. \] This improves on the best previous result which contained an extra factor \((\log (n/d))^ d\). The new bound is best possible up to a multiplicative constant. There are applications in the theory of empirical processes.