Expressivity of Contradiction Graphs
Abstract
We study the contradiction graphs associated with a binary concept class. For a class H⊆{0,1}X, 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 VCdim(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.
Related
- Algebraic Expressivity Certificates for Shallow Polynomial Neural Networks
- The Surprising Expressivity of a Single Neuron with Autoregressive Chain-of-Thought
- Constructive Bounds for the Topological Expressivity of Neural Networks
- Information-Induced Training Geometry: Exact Reduction, Canonical Completion, and Structured Expressivity
- Fractional Laplace Neural Operators: Exact Architectures, an Expressivity Frontier at Criticality, and Certified Stability for Memory-Driven Network Dynamics
BibTeX
@misc{campbell2026expressivity,
title = {{Expressivity of Contradiction Graphs}},
author = {Jesse Campbell and Daniel Ibaibarriaga and Lev Reyzin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.20434},
eprint = {2605.20434},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.20434},
}
RIS
TY - UNPB
TI - Expressivity of Contradiction Graphs
AU - Jesse Campbell
AU - Daniel Ibaibarriaga
AU - Lev Reyzin
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2605.20434
UR - https://arxiv.org/abs/2605.20434
AB - We study the contradiction graphs associated with a binary concept class. For a class H⊆{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 VCdim(H)≥ m. Consequently, the sequence (G_m(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.
ER -