MathDB

For every natural number

r

, the set of

r

-tuples of natural numbers is partitioned into finitely many classes. Show that if

f(r)

is a function such that

f(r)\geq 1

and \lim _{r\rightarrow \infty} f(r)\equal{}\plus{}\infty, then there exists an infinite set of natural numbers that, for all

r

, contains

r

-triples from at most

f(r)

classes. Show that if f(r) \not \rightarrow \plus{}\infty, then there is a family of partitions such that no such infinite set exists. P. Erdos, A. Hajnal

Problem Statement