Expressivity of Contradiction Graphs

Jesse Campbell, Daniel Ibaibarriaga, Lev Reyzin

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