Expressivity of Contradiction Graphs

תקציר מקורי באנגליתarXiv:2605.20434v2 Announce Type: replace-cross Abstract: 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 sequence of contradiction graphs determines, up to s