The following theorem is proved here
Let $Q_n=(V,E)$ be the Hamming graph, and let $S \subseteq V$, $|S|<2^{n-1}$. Then the induced subgraph on $V \setminus S$, $Q_n[V \setminus S]$, has a connected component which contains edges in all $n$ directions. This is easily seen to be tight, since if we were allowed to remove $2^{n-1}$ vertices, we could choose some direction $i$, and remove exactly one vertex out of each of the $2^{n-1}$ edges in the $i$th direction.
I suggest two possible conjectures that generalize this:
Conjecture 1: Let $k<n$, and take $S \subseteq V$, $|S|<2^{n-k}$. Then the subgraph $Q_n[V \setminus S]$ has a connected component that contains a $k$-dimensional subcube in all possible ${n \choose k}$ directons. From similar considerations to the case above, $2^{n-k}$ is an obvious upper-bound.
The second conjecture, which would imply the first, uses a more restricted definition of connectivity. For an induced subgraph of the hamming cube, $Q_n[V \setminus S]$, we say that two $k$-dimensional subcubes are adjacent if they share a common $k-1$-dimensional facet. By taking transitive closures, this defines another notion of connected components, which we can call $k-1$-facet connected components.
Conjecture 2: Let $k<n$, and take $S \subseteq V$, $|S|<2^{n-k}$. Then the subgraph $Q_n[V \setminus S]$ has a $k-1$-facet connected component that contains a $k$-dimensional subcube in all possible ${n \choose k}$ directons.
