Expressivity of Contradiction Graphs
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$-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 $\operatorname{VCdim}(H)\ge m$. Consequently, the sequence $(G_m(H))_{m\ge1}$ 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 sequenc...
| Authors | Jesse Campbell, Daniel Ibaibarriaga, Lev Reyzin |
|---|---|
| Primary category | stat.ML |
| Published | 19 May 2026 |
| Last updated at source | 4 September 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.