## Sauer’s Lemma

I’ve been slowly working my way through the computational learning theory paper “On Weak Learning” by D. Helmbold and M. Warmuth. On my first scan, I caught a reference to Sauer’s Lemma in the proof of Theorem 7.3. I had never heard of Professor Sauer or his lemma; so, I checked the paper’s references and learned it was a result in Combinatorics. Moreover, the proof is short. So I read the paper and took some notes on it, as is my habit of doing.

It turns out that a number of people have proven the result known as Sauer’s lemma independently, but the context of N. Sauer’s proof is worth mentioning. Apparently, Paul Erdős asked Sauer the following question:

Is it true that if $\mathscr{F}$ is a family of subsets of some infinite set $S$ then either there exists to each number $n$ a set $A\subset S$ of cardinality $n$ such that $\left|\mathscr{F}\cap A\right|=2^{n}$ or there exists some number $N$ such that $\left|\mathscr{F}\cap A\right|\leq\left|A\right|^{c}$ for each $A\subset S$ with $\left|A\right|\geq N$ for some constant $c$.

(Here, $\mathscr{F}\cap A:=\left\{F\cap A: F\in\mathscr{F}\right\}$)

Sauer answered the question in the affirmative. My notes can be found here.

1. N. Sauer, On the density of families of sets, Journal of Combinatorial Theory, Series A 13 (1972), 145-147.
Advertisements
This entry was posted in math.CO and tagged , , , . Bookmark the permalink.