5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Isn't an optimal choice for $A$ all sequences with at most $d-1$ zeros? That gives $|A|\le\sum_{k=0}^{d-1}{n \choose k}$. $\endgroup$ – Christian Remling Jul 25 '17 at 6:18
  • $\begingroup$ For the asymptotics of this, perhaps search for "tail bounds" for the binomial distribution. $\endgroup$ – Christian Remling Jul 25 '17 at 6:23
  • $\begingroup$ It seems like a reasonable conjecture that it is indeed an optimal choice of A. But I don't see an obvious proof of this fact. $\endgroup$ – ivmihajlin Jul 25 '17 at 6:26
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is the statement that you are proving? $\endgroup$ – Emil Jeřábek Jul 25 '17 at 10:48
  • $\begingroup$ @EmilJeřábek what was supposed by Christian Remling, see update of my answer. $\endgroup$ – Fedor Petrov Jul 25 '17 at 10:54
  • $\begingroup$ Oh I see, thank you. $\endgroup$ – Emil Jeřábek Jul 25 '17 at 13:29
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.