ON THE VC-DIMENSION OF BINARY CODES.

We investigate the maximal asymptotic rates of length-n binary codes with VC-dimension at most dn and minimum distance at least δn. Two upper bounds are obtained, one as a simple corollary of a result by Haussler and the other via a shortening approach combining the Sauer--Shelah lemma and the linear programming bound. Two lower bounds are given using Gilbert--Varshamov-type arguments over constant-weight and Markov-type sets. [ABSTRACT FROM AUTHOR]