Sets with no "full" projection on sufficiently large subset of coordinates Let $\ M\ $ be a finite set. Call set $A\ \ d$-fully shattering ($d\le|M|$) $\ \Leftarrow:\Rightarrow\ $ the following are true:


*

*$A \subset \{0,1\}^M$.

*$\forall_{\, S \in\binom Md}\ \pi_S(A)\ne\{0,1\}^S,\,\ $
where $\,\ \pi_S:\{0,1\}^M\rightarrow\{0,1\}^S\ $ is the canonical projection.


I'm interested in the upper bounds on the size of $d$-fully shattering sets especially in the regime $d=|M|^\alpha$.
I'm pretty sure this object was studied before but I don't know under what name. Any references or hints would be greatly appreciated.
 A: Yes, as Christian Remling says, the maximal size of $S$ is indeed $\sum_{i<d} \binom{n}i$. This is known as the shattering lemma (found independently by Sauer, Shelah-Pearls, and Vapnik-Chervonenkis), see the linear algebraic clever proof by Frankl and Pach here:
https://gowers.wordpress.com/2008/07/31/dimension-arguments-in-combinatorics/
I particularly like the following polynomial version of it. 
Let $X$ denote a space of multilinear polynomials $f(x_1,\dots,x_n)\in \mathbb{F}_2[x_1,\dots,x_n]$ of degree at most $d-1$. If $|A|>\dim X=\sum_{i<d}\binom{n}i$, there exists a non-zero function $c:A\to \mathbb{F}_2$ on $A$ satisfying $\sum_{x\in A} c(x)f(x)=0$ for all $f\in X$. Rewrite this as $$\Phi(f):=\sum_{x\in B} f(x)=0,$$ where $B=\{x\in A: c(x)=1\}$. But $\Phi(f)=0$ can not hold for any multilinear polynomial $f$ (take $W=(w_1,\dots,w_n)\in B$ and $f(x_1,\dots,x_n)=\prod_i (x_i+w_i+1)$). So, consider the monomial $h$ of minimal degree $k$ such that $\Phi(h)=1$.  We have $k\geqslant d$, we may think that $h(x_1,\dots,x_n)=x_1\dots x_k$. I claim that $S=\{1,\dots,k\}$ satisfies the following condition: for each $T\subset S$, the number $\eta(T)$ of elements $x\in B$ such that $\{i\in S: x_i=1\}=T$ is odd. In particular, the set of such $x$ is non-empty, as we need. The claim follows from the identity $$\Phi\left(\prod_{i\in T} x_i\right)=\sum_{S_1\supset T} \eta(S_1)=\begin{cases}1,& T=S\\0,& T\ne S\end{cases}$$
and inclusion-exclusion. 
A: This is a comment about shattering.
Let $U$ be a finite set. If $S\subseteq [n]$ has cardinality $d$, then
call $U^n$ an $n$-dimensional cube and 
call $U^S$ the $d$-dimensional face indexed by $S$. A subset
$A\subseteq U^n$ shatters the face $U^S$ if the projection of
$U^n$ onto $U^S$ maps $A$ onto $U^S$.
The Shattering Lemma, due to Vapnik-Chervonenkis and also to
Perles–Sauer–Shelah, concerns the case $U=\{0,1\}$.
It is the statement that the maximal size of
a subset $A\subseteq \{0,1\}^n$ that shatters no
$d$-dimensional face is $\sum_{k<d} \binom{n}{k}$.
An explicit nonshattering set of size
$\sum_{k<d} \binom{n}{k}$ is known, namely
the set of all tuples in $\{0,1\}^n$ with fewer than
$d$ ones.
A dual combinatorial
problem came up in a paper I wrote with Emil Kiss
and Agnes Szendrei. We wanted to know:
what is the minimal size of a subset $A\subseteq U^n$
that shatters every $d$-dimensional face?
Here $U$ is allowed to be an arbitrary finite set.
We found that (if $n\geq d>1$) there is some $A\subseteq U^n$ that shatters every
$d$-dimensional face, which satisfies the bound
$$
|A|\leq \lceil d\log_b(n)+\log_b(u^d/d!)
\rceil,
$$
where $u=|U|$ and $b=u^d/(u^d-1)$. For our purposes, $u, d, b$
are fixed, but $n$ is allowed to vary.
Although this $\sim \log_b(n)$ bound may not be optimal,
we know that there is no $A\subseteq U^n$
of size $<\log_u(n)$ that shatters every $d$-dimensional
face, so $\log(n)$ is the right growth order.
The thing that might interest readers of this thread
is: we proved the existence of a fully-shattering set
of $\log(n)$-size with a probabilistic argument.
We computed the expected number of unshattered $d$-dimensional faces
for a randomly chosen subset $A\subseteq U^n$ of size 
$\lceil d\log_b(n)+\log_b(u^d/d!)
\rceil$ and found it to be less than $1$, so at least one of the
sets of this size unshatters zero faces (i.e. shatters every face).
We don't have an explicit description of any
$\log(n)$-size fully-shattering sets.
[This combinatorial problem came up while investigating the
minimal sizes of generating
sets of powers $\mathbb U^n$ of a finite algebraic structure $\mathbb U$.]
