Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
en.wikipedia.org/wiki/Bipartite_graph $\:$ –  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.