# Set that doesn't shatter certain subsets

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.

• 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? – Alex Ravsky Dec 21 '18 at 3:43
• 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$. – Alex Ravsky Dec 21 '18 at 3:44
• @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$ – 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.