I was solving questions about finding the VC dimension of some binary classifiers, and I couldn't solve this one:
$\mathcal{H}$ is a hypothesis set on $\mathbb{R}^d$, given by:
$\mathcal{H}=\{f_{T, S}(x)= 2\cdot [[V \in S]] - 1, \text{where } T=[t_1, t_2,\dots,t_d]^T\text{, and } V =[v_1, v_2,\dots,v_d]^T, v_i = [[x_i>t_i]]. S\text{ is a subset of }\{0,1\}^d\}$
I understood it as: We divide the space into $2^d$ regions (by choosing the vector $T$), and we mark each region with either $+1$ or $-1$ (by choosing the set $S$). For any vector $x$, $f_{T,S}(x)$ is determined by the mark of the region that $x$ belongs to.
I was only able to show that $\mathcal{H}$ can shatter $2^d$ points by choosing one from each region, but I got stuck when I tried to show $\mathcal{H}$ cannot shatter any set of $2^d+1$ points. I only knew when there were $2^d+1$ points, at least two of them would be in the same region. But since both $T$ and $S$ could be changed arbitrarily, I wasn't sure how to show that no matter how $T$ and $S$ were changed, it still couldn't shatter any set with $2^d+1$ points.