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 .
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.