MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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). – user9072 Aug 27 '12 at 19:08
@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. – Douglas Zare Aug 27 '12 at 20:22
@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. – user9072 Aug 27 '12 at 23:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.