Exercise 6, § 2

Let $c$ be a natural number.

a) There exists a unique family of mappings $R_c: (\mathbf{N}^*)^c\rightarrow \mathbf{N}^*$, for $c\geqslant 2$, satisfying the following properties:

(i) If there exists $i$ such that $n_i= 1$, then $R_c(n_1, . . . , n_c) = 1$ ;

(ii) One has $R_2(m, n) = R_2(m-1, n) + R_2(m, n-1)$ if $m$ and $n$ are integers $\geqslant 2$ ;

(iii) If $c\geqslant 3$, one has $R_c(n_1, . . . , n_c) = R_{c-1}(n_1, . . . , n_{c-2},R_2(n_{c-1}, n_c))$ for all $(n_1, . . . , n_c)\in \mathbf{N}^c$.

b) One has $R_2(m, n) =(^{m+n-2}_{m-1})$ for every pair $(m, n)$ of integers $\geqslant 1$.

c) For every finite sequence $(n_1, . . . , n_c)$ of natural numbers $\geqslant 1$ and every natural number $R\geqslant 1$, one says that the property $\mathbf{R}(n_1, . . . , n_c; R)$ is satisfied if, for every complete graph whose set of vertices S has cardinal $\geqslant R$ and every partition $P = (F_1, . . . ,F_c)$ of the set F of its arrows, there exists an integer $i\in \{1, . . . , c\}$ and a subset A of S of cardinal $n_i$ such that every arrow of G joining two elements of A belongs to $F_i$.

Prove the property $\mathbf{R}(n_1, . . . , n_c; R_c(n_1, . . . , n_c))$.

d) We denote by $R(n_1, . . . , n_c)$ the smallest integer $R\geqslant 1$ such that the property $\mathbf{R}(n_1, . . . , n_c; R)$ is satisfied ("Ramsey numbers").

e) One has $R(n,2) =n$ for every integer $n\geqslant 2$ ; one has $R(3,3) = 6$.

f) Prove that $R(4,3) = 9$.

g) Calculate $R(5,5)$ ; calculate $R(6,6)$.