Campbell et al. Show Contradiction Graphs Determine VC Dimension

A new paper by Jesse Campbell, Daniel Ibaibarriaga, and Lev Reyzin introduces a graph-theoretic approach to determining the Vapnik–Chervonenkis (VC) dimension of binary concept classes. The authors define the order-m contradiction graph G_m(H), where vertices are H-realizable labeled sequences of length m, and two vertices are adjacent when the sequences assign opposite labels to a common domain point. Their main result is that a single graph G_m(H) can answer the threshold question: Is VCdim(H) >= m? Consequently, examining the entire sequence of graphs for increasing m reveals the exact VC dimension and determines whether it is finite or infinite. This elegantly solves an open problem posed by Alon et al. in 2024.

The implications for machine learning theory are significant. VC dimension is a central measure of model complexity and generalization, but computing it for arbitrary classes is notoriously hard. This graph-based characterization provides a new, structurally intuitive lens: the contradiction graph encodes the interplay of realizable sequences. While practical computation for large classes remains challenging, the result deepens understanding of how combinatorial structure relates to learnability. It also opens doors for algorithmic approaches that leverage graph properties to bound or compute VC dimension, potentially impacting the design of learning algorithms and the analysis of overparameterized models.