1
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I might be wrong, but I suspect the notion of VC dimesion (Vapnik-Chervonenkis, I assume after some searching) is not very widely known on this site. It could help in attracting answers, if you would include more context in your question(s). $\endgroup$
    – user9072
    Commented Aug 27, 2012 at 19:08
  • $\begingroup$ @quid: VC dimension is well known by some. It's one of the fundamental theoretical tools in the theory of learning, and it should be covered in any first course on machine learning even if you don't do anything rigorous, since it is intuitive, too. youtube.com/watch?v=Dc0sr0kdBVI $\endgroup$
    – Douglas Zare
    Commented Aug 27, 2012 at 20:22
  • 1
    $\begingroup$ @Douglas Zare: thank you for the information. I sorted-of figured it was a well-known notion in learning theory. But then while I know there are some experts on this on MO, I thought since this is tagged combinatorics there could be some additional people that might be able to say something if the problem was spelled out (but perhaps this is infeasible or unlikley to be of success). Anyway, it was just an idea, since this is the second question of OP that seems to pass a bit unnoticed. I will tag in addition learning-theory. $\endgroup$
    – user9072
    Commented Aug 27, 2012 at 23:31

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .