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 .

Leave a Reply

Your email address will not be published. Required fields are marked *