# VC dimension of TOP-set system

By | September 18, 2020

Here we mention the definition of VCdimension that came in the paper “A Simple Proof of Optimal Epsilon Nets” by Nabil H. Mustafa, Kunal Dutta & Arijit Ghosh;

Given $(X, \mathcal{R})$ and any set $Y \subseteq X$ , define the projection of $\mathcal{R}$ onto $Y$ as the set system:

$\mathcal{R} |_Y = \{ R \cap Y \ | \ R \in \ \mathcal{R} \}$

The VC dimension of $\mathcal{R}$ is the size of the largest subset Y for which $\mathcal{R} |_Y = 2^Y$.

Now if $(X , \mathcal{R} , TOP(\mathcal{R}) )$ be a TOP-set system, the projection of $TOP(\mathcal{R})$ on $Y \subseteq X$ as a TOP-set system:

$TOP(\mathcal{R}) |_Y = \{ R \cap Y \ | \ R \in \ TOP(\mathcal{R}) \}$

is the subspace topology of $TOP(\mathcal{R})$ on $Y$.

The VC dimension of $TOP ( \mathcal{R} )$ is the size of the largest subset Y for which $TOP(\mathcal{R}) |_Y = 2^Y$.

Question: ‎Is ‎it ‎true ‎that ‎if‎ ‎$(X, \mathcal{R}_1, TOP(\mathcal{R}_1) ) ‎$ ‎and‎ ‎ ‎$( X, \mathcal{R}_2, TOP(\mathcal{R}_2) ) ‎$ ‎be ‎two TOP-‎set ‎system,‎ ‎and‎ ‎ ‎$TOP(\mathcal{R}_1) ‎$ ‎be a‎ ‎finer ‎topology ‎on‎ ‎ ‎$X ‎$ ‎than‎ ‎ ‎$TOP(\mathcal{R}_2) ‎$‎, then

$VC-dim ( TOP(\mathcal{R}_1) ) \ge VC-dim ( TOP(\mathcal{R}_2) ) ‎$ ‎?

If so, How about saying ‎$VC-dim ( \mathcal{R}_1) \ge VC-dim ( \mathcal{R}_2)‎$ ‎?

Example: If $|X| = n$ and $(X, P(X) ) ‎$ ‎be a set system, and $P(X)$ be the discrete topology on $X ‎$, then obviously $VC-dimension (P(X)) = n$.

Question: is the following proposition true?

If $(X , \mathcal{R} , TOP(\mathcal{R}) )$ be a TOP-set system, then $VC-dim ( TOP(\mathcal{R}) ) ‎$ is the size of largest subset $Y$ that the subspace topology of $TOP(\mathcal{R})$ on $Y$ is the same with discrete topology on $Y$.