Théorème de Hales-Jewett

En mathématiques, le théorème de Hales-Jewett est un résultat combinatoire fondamental de la théorie de Ramsey, nommé d'après Alfred W. Hales et Robert I. Jewett. Il concerne la dimension dans laquelle des objets de cette dimension doivent nécessairement présenter une certaine régularité dans leur structure combinatoire : il est impossible que de tels objets soient « complètement aléatoires »^[1].

Description informelle[modifier | modifier le code]

Une description géométrique informelle du théorème est la suivante : pour tous entiers positifs n et c, il existe un nombre H tel que si les cellules d'un cube de côté n en dimension H sont colorées en c couleurs, il existe une ligne, une colonne ou une diagonale (dans un sens précisé ci-dessous) de longueur n dont toutes les cellules sont de la même couleur. En d'autres termes, la généralisation du jeu de morpion ou tic-tac-toe en dimension supérieure, et multi-joueurs, ne peut pas se terminer par un match nul, quelle que soit la taille de n, quel que soit le nombre c de joueurs, et quel que soit l'ordre des joueurs, à la seule condition qu'il soit joué sur un plateau de dimension H suffisamment élevée. Par un argument de vol de stratégie (en) standard, on peut alors conclure que si deux joueurs alternent, alors le premier joueur possède une stratégie gagnante lorsque H est suffisamment grand, bien qu'aucun algorithme pratique pour obtenir cette stratégie ne soit connu.

Énoncé formel[modifier | modifier le code]

Soit $W_{n}^{H}$ l'ensemble des mots de longueur H sur un alphabet de n lettres ; c'est-à-dire l'ensemble des suites de longueur H à éléments dans {1, 2, ..., n }. C'est cet ensemble qui est l'hypercube objet du théorème.

Un mot variable $w(x)$ sur $W_{n}^{H}$ est un mot de longueur H qui contient une élément spécial x à la place d'au moins une des lettres. Les mots $w(1),w(2)\ldots ,w(n)$ obtenus en remplaçant toutes les instances de l'élément spécial x respectivement par 1, 2, ..., n, forment une droite combinatoire dans l'espace $W_{n}^{H}$ ; les droites combinatoires correspondent aux lignes, aux colonnes et à (certaines des) diagonales de l'hypercube. Le théorème de Hales-Jewett s'énonce alors comme suit :

Théorème de Hales-Jewett — Pour des entiers positifs donnés n et c, il existe un entier positif H, dépendant de n et c, tel que pour toute partition de $W_{n}^{H}$ en c parties, il y a au moins une partie qui contient une droite combinatoire^[2] .

Si on identifie les joueurs à la couleur de leurs pions, le théorème assure l'existence d'une droite combinatoire monochrome.

Exemple[modifier | modifier le code]

Soient n = 3, H = 2 et c = 2. L'hypercube $W_{n}^{H}$ , dans ce cas, est simplement de le plateau du morpion usuel, avec ses neuf positions :

11	12	13
21	22	23
31	32	33

Un exemple de droite combinatoire est le mot $2x$ , qui correspond à la droite 21, 22, 23 ; une autre droite combinatoire est $xx$ , qui est la droite 11, 22, 33. (la droite 13, 22, 31, bien qu'une droite valide pour le morpion, n'est pas représenté par une droite combinatoire). Dans ce cas particulier, le théorème de Hales-Jewett ne s'applique pas ; il est possible de diviser le plateau du morpion en deux ensembles, par exemple {11, 22, 23, 31} et {12, 13, 21, 32, 33}, dont aucun ne contient une droite combinatoire (et correspondrait à un match nul au jeu de tic-tac-toe). D'un autre côté, si on augmente H à 8 par exemple (de sorte que le plateau est maintenant en dimension huit, avec 3 ⁸ = 6561 positions), et si on divise ce plateau en deux ensembles (les "zéros" et les "croix"), alors l'un des deux ensembles doit contenir une droite combinatoire (c'est-à-dire qu'un mouvement gagnant est possible dans cette variante du tic-tac-toe).

Liens avec d'autres théorèmes[modifier | modifier le code]

L'énoncé admet le corollaire suivant : si A est l'ensemble des nombres à huit chiffres dont les chiffres sont tous soit 1, 2, 3 (donc A contient des nombres tels que 11333233), et si on colorie A avec deux couleurs, alors A contient au moins une progression arithmétique de longueur trois, dont tous les éléments sont de la même couleur Une formulation plus générale montre que le théorème de Hales-Jewett généralise le de van der Waerden.

Tout comme le théorème de van der Waerden a une « version en densité » plus forte dans le théorème de Szemerédi, le théorème de Hales-Jewett a également une version en densité. Dans cette version renforcée du théorème de Hales-Jewett, au lieu de colorer tout l'hypercube $W_{n}^{H}$ en c couleurs, on donne un sous-ensemble arbitraire A de l'hypercube $W_{n}^{H}$ avec une densité donnée 0 < δ < 1. Le théorème dit que si H est suffisamment grand en fonction de n et de δ, alors l'ensemble A doit nécessairement contenir une droite combinatoire complète.

