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

Are there any well studied graph theoretic properties that are common to all subgraphs of the boolean hypercubes that have a given VC dimension d.

share|cite|improve this question $\:$ – Ricky Demer Aug 16 '12 at 19:26
@Ricky Demer Well,any induced subgraph of the boolean hypercube is bipartite. But the question is what other properties emerge when the set of boolean vectors that the nodes of the induced subgraph represent has VC dimension d? – Arun Aug 17 '12 at 6:05

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.