1
$\begingroup$

Let $A$ and $B$ be sets of real-valued functions on $X$. Are there any reasonably tight bounds on the VC-dimension of $A\cap B$ in terms of the VC-dimensions of $A$ and $B$?

$\endgroup$
4
  • $\begingroup$ There are Van Der Vaart results on the set of sets constructed as intersection of the members of A&B but that's different. I expect that one cannot do better than the min of their VC dimensions. $\endgroup$
    – ABIM
    Commented Aug 8 at 13:37
  • $\begingroup$ If $A \subseteq B$, then the VC-dim is the min. $\endgroup$ Commented Aug 8 at 18:04
  • $\begingroup$ What does that mean? You mean if $X\subset A\cap B$ then $VC(X)\le \min\{VC(A),VC(B)\}$ no? $\endgroup$
    – ABIM
    Commented Aug 8 at 21:14
  • 1
    $\begingroup$ If they're linearly ordered by inclusion, then a tight upper bound is 2, do you need a proof for this? $\endgroup$
    – Saginus
    Commented Sep 25 at 11:12

0

You must log in to answer this question.

Browse other questions tagged .