Le théorème de van der Waerden (d'après Bartel Leendert van der Waerden) est un théorème de combinatoire, plus précisément de la théorie de Ramsey. Le théorème est le suivant
De manière plus formelle, l'énoncé dit que si on partitionne l'ensemble en parties, au moins une des parties contient une progression arithmétique de longueur . Le théorème affirme seulement l'existence de l'entier mais ne dit rien sur sa valeur ; une formule générale en fonction de n'est pas connue.
Exemples 1.— Pour le théorème dit simplement que si est assez grand, il existe deux éléments de même couleur parmi ; il suffit d'appliquer le principe des tiroirs et de choisir .
2.— Pour et pour trois couleurs voici un exemple : {| class="wikitable" |+ !1!!2!!3!!4!!5 !!6!!7!!8!!9 !!10!!11!!12!!13!!14!!15!!16!!17
||||||| || || || ? |} Quel que soit le choix de la couleur pour , on obtient une progression arithmétique de longueur 3 : pour , c'est , pour c'est et pour , c'est . Cet exemple ne dit rien sur la valeur de . On peut montrer que est un nombre qui convient pour , et il existe une séquence de longueur 26 sans progression de longueur 3, par exemple : RRVVRRVBVBBRBRRVRVVBRBBVBV.
Nombres de van der Waerden
Les nombres de van der Waerden sont les plus petits des nombres . On les note . Seules quelques valeurs sont connues. Les nombres sont la . Voici une table plus complète de valeurs exactes.
{| class="wikitable" ! r \ k ! 3 ! 4 ! 5 ! 6 ! 7 |- | 2 couleurs | align="right" | 9 | align="right" | 35 | align="right" | 178 | align="right" | 1132 | align="right" | > 3703 |- | 3 couleurs | align="right" | 27 | align="right" | 293 | align="right" | > 2173 | align="right" | > 11191 | align="right" | > 43855 |- | 4 couleurs | align="right" | 76 | align="right" | > 1048 | align="right" | > 17705 | align="right" | > 91331 | align="right" | > 393469 |- | 5 couleurs | align="right" | > 170 | align="right" | > 2254 | align="right" | > 98740 | align="right" | > 540025
Historique En 1926, van der Waerden, avec Emil Artin et Otto Schreier, ont commencé à travailler sur une conjecture du mathématicien néerlandais Baudet qui formule la conjecture suivante.
Cette conjecture est étendue par Artin au cas d'une partition en classes ; cette conjecture est affinée par O. Schreier en l’énoncé démontré par van der Waerden.. Van der Waerden revient sur la genèse du théorème et de sa démonstration dans un article en 1965. republié en 1971..
Démonstrations Plusieurs démonstrations directes existent, purement combinatoires ou topologiques. Deux de ces démonstrations sont reproduites dans le livre Combinatorics on Words de M. Lothaire — Réédition cartonnée avec corrections en 1997 dans la Cambridge Mathematical Library, .. La première est combinatoire., la deuxième topologique.. Une preuve courte est de Graham et Rothschild.. Une preuve combinatoire détaillée est dans le livre de Khintchin. — Réédition de la première traduction de 1952..
Une démonstration indirecte consiste à constater que le théorème est une conséquence assez facile du théorème de Szemerédi que voici : Soient un entier positif et . Alors il existe un entier tel que tout sous-ensemble de d'au moins éléments contienne une progression arithmétique de longueur .
Pour démontrer le théorème de van der Waerden pour deux entiers , on choisit . Il existe alors, parmi les r parties monochromes de , l'une au moins qui a plus de éléments. Comme , cette partie contient une progression arithmétique de longueur .
Notes et références
Liens externes
Articles liés Théorie de Ramsey
Van der Waerden Catégorie:Combinatoire