Expressivity of Contradiction Graphs

We study the contradiction graphs associated with a binary concept class. For a class Hsubseteq0,1X, the order-m contradiction graph Gm(H) has as vertices the H-realizable labeled sequences of length m, with two vertices adjacent when the two sequences assign opposite labels to some common domain point. First, we identify a graph-theoretic property that determines the threshold predicate operatornameVCdim(H)≥ m. Consequently, the sequence (Gm(H))m≥1 determines the exact VC dimension and, in particular, distinguishes finite from infinite VC dimension, answering a question posed by Alon et al. (2024). We then generalize this result by proving that the sequence of contradiction graphs determines, up to signed relabeling, the realizable datasets of any fixed length. Thus, any learning-theoretic property determined by the realizable datasets of a fixed length and invariant under signed relabeling can be recovered from the contradiction graph sequence. As an application, we explicitly provide a characterization of Littlestone dimension.