When moving to \(\mathcal {H}\subseteq \lbrace 0,\ldots ,k\rbrace ^\mathcal {X}, k > 1,\)  there are many different extensions of the VC-dimension that have been considered in the literature. We recall the definition of two of them that are important in our work, the Natarajan dimension [1]} and the Graph dimension [2]}, [1]}.
