Exercice 6, § 2

Soit $c$ un entier naturel.

a) Il existe une unique famille d’applications $R_c: (\mathbf{N}^*)^c\rightarrow \mathbf{N}^*$, pour $c\geqslant 2$, vérifiant les propriétés suivantes :

(i) S’il existe $i$ tel que $n_i= 1$, alors $R_c(n_1, . . . , n_c) = 1$ ;

(ii) On a $R_2(m, n) = R_2(m-1, n) + R_2(m, n-1)$ si $m$ et $n$ sont des entiers $\geqslant 2$ ;

(iii) Si $c\geqslant 3$, on a $R_c(n_1, . . . , n_c) = R_{c-1}(n_1, . . . , n_{c-2},R_2(n_{c-1}, n_c))$ pour tout $(n_1, . . . , n_c)\in \mathbf{N}^c$.

b) On a $R_2(m, n) =(^{m+n-2}_{m-1})$ pour tout couple $(m, n)$ d’entiers $\geqslant 1$.

c) Pour toute suite finie $(n_1, . . . , n_c)$ d’entiers naturels $\geqslant 1$ et tout entier naturel $R\geqslant 1$, on dit que la propriété $\mathbf{R}(n_1, . . . , n_c; R)$ est satisfaite si, pour tout graphe complet dont l’ensemble des sommets S est de cardinal $\geqslant R$ et toute partition $P = (F_1, . . . ,F_c)$ de l’ensemble F de ses flèches, il existe un entier $i\in \{1, . . . , c\}$ et une partie A de S de cardinal $n_i$ tels que toute flèche de G reliant deux éléments de A appartienne à $F_i$.

Démontrer la propriété $\mathbf{R}(n_1, . . . , n_c; R_c(n_1, . . . , n_c))$. d) On note $R(n_1, . . . , n_c)$ le plus petit entier $R\geqslant 1$ tel que la propriété $\mathbf{R}(n_1, . . . , n_c; R)$ soit vérifiée (« nombres de Ramsey »).

e) On a $R(n,2) =n$ pour tout entier $n\geqslant 2$ ; on a $R(3,3) = 6$.

f) Démontrer que $R(4,3) = 9$.

¶ g) Calculer $R(5,5)$ ; calculer $R(6,6)$.