Skip to main content
2 of 2
added tag, and format edits; added 2 characters in body
user avatar
user avatar

Vertex cover for hamming graphs representing sets of bounded VC dimension

Let $S$ be a set of binary vectors (in $\lbrace 0,1 \rbrace^m $) whose VC dimension is $d$. Let $H$ be the Hamming graph generated from this set where each node represents a binary vector and two nodes have an edge if they differ in "at most" $d$ positions. Is there a way to bound the size of the vertex cover of $H$?

Any relevant reference would be of great help!

Arun
  • 11
  • 1