Le théorème de Hales-Jewett avec densité a été prouvé à l'origine par Furstenberg et Katznelson en utilisant la théorie ergodique^[3]. En 2009, le projet Polymath a développé une nouvelle preuve^[4]^,^[5] du théorème Hales-Jewett en densité, sur la base d'idées tirées de la preuve du théorème des coins (en)^[6]. Dodos, Kanellopoulos et Tyros ont donné une version simplifiée de la preuve du Polymath^[7].

Le théorème de Hales–Jewett est généralisé par le théorème de Graham–Rothschild (en) sur des cubes combinatoires en dimension supérieure.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hales–Jewett theorem » (voir la liste des auteurs).

↑ Hales et Jewett, « Regularity and positional games », Trans. Amer. Math. Soc., vol. 106, n^o 2,‎ 1963, p. 222–229 (DOI 10.1090/S0002-9947-1963-0143712-1, MR 0143712).
↑ Ronald L. Graham, Bruce L. Rothschild et Joel H. Spencer, Ramsey Theory, Wiley-Interscience, 1991, 2^e éd. (ISBN 978-0-471-50046-9), p. 36.
↑ Furstenberg et Katznelson, « A density version of the Hales–Jewett theorem », Journal d'Analyse Mathématique, vol. 57, n^o 1,‎ 1991, p. 64–119 (DOI 10.1007/BF03041066, MR 1191743).
↑ D. H. J. Polymath, « A new proof of the density Hales–Jewett theorem », Annals of Mathematics, vol. 175, n^o 3,‎ 2012, p. 1283–1327 (DOI 10.4007/annals.2012.175.3.6, MR 2912706).
↑
William Timothy Gowers, « Polymath and the density Hales-Jewett theorem », dans Imre Bárány et József Solymosi, An irregular mind, vol. 21, Budapest, coll. « Bolyai Society Mathematical Studies », 2010, 659–687 p. (ISBN 978-963-9453-14-2, DOI 10.1007/978-3-642-14444-8_21, MR 2815619)
{{Article encyclopédique}} : l'usage du paramètre |périodique = János Bolyai Mathematical Society laisse présager
soit d'une confusion entre les modèles {{article encyclopédique}} et {{article}}

soit d'une confusion entre les paramètres périodique et éditeur.
Merci de consulter la documentation des modèles et de corriger l'article.
↑ Ajtai et Szemerédi, « Sets of lattice points that form no squares », Stud. Sci. Math. Hungar., vol. 9,‎ 1974, p. 9–11 (MR 0369299)
↑ Dodos, Kanellopoulos et Tyros, « A simple proof of the density Hales–Jewett theorem », International Mathematics Research Notices, vol. 2014, n^o 12,‎ 2014, p. 3340–3352 (DOI 10.1093/imrn/rnt041, MR 3217664, arXiv 1209.4986).

Liens externes[modifier | modifier le code]

[1] Hales et Jewett, « Regularity and positional games », Trans. Amer. Math. Soc., vol. 106, n^o 2,‎ 1963, p. 222–229 (DOI 10.1090/S0002-9947-1963-0143712-1, MR 0143712).

[2] Ronald L. Graham, Bruce L. Rothschild et Joel H. Spencer, Ramsey Theory, Wiley-Interscience, 1991, 2^e éd. (ISBN 978-0-471-50046-9), p. 36.

[3] Furstenberg et Katznelson, « A density version of the Hales–Jewett theorem », Journal d'Analyse Mathématique, vol. 57, n^o 1,‎ 1991, p. 64–119 (DOI 10.1007/BF03041066, MR 1191743).

[4] D. H. J. Polymath, « A new proof of the density Hales–Jewett theorem », Annals of Mathematics, vol. 175, n^o 3,‎ 2012, p. 1283–1327 (DOI 10.4007/annals.2012.175.3.6, MR 2912706).

[5] William Timothy Gowers, « Polymath and the density Hales-Jewett theorem », dans Imre Bárány et József Solymosi, An irregular mind, vol. 21, Budapest, coll. « Bolyai Society Mathematical Studies », 2010, 659–687 p. (ISBN 978-963-9453-14-2, DOI 10.1007/978-3-642-14444-8_21, MR 2815619)
{{Article encyclopédique}} : l'usage du paramètre |périodique = János Bolyai Mathematical Society laisse présager
soit d'une confusion entre les modèles {{article encyclopédique}} et {{article}}

soit d'une confusion entre les paramètres périodique et éditeur.

Merci de consulter la documentation des modèles et de corriger l'article.

[6] soit d'une confusion entre les modèles {{article encyclopédique}} et {{article}}

[7] soit d'une confusion entre les paramètres périodique et éditeur.

[6] Ajtai et Szemerédi, « Sets of lattice points that form no squares », Stud. Sci. Math. Hungar., vol. 9,‎ 1974, p. 9–11 (MR 0369299)

[7] Dodos, Kanellopoulos et Tyros, « A simple proof of the density Hales–Jewett theorem », International Mathematics Research Notices, vol. 2014, n^o 12,‎ 2014, p. 3340–3352 (DOI 10.1093/imrn/rnt041, MR 3217664, arXiv 1209.4986).

[1]

[2]

[3]

[4]

[5]

[6]

[7]