Sets with no “full” projection on sufficiently large subset of coordinates

Question

Let $\ M\ $ be a finite set. Call set $A\ \ d$-fully shattering ($d\le|M|$) $\ \Leftarrow:\Rightarrow\ $ the following are true:

1. $A \subset \{0,1\}^M$.
2. $\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.

Answer 1

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.

Answer 2

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$.]