Contradiction Graphs Determine VC Dimension
Provides a graph-theoretic characterization of VC dimension, a fundamental concept in learning theory, for the broader ML theory community.
The paper shows that the order-m contradiction graph of a binary concept class determines whether its VC dimension is at least m, and thus the full graph sequence determines the exact VC dimension, answering an open question by Alon et al. (2024).
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$-realizable labeled sequences of length $m$, with two vertices adjacent when the two sequences assign opposite labels to some common domain point. Our main result is that the single graph $G_m(H)$ determines the threshold predicate $\mathrm{VCdim}(H)\ge m$. Consequently, the full sequence $(G_m(H))_{m \ge 1}$ determines the exact VC dimension and, in particular, detects finite versus infinite VC dimension, answering a question posed by Alon et al. (2024).