Definition of Strongly Shattering

Question

I am familiar with what it means for a collection $\mathcal{F}\subseteq 2^{[n]}$ to shatter a set $S$, $$2^{S} = \{F \cap S: F\in \mathcal{F}\}.$$

I'm reading a paper and they introduce the notion of strongly shattering a set $S$. If there exists an $I\subseteq [n]\backslash F$ such that $$2^F + I = \{H\cup I: H\subseteq F\}\subseteq \mathcal{F}.$$

This definition does not appear to follow directly from the definition of shattering a set. I would appreciate if someone could explain this definition in plain English so that I could better understand it.

It is clear to me that if $2^F \subseteq \mathcal{F}$ then $\mathcal{F}$ shatters $F$, although this is not the only way in which $\mathcal{F}$ can shatter $F$. Is the idea that $\mathcal{F}$ shatters $F$ and more?

Answer 1

The statement "$\mathcal F$ shatters $S$" can be stated as "For all subsets $A \subseteq S$, there is a set $B$ disjoint from $S$ such that $A \cup B \in \mathcal F$".

The statement "$\mathcal F$ strongly shatters $S$" can be stated as "There is a set $B$ disjoint from $S$ such that for all subsets $A \subseteq S$, $A \cup B \in \mathcal F$".

The only difference is that we must use the same $B$ for every $A$. This is a stronger condition: if $\mathcal F$ strongly shatters $S$, then $\mathcal F$ shatters $S$, but the reverse is not necessarily true.

For example:

• to shatter $\{1,2\}$, $\mathcal F$ might contain the sets $\{3,4,5\}$ (for $\emptyset \subseteq \{1,2\}$), $\{1, 6\}$ (for $\{1\} \subseteq \{1,2\}$), $\{2,4,8\}$ (for $\{2\} \subseteq \{1,2\}$) and $\{1,2,3\}$ (for $\{1,2\} \subseteq \{1,2\}$).
• to strongly shatter $\{1,2\}$, $\mathcal F$ might contain all the sets $\{3,5\}$, $\{1,3,5\}$, $\{2,3,5\}$, and $\{1,2,3,5\}$.