This is the problem from David Pollard Book" Convergence of Stochastic Process".
Can anyone give me some hint here??
Let $S_0$ be a set of N points in $S$. Suppose there is an integer $V\leq N$ such that $D$ shatters no set of V points in $S_0$. Then $D$ picks out no more that ${n \choose 0}+ {n \choose 1}+ .....+ {n \choose {V-1}}$ subset from $S_0$
The above theorem informs us that the class of quadrants in $R^2$ picks out at most $1+\frac{1}{2}N+ \frac{1}{2}N^2$ subsets from any collection of N points. Find a configuration for which this bound is achieved.
Hstrong textow to find Configuration for which this bound is achived??
Definition from the same book :
Let $D$ be a class of subsets of some space $S$. It is said to have polynomial discrimination (of degree v) if there exists a polynomial $\rho(.)$ (of degree $v$) such that, from every set of $N$ points in $S$, the class picks out at most $\rho(N)$ distinct subsets. Formally, if $S_0$ consists of $N$ points, then there are at most $\rho(N)$ distinct sets of the form $S_0\bigcap d $ with$ d$ in $D$. Call $\rho(.)$ the discriminating polynomial for $D$.
Thank you