Skip to main content
MathOverflow

Return to Question

added tag, and format edits; added 2 characters in body
Source Link
user9072
user9072

Let S$S$ be a set of binary vectors (in {0,1}^m$\lbrace 0,1 \rbrace^m $) whose VC dimension is d$d$. Let H$H$ be the hammingHamming 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$d$ positions. Is there a way to bound the size of the vertex cover of H$H$?

Any relevant reference would be of great help!

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!

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!

Source Link
Arun
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!