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.

Improve this question
$\endgroup$
2
  • $\begingroup$ en.wikipedia.org/wiki/Bipartite_graph $\:$ $\endgroup$
    – user5810
    Commented 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
    Commented Aug 17, 2012 at 6:05

0

Reset to default

You must log in to answer this question.