Contradiction Graphs Determine VC Dimension

Jesse Campbell, Daniel Ibaibarriaga, Lev Reyzin

We study the contradiction graphs associated with binary concept classes. For a class $H\subseteq \{0,1{\}}^X$, the order-$m$ contradiction graph $G_m(H)$ has as vertices the $H$-re…