Théorème de Hales-Jewett

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.

Soit ${\displaystyle 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 ${\displaystyle w(x)}$ sur ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 :

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

Soient n = 3, H = 2 et c = 2. L'hypercube ${\displaystyle 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 ${\displaystyle 2x}$, qui correspond à la droite 21, 22, 23 ; une autre droite combinatoire est ${\displaystyle 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).

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 ${\displaystyle W_{n}^{H}}$ en c couleurs, on donne un sous-ensemble arbitraire A de l'hypercube ${\displaystyle 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.

• (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).

• Emo Welzl, The Hales-Jewett Theorem - Cours de combinatoire.
• Article de Science News sur la preuve collaborative du théorème de Hales-Jewett de densité
• Un article de blog de Steven Landsburg expliquant comment la preuve de ce théorème a été améliorée en collaboration sur un blog

• Portail des mathématiques
• Portail de l'informatique théorique