stat.MLMay 19, 2026

Contradiction Graphs Determine VC Dimension

Authors: Jesse CampbellDaniel IbaibarriagaLev Reyzin

Organizations: Department of Mathematics, Statistics, & Computer Science University of Illinois Chicago

Abstract

We study the contradiction graphs associated with binary concept classes. For a class H{0,1}XH \subseteq \{0,1\}^X, the order-mm contradiction graph Gm(H)G_m(H) has as vertices the HH-realizable labeled sequences of length mm, with two vertices adjacent when the two sequences assign opposite labels to some common domain point. Our main result is that the single graph Gm(H)G_m(H) determines the threshold predicate VCdim(H)m\mathrm{VCdim}(H)\ge m. Consequently, the full sequence (Gm(H))m1(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).

Explore similar work

CardsList
  1. The VC dimension of partial concept classes via Radon's theorem

    Jul 12, 2026Grigory Ivanov, Attila Jung, Márton NaszódiMetric SpacesTheorem

  2. A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC

    Aug 31, 2026Mateus Jesus de Arruda Campos, Gabriel Fernandes, Vinicius de Oliveira RodriguesProbability Measures