A lower bound for families of Natarajan dimension d

Abstract

The Natarajan dimension is a generalization of the VC-dimension to families of multivalued functions. We prove a lower bound on the maximum cardinality of families of a given dimension.