Le théorème de van der Waerden dit que pour tous les entiers naturels et , il existe un entier naturel tel que si l'on colorie les entiers en couleurs, il existe une progression arithmétique de longueur dans dont les éléments ont tous la même couleur.
Les nombres de van der Waerden sont les plus petits des nombres pour lesquels ces progressions arithmétiques existent. On les note .
Table des nombres de van der Waerden
Peu de 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
Un majorant est donné par Timothy Gowers en 2001Timothy Gowers: A new proof of Szemerédi's theorem, Geom. Funct. Anal., 11(3): S. 465-588, 2001. Online-Version bei https://www.dpmms.cam.ac.uk/~wtg10/papers.html., à savoir :
en relation avec une démonstration du théorème de Szemerédi. De plus, on a
pour tout et pour assez grand.
Pour les nombres , donc pour deux couleurs, et des nombres premiers on a .
Certificats Un certificat pour la valeur est une suite sur r couleurs qui ne possède pas de progression arithmétique de longueur k. Par exemple, la suite RVB est un certificat pour . La longueur d'un certificat est un minorant strict de : si une certificat pour la valeur a longueur , alors . L'article de P. Herwig, M. J. H. Heule, M. van Lambalgen et H. van Maaren décrit l'usage de divers logiciels pour construire des certificats.
Notes et références
Liens externes
Articles liés Théorie de Ramsey
Van der Waerden Catégorie:Combinatoire