Contradiction Graphs Determine VC Dimension

• URL: http://arxiv.org/abs/2605.20434v1
• Date: Tue, 19 May 2026 19:30:46 GMT
• Title: Contradiction Graphs Determine VC Dimension
• Abstract summary: We study the contradiction graphs associated with binary concept classes.<n>Our main result is that the single graph $G_m(H)$ determines the threshold predicate $mathrmVCdim(H)ge m$.
• Score: 0.45880283710344055
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the contradiction graphs associated with binary concept classes. 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. Our main result is that the single graph $G_m(H)$ determines the threshold predicate $\mathrm{VCdim}(H)\ge m$. Consequently, the full sequence $(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).

Related papers

• Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence [54.59847568544922]
  We study horizon-free regret for finite-horizon time-homogeneous Markov decision processes with $A$ states, $A$ actions, horizon $H$, and per-trajectory total reward bounded by $1$.<n>We prove a regret upper bound [tilde O(sqrtSAK+S8A3)] with failure probability $$, where $K$ is the number of episodes and $tilde O(sqrtSAK+S3K)$ hides $mathsfpoly
  arXiv  Detail & Related papers  (2026-07-22T07:42:19Z)
• Perfect State Transfer on Quotient Graphs in Shunt Decomposition-Based Quantum Walks [0.0]
  This paper investigates perfect state transfer (PST) in discrete-time constructed via the shunt decomposition method.<n>We derive an explicit relation between the shift operator of the parent graph $G$ and that of its quotient graph $G/$.<n>We prove that PST occurs on $G$ if and only if it occurs on $G/$.
  arXiv  Detail & Related papers  (2026-06-23T11:18:49Z)
• Schur States, Average Mixing, and Counting Trees on Line Graphs' CTQW [0.0]
  We introduce a family of complex-valued edge weights on a finite simple graph $G$ arising from a continuous-time quantum walk on the line graph $ellG$.<n>We identify a structural mechanism -- the $-2$ eigenspace of $ellG$ -- providing uniform commutative states beyond the regular case.
  arXiv  Detail & Related papers  (2026-05-03T16:31:26Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation [47.790126028106734]
  A popular approach to cope with the NP-hardness is to compute a strong coreset.<n>We obtain an algorithm for constructing a strong coreset for $ell_p$ subspace approximation of size $tilde O(kepsilon-4/p)$ for $p2$ and $tilde O(kp/2epsilon-p)$ for $p>2$.
  arXiv  Detail & Related papers  (2024-07-03T16:49:28Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem. We consider detecting the presence of a planted $Gr(ngamma, n-alpha)$ subhypergraph in a $Gr(n, n-beta) hypergraph. Our results are already new in the graph case $r=2$, as we consider the subtle log-density regime where hardness based on average-case reductions is not known.
  arXiv  Detail & Related papers  (2023-04-17T10:38:08Z)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
  arXiv  Detail & Related papers  (2022-08-12T15:05:07Z)
• Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems [0.0]
  We prove that the continuous-time quantum walk (CTQW) -- with Hamiltonian $H=gamma L$ -- does not depend on the graph $G$. We apply our results to spatial search and quantum transport for single and multiple fully connected marked vertices.
  arXiv  Detail & Related papers  (2022-02-28T14:33:44Z)
• Fast Computation of Generalized Eigenvectors for Manifold Graph Embedding [38.902986549367434]
  We leverage existing fast extreme eigenvector computation algorithms for speedy execution. Our embedding is among the fastest in the literature, while producing the best clustering performance for manifold graphs.
  arXiv  Detail & Related papers  (2021-12-15T03:45:39Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs. It can be viewed as a noisy average-case version of the graph isomorphism problem.
  arXiv  Detail & Related papers  (2021-10-11T05:07:50Z)
• A common variable minimax theorem for graphs [3.0079490585515343]
  We study the problem of understanding whether there exists a nonconstant function that is smooth with respect to all graphs in $mathcalG$, simultaneously, and how to find it if it exists.
  arXiv  Detail & Related papers  (2021-07-30T16:47:25Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  A learning agent repeatedly chooses from a set of $K$ actions after being presented with a $d$-dimensional context vector. The agent incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures. Two efficient algorithms are developed based on textttEXP3.
  arXiv  Detail & Related papers  (2020-12-10T15:40:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.