most recent 30 from http://mathoverflow.net 2013-05-20T03:53:56Z http://mathoverflow.net/feeds/question/105645 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105645/vertex-cover-for-hamming-graphs-representing-sets-of-bounded-vc-dimension Arun 2012-08-27T17:38:18Z 2012-08-27T23:33:17Z

<p>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$?</p> <p>Any relevant reference would be of great help!</p>