Skip to main content
1 of 2
Arun
  • 11
  • 1

Vertex cover for hamming graphs representing sets of bounded VC dimension

Let S be a set of binary vectors (in {0,1}^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