Nombre de van der Waerden

Le théorème de van der Waerden dit que pour tous les entiers naturels $r$ et $k$ , il existe un entier naturel $N(r,k)$ tel que si l'on colorie les entiers $1,2,\ldots ,N(r,k)$ en $r$ couleurs, il existe une progression arithmétique de longueur $k$ dans $1,2,\ldots ,N(r,k)$ dont les éléments ont tous la même couleur.

Les nombres de van der Waerden sont les plus petits des nombres $N(r,k)$ pour lesquels ces progressions arithmétiques existent. On les note $W(r,k)$ .

Table des nombres de van der Waerden modifier

Peu de valeurs sont connues. Les nombres $W(2,k)$ sont la suite A005346 de l'OEIS. Voici une table plus complète de valeurs exactes^[1]^,^[2] :

r\k	3	4	5	6	7
2 couleurs	9	35	178	1132	> 3703
3 couleurs	27	293	> 2173	> 11191	> 43855
4 couleurs	76	> 1048	> 17705	> 91331	> 393469
5 couleurs	> 170	> 2254	> 98740	> 540025

Un majorant est donné par Timothy Gowers en 2001^[3], à savoir :

W(r,k)\leq 2^{2^{r^{2^{2^{k+9}}}}}

en relation avec une démonstration du théorème de Szemerédi. De plus, on a

W(2,k)>2^{k}/k^{\varepsilon }\,

pour tout $\varepsilon$ et pour $k$ assez grand^[4].

Pour les nombres $W(2,k)$ , donc pour deux couleurs, et des nombres premiers $p$ on a ^[5]

W(2,p+1)>p\cdot 2^{p}.

Certificats modifier

Un certificat pour la valeur $W(r,k)$ 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 $W(3,2)$ . La longueur d'un certificat est un minorant strict de $W(r,k)$ : si une certificat pour la valeur $W(r,k)$ a longueur $n$ , alors $W(r,k)>n$ . L'article de P. Herwig, M. J. H. Heule, M. van Lambalgen et H. van Maaren^[2] décrit l'usage de divers logiciels pour construire des certificats.

Notes et références modifier

↑ Marijin J. H. Heule, « Improving the odds. New lower bounds for Van der Waerden Numbers », Université de technologie de Delft, 14 mai 2009 (consulté le 10 janvier 2018)
↑ ^{a et b} P. Herwig, M. J. H. Heule, M. van Lambalgen et H. van Maaren, « A new method to construct lower bounds for Van der Waerden numbers », The Electronic Journal of Combinatorics, vol. 14,‎ 2007, article n^o R6 (lire en ligne, consulté le 9 janvier 2018)
↑ Timothy Gowers: A new proof of Szemerédi's theorem, Geom. Funct. Anal., 11(3): S. 465-588, 2001. Online-Version bei http://www.dpmms.cam.ac.uk/~wtg10/papers.html.
↑ Zoltán Szabó, « An application of Lovász' local lemma -- a new lower bound for the van der Waerden number », Random Struct. Algorithms, vol. 1, n^o 3,‎ 1990, p. 343–360
↑ E. Berlekamp, « A construction for partitions which avoid long arithmetic progressions », Canadian Mathematics Bulletin, vol. 11,‎ 1968, p. 409–414.

Liens externes modifier

(en) Eric W. Weisstein, « van der Waerden Number », sur MathWorld

Articles liés modifier

Théorie de Ramsey

[1] Marijin J. H. Heule, « Improving the odds. New lower bounds for Van der Waerden Numbers », Université de technologie de Delft, 14 mai 2009 (consulté le 10 janvier 2018)

[Cert-2] {a et b} P. Herwig, M. J. H. Heule, M. van Lambalgen et H. van Maaren, « A new method to construct lower bounds for Van der Waerden numbers », The Electronic Journal of Combinatorics, vol. 14,‎ 2007, article n^o R6 (lire en ligne, consulté le 9 janvier 2018)

[3] Timothy Gowers: A new proof of Szemerédi's theorem, Geom. Funct. Anal., 11(3): S. 465-588, 2001. Online-Version bei http://www.dpmms.cam.ac.uk/~wtg10/papers.html.

[4] Zoltán Szabó, « An application of Lovász' local lemma -- a new lower bound for the van der Waerden number », Random Struct. Algorithms, vol. 1, n^o 3,‎ 1990, p. 343–360

[5] E. Berlekamp, « A construction for partitions which avoid long arithmetic progressions », Canadian Mathematics Bulletin, vol. 11,‎ 1968, p. 409–414.

[1]

[2]

[3]

[4]

[5]