Density versions of theorems from Lecture 2

Jozsef Solymosi
University of British Columbia

In the previous lecture we proved statements for partitions. When there are only a few partition classes, then the size of at least one partition class is large. In some cases the largeness of a subset is enough in order to prove that it contains a special substructure. Using our previous example, one can prove that every dense subset of the natural numbers contains long arithmetic progressions. (This important theorem is called Szemeredi’s theorem.)

Back to Combinatorics Tutorials