@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?
– ArunAug 17 '12 at 6:05