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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s