5
$\begingroup$

I first recall some definition since the notation can differ somewhat.

Consider a formula $\phi(x,z)$ defining a binary relation $\{(u,v)\in U\times V|\quad \phi(u,v)\}$.
$\phi$ defines subsets of $U$ as $\phi(U,b)=\{a\in U|\quad \phi(a,b)\}$.
The corresponding collection of defined subsets is $\phi(U,b)_{b\in V}\subset\wp(U)$
Now, we say $\phi$ has VC dimension $\kappa$ if $\kappa$ is the maximum cardinality of $A\subset U$ such that $\phi$ shatters $A$ i.e. $\phi(A,b)_{b\in V}=\wp(A)$
The dual dimension is just the dimension of the dual formula $\phi^*(z,x):=\phi(x,z)$

Now I am asked to find a formula as in the title.

The only way I know to produce a formula (actually a set-system, in an equivalent fashion) of arbitrary $\kappa$ VC dimension is to consider: $$\Phi=U^{\leq\kappa}:=\{A\subset U|\quad |A|\leq\kappa\}\subset\wp(U)$$

Now this is equivalent to the binary relation defined by $$\phi(u,B)\Leftrightarrow u\in B \quad\quad on\ \ U\times\Phi$$

So my try is to prove that $\phi^*(B,u)$ has VC dimension $2^k$.
To asess that it has dimension $\geq2^\kappa$ I would try by proving that since there must be $A\subset U\ \ |A|=\kappa$ shattered by $\phi$ then $\phi^*$ shatters $\wp(A)\subset \phi\ \ |\wp(A)|=2^\kappa$.

Anyhow I am quite stuck on this.
I think that similarly one can prove that $\phi^*$ has VC dimension $\leq 2^\kappa$

Can someone help?

$\endgroup$
5
$\begingroup$

I'll assume $\kappa$ is finite in this answer. For infinite $\kappa$, there's one major issue: The function $\kappa\mapsto 2^\kappa$ may not be strictly increasing on infinite cardinals. If you're really interested in infinite $\kappa$, I think that everything I wrote goes through with minor modifications if you assume GCH. I'm not sure what happens when $\kappa\mapsto 2^\kappa$ is not strictly increasing.


The set system $\mathcal{P}_{\leq\kappa}(U) = \{A\subseteq U\mid |A|\leq \kappa\}$ is a natural guess, since it is somehow the canonical set system with VC dimension $\kappa$. Unfortunately, it can't have dual VC-dimension $2^\kappa$. Suppose we have $\mathcal{B} = \{B_1,\dots,B_{d}\}\in \wp_{\leq\kappa}(U)$. To shatter $\mathcal{B}$, we need a family $(a_X)_{X\subseteq \mathcal{B}}$ of $2^{d}$-many (distinct) elements of $U$ such that for any subset $X\subseteq \mathcal{B}$, we have $a_X\in B_j$ if and only if $B_j\in X$. But for each $j$, $B_j$ is in exactly half of the $2^{d}$-many subsets of $\mathcal{B}$, so $B_j$ contains $2^{d-1}$ many distinct elements $a_X$, and hence $\kappa \geq |B_j|\geq 2^{d-1}$. This shows that $\lfloor \log_2(\kappa)\rfloor + 1$ is an upper bound for the dual VC dimension of $\mathcal{P}_{\leq\kappa}(U)$. And that quantity is much smaller than $2^\kappa$, for all $\kappa>0$.

However, this suggests that $\mathcal{P}_{\leq 2^\kappa}(U)$ might be an example of a set system with VC dimension $2^\kappa$ and dual VC dimension $\kappa$. This is equivalent to what you asked for, by dualizing. In fact, this system has dual VC dimension $\kappa+1$. But we can fix the example: rather than considering the subsets of size at most $2^\kappa$ of some large set $U$, let's just think about the full power set of a set $U$ of size $2^\kappa$ (and note that all such sets have size at most $2^\kappa$!).


Let $U$ be a set of size $2^\kappa$, and consider the set system $\mathcal{P}(U)$ (the full power set). Clearly $\mathcal{P}(U)$ has VC dimension $2^\kappa$, since it shatters $U$, but there is no subset of $U$ of size greater than $2^\kappa$ to shatter. But also the dual VC dimension is at most $\kappa$, since we would need $2^{\kappa+1}$ points in $U$ to shatter a subset of $\mathcal{P}(U)$ of size $\kappa+1$. So it remains to show that the dual VC dimension is at least $\kappa$.

This follows from the usual bound (see below): If the dual VC dimension of a set system is $d$, then the VC dimension of the set system is strictly less than $2^{d+1}$.

In the contrapositive, this says that if the VC dimension of a set system is at least $2^{d+1}$, then the dual VC dimension is strictly greater than $d$. Equivalently, taking $\kappa = d+1$, if the VC dimension of a set system is at least $2^{\kappa}$, then the dual VC dimension is at least $\kappa$, which is what we wanted.


Proof of the usual bound: We prove it in the modified contrapositive form, that if the VC dimension of a set system $\Phi$ on the set $U$ is at least $2^{\kappa}$, then the dual VC dimension is at least $\kappa$.

Let $A\subseteq U$ be a subset of size $2^\kappa$ which is shattered by $\Phi$. Put the elements of $A$ in bijection with binary sequences of length $\kappa$. For $a\in A$ and $n < \kappa$, write $a(n)\in \{0,1\}$ for the $n^\text{th}$ term in the corresponding sequence. Now for each $n < \kappa$, let $B_n\in \Phi$ be a set such that for all $a\in A$, $a\in B_n$ if and only if $a(n) = 1$ (we can do this since $\Phi$ shatters $A$). Then $\mathcal{B} = \{B_n\mid n<\kappa\}$ has size $\kappa$, and $\mathcal{B}$ is shattered by $A$. Indeed, for any subset $X\subseteq \mathcal{B}$, let $a\in A$ be the element such that $a(n) = 1$ if and only if $B_n\in X$. Then for all $n$, $a\in B_n$ if and only if $a(n) = 1$ if and only if $B_n\in X$. So the dual VC dimension is at least $\kappa$.


Incidentally, exactly the same argument shows that the usual bound is tight. That is, we can do better than what you asked for: We can find a set system with VC dimension $2^{\kappa+1}-1$ and dual VC dimension $\kappa$.

Let $U$ be a set of size $2^{\kappa+1}-1$, and consider the set system $\mathcal{P}(U)$. Clearly $\mathcal{P}(U)$ has VC dimension $2^{\kappa+1}-1$. But the dual VC dimension is at most $\kappa$, since we would need $2^{\kappa+1}$ elements of $U$ to shatter a subset of $\mathcal{P}(U)$ of size $\kappa+1$. And by the usual bound, since the VC dimension is at least $2^\kappa$, the dual VC dimension is at least $\kappa$, and hence equal to $\kappa$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, I was interested in the finite case, so your answer is perfect! $\endgroup$ – Francesco Bilotta Apr 16 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.