0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ en.wikipedia.org/wiki/Bipartite_graph $\:$ $\endgroup$
    – user5810
    Aug 16, 2012 at 19:26
  • $\begingroup$ @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? $\endgroup$
    – Arun
    Aug 17, 2012 at 6:05

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.