Let $A\subset \mathcal{P}(\{1, \dots, n\}) $ and $ B \subset \{1, \dots, n \}$

We say $A$ shatters $B$ if $\forall y \subset B, \exists x \in A$ such that $x \cap B = y$.

I am asked to show that if $A$ does not shatter the sets: $\{1,2,3\},\{2,3,4\},\ \dots, \{n-2,n-1,n,\}, \{n-1,n,1\}, \{n,1,2\}$ and $n$ is a multiple of $3$ then $|A| \leq 7^{\frac{n}{3}}$

My current thinking is that, for each of these $3$-sets, we have to miss at least one of their subsets.

Specifically, for each $a \subset \{x,y,z\}$ there are $2^{n-3}$ subsets of $\{1,\dots,n\}$ that intersect with $\{x,y,z\}$ to give $a$. (Call the set of there $2^{n-3}$ subsets $C_{\{x,y,z\}}(a)$) Hence if $A$ does not shatter $\{1,2,3\}$ because we are missing $a$, then $A$ cannot contain these $2^{n-3}$ subsets.

I want to say that there is some subset $B \subset \mathcal{P}(\{1,\dots,n\}$ of size $8* 7^{\frac{n}{3}}$ such that we must have $A \subset B$, and we may only have at most $\frac{7}{8}$ of the elements of $B$. I suspect we have something like:

$B = \bigcup_{\{x,y,z\} \text{ mentioned earlier}}\bigcup_{a \subset \{x,y,z\}} C_{\{x,y,z\}}(a)$

However, at this point I am stuck and I'm not sure how to proceed. I can't think of a nice way to count the size of $B$ and show it is what I want because I can't think of an easy way to account for all of the overlaps occurring.

  • $\begingroup$ Since $\mathcal{P}(\{1, \dots, n\})$ is a family of (non-empty) subsets of $\{1, \dots, n\}$ and $A$, $B$ are subsets of this family, they are also families of sets. Then $A$ does not shatter the sets ... means $A$ does not shatter the family consisting of these sets, right? $\endgroup$ – Alex Ravsky Dec 21 '18 at 3:43
  • 2
    $\begingroup$ Anyway, I don’t understand the definition of $A$ shatters $B$. If $A$ shatters $B$ then, $B\subset B$ so there exists $x\subset A$ such that $x\cap B=B$, that is $x\supset B$. So $A\supset B$. Conversely, if $A\supset B$ than for any $y\subset B$ we have $y\subset A$ so if we put $x=y$ then $x\cap B=y$. That is $A$ shatters $B$ iff $A\supset B$. $\endgroup$ – Alex Ravsky Dec 21 '18 at 3:44
  • $\begingroup$ @AlexRavsky my apologies, I wrote the definition wrong. Firstly, $A$ is a family of subsets and $B$ is a subset. Secondly, $A$ shatters $B$ if for all $y \subset B \; \exists x \in A$ such that $x \cap B = y$ $\endgroup$ – user366818 Dec 22 '18 at 15:11

Consider the $n/3$ sets $$ \{1,2,3\},\{4,5,6\},\ldots,\{n-2,n-1,n\}. $$ Since $A$ doesn't shatter $\{1,2,3\}$, there exists some subset $T_{123}$ such that $S \cap \{1,2,3\} \neq T_{123}$ for all $S \in A$. Define $T_{456},\ldots$ similarly. Then $$ A \subseteq [\mathcal{P}(\{1,2,3\}) \setminus \{T_{123}\}] \times [\mathcal{P}(\{4,5,6\}) \setminus \{T_{456}\}] \times \cdots \times [\mathcal{P}(\{n-2,n-1,n\}) \setminus \{T_{n-2,n-1,n}\}]. $$ Each of the $n/3$ factors on the right-hand side contains $2^3-1=7$ elements, and so the right-hand side consists of $7^{n/3}$ sets.

When $n > 3$, this bound isn't tight, since the right-hand side does shatter all other adjacent triplets.


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.