Abstract:
One of the central results of Ramsey theory is van der
Waerden's theorem on arithmetic progressions:
Let N denote the set of positive integers. Let f be any
function from N to a finite set. Then there are arbitrarily large
(finite) arithmetic progressions P = {a, a+d, a+2d, ..., a+kd} such
that f is constant on P.
There is a "canonical version" of this theorem, which says:
If f is any coloring of N (which means that f is a function
from N to an infinite set), then there are arbitrarily large (finite)
arithmetic progressions P such that either f is constant on P or f is
1-1 on P.
We discuss these results and another simple theorem, which
- has the same flavor as van der Waerden's theorem,
- is much easier to prove than van der Waerden's theorem,
- does not directly imply, and is not directly implied by,
van der Waerden's theorem,
- does not have a "density version" (as van der Waerden's
theorem does)
- does not (yet) have a canonical version.
|