2
$\begingroup$

I've been working on some problems in introductory combinatorics, and I would like some help on going about proving Sauer-Shelah's theorem.

A family $\mathcal{F}$ shatters a set $A$ if for every $B \subset A$, there is an $F \in \mathcal{F}$ such that $F \cap A = B.$ I want to show that if $\mathcal{F} \subset 2^{[n]}$ (i.e. the power set of $[n]$) and $|\mathcal{F}| > \sum_{i=0}^k \binom{n}{i}$, then there is a set $A \subset [n]$ of size $k+1$ such that $\mathcal{F}$ shatters $A$.

I started this by going about an "assume for the sake of contradiction" proof in which I stated that for all sets $A \subset [n]$ of size $k+1$, $\mathcal{F}$ does not shatter $A$. Thus, for every $A$ that satisfies the above, there exists a $B \subset A$ such that there is no $F \in \mathcal{F}$ such that $F \cap A = B.$ The problem is, I am having some difficulty figuring out how the construction of $\mathcal{F}$ makes meaningful implications about the contents of $B$ in this situation. Is it possible that I should go about this proof directly? Any recommendations would be appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

The induction proof is easier if you prove a stronger result: if $\mathscr{F}\subseteq 2^{[n]}$, then $\mathscr{F}$ shatters at least $|\mathscr{F}|$ subsets of $[n]$. Since $[n]$ has only $\sum_{i=0}^k\binom{n}i$ subsets of cardinality less than $k+1$, any $\mathscr{F}$ of cardinality greater than $\sum_{i=0}^k\binom{n}i$ must then shatter some subset of cardinality at least $k+1$ and hence one of cardinality $k+1$.

Clearly every non-empty $\mathscr{F}$ shatters $\varnothing$, so in particular $\mathscr{F}$ shatters at least one subset of $[n]$ if $|\mathscr{F}|=1$. Now assume that $|\mathscr{F}|>1$, and $\mathscr{G}$ shatters at least $|\mathscr{G}|$ subsets for each $\mathscr{G}\subsetneqq\mathscr{F}$. For each $r\in[n]$ let $\mathscr{F}_r=\{F\in\mathscr{F}:r\in F\}$ and $\mathscr{F}_r'=\mathscr{F}\setminus\mathscr{F}_r$.

  • Show that there is an $r\in[n]$ such that $\mathscr{F}_r\ne\varnothing\ne\mathscr{F}_r'$.

By hypothesis $\mathscr{F}_r$ and $\mathscr{F}_r'$ shatter at least $|\mathscr{F}_r|$ and $|\mathscr{F}_r'|$ subsets, respectively. Let $\mathscr{S}$ be the family of subsets shattered by $\mathscr{F}$, $\mathscr{S}_r$ be the family of subsets shattered by $\mathscr{F}_r$ and $\mathscr{S}_r'$ the family of subsets shattered by $\mathscr{F}_r'$.

  • Show that $$\mathscr{S}\supseteq(\mathscr{S}_r\setminus\mathscr{S}_r')\cup(\mathscr{S}_r'\setminus\mathscr{S}_r)\cup(\mathscr{S}_r\cap\mathscr{S}_r')\cup\{A\cup\{r\}:A\in\mathscr{S}_r\cap\mathscr{S}_r'\}\;,$$ and that the four sets whose union is being taken on the right are pairwise disjoint.
  • Conclude that $|\mathscr{S}|\ge|\mathscr{F}|$.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .