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 is a family of subsets of some infinite set then either there exists to each number a set of cardinality such that or there exists some number such that for each with for some constant .*

*(Here, )*

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

- N. Sauer, On the density of families of sets,
*Journal of Combinatorial Theory, Series A* **13** (1972), 145-147.

### Like this:

Like Loading...

*Related*