Vapnik-Chervonenkis Dimension and Density on Johnson and Hamming Graphs

Bjarki Geir Benediktsson, Dugald Macpherson, Isolde Adler

VC-dimension and VC-density are measures of combinatorial complexity of set systems. VC-dimension was first introduced in the context of statistical learning theory, and is tightly…